Winda

Berkeley CS170: Efficient Algorithms and Intractable Problems

Contents · 38

  1. 01-IntroductionIntroduces CS 170’s goals and logistics, then explores the history of algorithms, big-O notation, and the running time of elementary integer addition and multiplication.
  2. 01-IntroductionIntroduces algorithms and their goals of correctness and efficiency, then examines arithmetic algorithms for adding and multiplying base-10 numbers.
  3. 02-Divide-and-Conquer (Part I)Karatsuba multiplication and its runtime analysis, formal Big-O and Ω notation, and recurrence relations.
  4. 02-Divide-and-Conquer (Part I)Introduces Fibonacci numbers to analyze arithmetic-operation counts, contrasting naive recursion with more efficient computation, and develops asymptotic notation and the master theorem for recurrence runtimes.
  5. 03-Divide-and-Conquer (Part II)Recurrences and the Master Theorem, plus matrix multiplication complexity and Strassen’s divide-and-conquer approach.
  6. 03-Divide-and-Conquer (Part II)Introduces the Master Theorem for analyzing divide-and-conquer runtimes, deriving total work from a recursion tree and relating it to multiplication algorithms.
  7. 04-Divide-and-Conquer (Part III)Randomized QuickSelect’s expected linear-time analysis using good pivots, plus the closest-pair problem as a divide-and-conquer example.
  8. 04-Divide-and-Conquer (Part III)Proves the Ω(n log n) lower bound for comparison-based sorting, then introduces divide-and-conquer selection and the fast Fourier transform.
  9. 05-Decomposition of GraphsCross-correlation computes shifted dot products and applies them to exact and approximate string matching, using fast polynomial multiplication and the FFT.
  10. 05-Decomposition of GraphsGraph definitions and representations, adjacency matrices and lists, DFS-based connectivity and connected components, runtime analysis, and DFS trees with pre/post visit times.
  11. 06-Paths in Graphs (Part I)DFS search trees, edge classification, cycle detection, topological sorting, and Kosaraju–Sharir’s algorithm for strongly connected components.DFS search trees, edge classification, cycle detection, topological sorting, and Kosaraju–Sharir’s algorithm for strongly connected components.
  12. 06-Paths in Graphs (Part I)Depth-first search, edge classification, directed cycles and DAGs, strongly connected components, and shortest paths by breadth-first search and edge weights.
  13. 07-Paths in Graphs (Part II)Shortest-path algorithms for unweighted, positive-weight, and negative-weight graphs, including BFS, Dijkstra’s algorithm, and Bellman–Ford.
  14. 07-Paths in Graphs (Part II)Shortest-path algorithms for unweighted graphs and graphs with nonnegative or negative edge lengths, including Dijkstra’s priority-queue approach.
  15. 08-Greedy (Part I)Greedy algorithm design and proof techniques, illustrated by optimal interval scheduling using earliest-finish-time selection. Includes runtime analysis and an inductive exchange argument.
  16. 08-Greedy (Part I)Defines minimum spanning trees, the greedy edge-selection strategy, and how connectivity, acyclicity, and edge count characterize trees.
  17. 09-Greedy (Part II)Huffman coding and its optimality, followed by Horn-SAT’s greedy algorithm and correctness proof.
  18. 09-Greedy (Part II)Greedy algorithms for deadline-based task scheduling, Huffman coding for compact data storage, and set cover approximation.
  19. 10-Greedy (Part III)Introduces greedy algorithms for minimum spanning trees, including tree and cut definitions, the cut property, and a general MST-building algorithm.
  20. 10-Greedy (Part III)Analyzes the greedy set cover algorithm, including its logarithmic approximation bound and a worst-case example.
  21. 11-Greedy Wrap-Up and Introduction to Dynamic ProgrammingIntroduces dynamic programming through Fibonacci memoization, top-down and bottom-up methods, and DAG-based computation, then applies it to shortest paths with negative edge weights.
  22. 11-Greedy Wrap-Up and Introduction to Dynamic ProgrammingAnalysis of union-find disjoint forests, including rank groups and charging arguments for bounding the amortized cost of find and union.
  23. 12-Dynamic Programming (Part II)Explains dynamic programming for all-pairs shortest paths with Floyd–Warshall and introduces longest increasing subsequences.
  24. 12-Dynamic Programming (Part II)Reconstructing optimal solutions from dynamic programming choices, illustrated with shortest paths in a DAG.
  25. 13-Dynamic Programming (Part III)Explains edit distance, knapsack with and without repetition, pseudo-polynomial time, and dynamic programming examples including TSP and tree independent sets.
  26. 13-Dynamic Programming (Part III)Introduces linear programming and matrix inequalities, using factory production constraints to illustrate feasible regions.
  27. 14-Dynamic Programming (Part IV)Dynamic programming for the Traveling Salesperson Problem, maximum independent sets in trees, and matrix-chain multiplication.
  28. 14-Dynamic Programming (Part IV)Simplex algorithm basics, linear programming duality, and finding feasible starting vertices and neighboring corners.
  29. 15-Linear ProgrammingLinear programming models and feasible regions, vertices, simplex, and polynomial-time algorithms.Linear programming models, feasible regions, vertices, simplex search, and polynomial-time algorithms.
  30. 15-Linear ProgrammingIntroduces the maximum-flow problem and Ford–Fulkerson, including flow constraints, residual graphs, augmenting paths, and cuts.
  31. 16-Network Flow + Bipartite MatchingDefines maximum flow in capacitated directed graphs, presents Ford–Fulkerson and residual graphs, proves the max-flow min-cut theorem, and discusses runtime.
  32. 16-Network Flow + Bipartite MatchingIntroduces zero-sum games through Rock, Paper, Scissors, explaining payoff matrices, player strategies, and how linear programming duality can identify optimal strategies.
  33. 17-Duality, Zero-Sum GamesBipartite perfect matching via max flow, linear programming duality and optimality certificates, and the connection between LP duality and zero-sum games.
  34. 17-Duality, Zero-Sum GamesIntroduces multiplicative weights and the Experts Problem, defining expert losses and the goal of minimizing cumulative loss over repeated decisions.
  35. 18-P vs NPDefines P and NP through polynomial-time solving and verification, with examples including graph 3-coloring and integer factorization.
  36. 18-P vs NPIntroduces problem reductions and their implications for algorithm speed and hardness, with examples including bipartite matching to max flow, polynomial-time problems to linear programming, and matrix inversion to matrix multiplication.
  37. 19-P vs NP (Part II)Introduces P and NP through coloring, factoring, and TSP; defines search, decision, and verification problems; and explains polynomial-time reductions with Hamiltonian-cycle and TSP examples.
  38. 19-P vs NP (Part II)Defines P and NP through polynomial-time solving and witness verification, and introduces reductions and the relations used to define NP-completeness.