Lecture 1, Aug 30, 2012:

• Administrivia
• Primality testing vs. factoring; Euler tours vs. Hamiltonian cycles
• Problem complexity and asymptotics
• Analysis of algorithms: Worst case, average-case, self-improving (our focus will be on worst-case analysis)
• Languages and decision problems; the "right" decision problem for factoring
• The complexity class P and its robustness
• Reading: Kevin Wayne's slides

• The existence of problems of complexity n^c (for any c) in P, and why this does not impact the relevance of P
• NP ("managerial approach"): history and motivation, P contained in NP
• NP, IP, PSPACE and EXP; their inter-relationships
• Reductions and their transitivity, Cook and Karp reductions, NP-completeness
• Circuit-SAT and its NP-completeness (informal "proof")
• Reading: Kevin Wayne's slides

• NP-completeness of 3-SAT and k-Clique; the floodgates open!
• coNP-completeness
• Efficient algorithm for 2-SAT (quick coverage)
• The widespread nature of NP-completeness; computation and complexity as lenses on other disciplines
• NP-intermediate languages and statement of Ladner's Theorem
• Major open questions on: complexity classes, famous individual problems, types of reductions
• Reading: Kevin Wayne's slides

• Simple lower-bounds for black-box problems: NP is about structured search
• Recurrences and divide-and-conquer: Quicksort and Mergesort; the motivation for Randomized Quicksort
• Solving recurrences: unfolding, and introducing an auxiliary function: given T(n) = f(n) T(g(n)) + h(n), set T(n) = a(n) T'(n) where a() satisfies the recurrence f(n) a(g(n))= a(n), and solve for T': e.g., alternative proofs for the Mergesort and Karatsuba recurrences
• Randomized algorithms, the expectation (the "probabilistic method" and "long-term average" interpretations), the linearity of expectation and its applications
• Videos and Reading: Chapter 2 of Dasgupta-Papadimitriou-Vazirani and Roughgarden's lectures

• The analysis of Randomized Quicksort
• Markov's inequality and amplification by (careful) repetition
• Randomized algorithms vs. probabilistic analysis of algorithms
• Linear-time selection: deterministic and randomized
• Gauss' complex-multiplication trick and Karatsuba's multiplication algorithm
• Videos and Reading: Roughgarden's lectures, Manuel Blum's notes, and Chapter 2 of Dasgupta-Papadimitriou-Vazirani

• Strassen's matrix-multiplication algorithm
• The Fast Fourier Transform (FFT)
• The complexity of multiplication: only the time-bounds of Schonhage-Strassen and Furer
• Parallelism, multi-core systems, and the abstract PRAM model: emulation of many processors by a few, and simple parallel divide-and-conquer algorithms
• Reading: Chapter 2 and Chapter 6 of Dasgupta-Papadimitriou-Vazirani; also see Manuel Blum's notes on the FFT

• Start dynamic programming (DP): Fibonacci and shortest paths in DAGs, why naive recursion may not be a good idea
• Two views of DP: "DAG of subproblems" and "recursion + memoization" (with a short introduction to hashing and its use in memoization)
• Edit distance, knapsack (with and without repeats), benefits/costs of memoization
• Reading: Chapter 6 of Dasgupta-Papadimitriou-Vazirani

• Common templates that arise in identifying subproblems for dynamic programming
• Max-weight independent sets in trees
• Context-free grammars, parsing, and the CYK algorithm
• All-pairs shortest paths due to Floyd and Warshall (exercise: what happens when the additional parameter k is a bound on the number of edges allowed?)
• The distinction between time and space in sequential and parallel computation
• Edit-distance revisited: start sequence alignment in linear space
• Reading: Chapter 6 of Dasgupta-Papadimitriou-Vazirani, Kevin Wayne's slides

• Complete sequence alignment in linear space
• Savitch's Theorem that partly motivates the above approach, NPSPACE = PSPACE, directed s-t connectivity and LOGSPACE
• MSTs, and additive scaling (to make the smallest edge-weight zero) as intuition for Kruskal's algorithm
• Start greedy algorithms: much of Section 5.1 from DPV:
  • Simple properties of trees and cycles
  • The cut property using an exchange argument; correctness of Kruskal's and Prim's algorithms
  • Implementing each step of UNION-FIND in O(log n) time
  • Description of path-compression (runtime is a reading exercise)
• Bounds alone on the deterministic and randomized complexities of MST
• Reading: Chapter 5 of Dasgupta-Papadimitriou-Vazirani, Kevin Wayne's slides

• Three paradigms for the analysis of greedy algorithms:
  • exchange arguments as in the cut property: scheduling to minimize lateness, and an exchange argument to show the generality of non-preemption as well; the possibility of more-general exchange/perturbation arguments via the optimization of continuous ("potential") functions over compact sets
  • "the greedy algorithm stays ahead": interval scheduling
  • structural bounds: interval partitioning
• Start Dijkstra's algorithm
• Reading: Kevin Wayne's slides

• Dijkstra's single-source shortest paths algorithm
• Randomization when the next (greedy) step is not obvious: game trees, pruning, the analysis of Chomp (and related partial-order games), and game-tree evaluation
• Greedy algorithms in the messy real world:
  • "The greedy algorithm stays almost as ahead as optimal": approximation algorithms and the "shortest job first" heuristic in interval scheduling
  • Local search and the GRASP paradigm
  • Priority algorithms and BubbleSearch heuristics
• Reading: the web-pages linked to above

• Matroids and greedy algorithms
• Lower bounds:
  • the adversarial and information-theoretic methods for deterministic algorithms
  • simple randomized algorithms that beat deterministic lower-bounds, and alternative formula for the expectation; start lower bounds for randomized algorithms
• Reading: the web-pages linked to above

• Recap of the basic "probabilistic method" recipe
• The minimax principle and randomized algorithms:
  • the direction that yields lower bounds for randomized algorithms (short algebraic proof reminiscent of the probabilistic method)
  • simple applications followed by game-tree evaluation
• Communication complexity, hashing, and the communication complexity of Equality (with lower bound to follow)
• The rank bound in communication complexity: brief coverage in class, to be followed up by students' reading from Arora's lecture
• Perfect hashing: just the existence of small perfect-hash families via the probabilistic method, and the importance of explicit constructions
• Reading: the web-pages linked to above

• Hashing and random permutations/orientations (a method with surprisingly many applications) and the basic color-coding idea
• Quick recap of finite fields, and basic properties of polynomials over fields
• The Schwartz-Zippel/DeMillo-Lipton Lemma: proof and applications to polynomial identity testing and detecting perfect matchings; see also Dick Lipton's interesting blog-post on the Lemma's history
• Reading and Videos: the web-pages linked to above, and Noga Alon's video on color coding

• Variance and risk (and why the "first moment" alone is often insufficient), covariance, the Chebyshev and Chebyshev-Cantelli inequalities
• The kth moment method, k-wise independence, and universal hashing
• The Chernoff-Hoeffding bounds and applications in balls-and-bins
• Mid-term review
• Reading and Videos: Notes distributed by Aravind, and Charles Leiserson's two lectures on hashing

• Network flows: definition and motivations, edge-based and path-based formulations, Ford-Fulkerson algorithm
• Reading: Chandra Chekuri's two slide-decks

• Review: flows in undirected vs. directed graphs, residual graphs and augmenting paths, Ford-Fulkerson, integrality of flows in the case of integer capacities
• The Max-Flow Min-Cut Theorem
• The Scaling Max-Flow Algorithm
• Runtime bounds alone of the Edmonds-Karp strongly-polynomial algorithm and Orlin's recent breakthrough (see Andrew Goldberg's blog post for interesting history)
• Applications of max-flow min-cut and integrality:
  • Matrix rounding to preserve row- and column- sums
  • Efficient algorithm for bipartite matching
  • Hall's Theorem
• Reading: Kevin Wayne's two slide-decks

• Further applications/extensions of network flow:
  • single-commodity edge-disjoint paths
  • brief coverage of: network connectivity, Menger's Theorem, circulation (Hoffman's condition and recent application to the asymmetric TSP), min-cost flow, and Tardos' strongly-polynomial-time algorithm
• Matching -- theory and algorithms:
  • the continuing role played by matching in the development of many different algorithmic paradigms
  • Tutte-Berge formula
  • alternating and augmenting paths
  • equivalence of optimality and non-existence of augmenting paths
  • brief description of the Hopcroft-Karp algorithm for the bipartite case
  • start the Isolating Lemma
• Reading: Kevin Wayne's slides and Chandra Chekuri's notes

• Complete the Isolating Lemma; NC, RNC, and a very brief look at P-completeness; bipartite matching in RNC
• Linear programming:
  • Motivating example, packing formulation, equivalent definitions, vertices and their convex hull, optimality at a vertex
  • Weak and strong duality, start proof of strong duality ("objective vector is in the cone of the tight constraints")

• Linear programming:
  • Proof of strong duality: objective vector is in the cone of the tight constraints (see the nice and informal "physics proof" due to Vondrak for additional insight), complementary slackness, LP is in (NP intersection coNP)
  • Algorithms: high-level outline of the simplex-, ellipsoid-, and interior-point- methods, separation oracles and the ellipsoid method, convex optimization
  • Brief discussion of smoothed analysis of algorithms, with Simplex in mind
  • Diameter of polytopes, the Hirsch conjecture, and the possibility of strongly-polynomial algorithms
  • Integer programming: examples and NP-hardness
  • The polyhedral approach to combinatorial optimization:
    • The basic approach and negative results (in brief) for linear characterizations of the TSP
    • Polynomial-time solvability often characterized by nice polytopes; basic integrality theorem for the bipartite-matching polytope
  • Reading: Vondrak's Lecture 2

• Proof of the integrality theorem for the bipartite-matching polytope, and consequences for weighted bipartite matching
• Vertex-cover, matching, and Konig's Theorem
• 2-approximation algorithms for vertex cover:
  • Unweighted vertex cover: from maximal matchings
  • Weighted vertex cover: via LP-rounding and through the primal-dual method
• Reading: Vondrak's Lecture 2 and Section 2 of Shmoys' survey

• Recap of LP: duality, geometry, integrality
• Totally unimodular matrices and their applications
• The randomized rounding philosophy, congestion minimization, and relation to balls-and-bins
• Start the approximation of set cover by the method of alteration
• Reading: The page linked to above, and notes on rounding that were distributed by Aravind

• The method of alteration
• Randomized rounding plus alteration and scaling: unweighted set cover and edge-disjoint paths
• Reading: Aravind's paper for set cover; up to Lemma 2 of Schmidt-Siegel-Srinivasan for the disjoint-paths analysis

• More examples of poly-time solvability explained by LP: shortest paths (with negative edge-lengths allowed, but no negative cycles) and dependent rounding for s-t min-cut
• The spherical symmetry of high-dimensional Gaussians, semidefinite programming, and the "high-dimensional dependent-rounding" of Goemans-Williamson
• High-level outline of the PCP Theorem and of Dinur's proof
• Reading and Video: The material linked to above, notes (on rounding) distributed by Aravind for s-t min-cut, Ryan O'Donnell's entertaining history of the PCP Theorem, and Irit Dinur's video

• A recap of Dinur's Theorem, and its application to the inapproximability of MAX-SAT
• Some approximability thresholds with examples: constant, logarithmic, linear; relative-error approximation means that vertex cover and independent set are very different here
• Khot's Unique-Games Conjecture and consequences for vertex cover and max-cut
• Data streams: a brief look at "classical" work, the need for randomization and approximation, start Alon-Matias-Szegedy
• Reading: The material linked to above

• Data streams and summarization:
  • Combining the mean and median to transform unbiased estimators to high-probability estimators; Alon-Matias-Szegedy's F_2 computation
  • Streaming and communication complexity; lower bound for estimating F_{infinity}^*
  • Models for data streams: time-series, cash register, strict turnstile, turnstile
  • The Count-Min Sketch and its applications to point queries in the strict turnstile model
• Reading: Alon-Matias-Szegedy and Muthukrishnan's book on streaming

• Fixed-parameter tractability:
  • Basic ("multiplicative f(k)") definition and example of vertex-cover
  • "Additive f(k)" definition and why it holds for vertex cover
  • Kernelization, and the statement alone of the equivalence of multiplicative and additive f(k) in the FPT context
  • Definition of treewidth and elimination orderings
  • SAT is fixed-parameter tractable for instances with the primal graph having bounded treewidth (without proof)
• Online algorithms:
  • Definition of competitive ratio, ski rental, and the analysis of Graham's algorithm for online load-balancing
  • Brief mention of ad auctions; the algorithm and result of Karp-Vazirani-Vazirani for online bipartite matching (without proof)
  • Possible problems with the definition of competitive analysis
• Reading: Karger's two lectures

• Local Search: the general paradigm and its advantages/disadvantages; stable configurations in Hopfield neural nets
• Big-data analysis and MapReduce:
  • A model for MapReduce and open-source implementations
  • The nuances and advantages of the model; what freedom it offers - and what is hidden from - the parallel programmer
  • MapReduce algorithms for frequency moments and minimum spanning tree
• Recap of the course
• Reading: Kevin Wayne's slides and Karloff-Suri-Vassilvitskii

Web Accessibility