CS170: Algorithms & Suffering 📉

Welcome to my digital graveyard of Dynamic Programming and NP-Completeness. Since I have officially escaped Berkeley, here lies the archived discussion worksheets I stared at for hours before finally checking the solutions.

The Surviving Worksheets

Discussion 1: Asymptotics & Master Theorem
Warmup

Big-O, Big-Omega, Big-Theta. The last time the math actually made sense.

Discussion 2: Divide and Conquer
O(N log N)

Merge sort, Strassen's, and dividing your remaining sanity into two halves.

Discussion 3: Fast Fourier Transform (FFT)
Math

Roots of unity. I still don't know how polynomial multiplication works in O(N log N).

Discussion 4: Graph Traversal (DFS/BFS)
O(V+E)

Pre/post numbers, connected components, and topological sorting.

Discussion 5: Shortest Paths
Graphs

Dijkstra and Bellman-Ford. Negative edge weights are a personal attack.

Discussion 6: Minimum Spanning Trees
Greedy

Kruskal's, Prim's, and the Union-Find data structure.

Discussion 7: Dynamic Programming I
DP

Longest Increasing Subsequence, Edit Distance. The start of the darkest timeline.

Discussion 8: Dynamic Programming II
DP 2

Knapsack, Independent Sets on Trees. Writing recurrence relations and praying.

Discussion 9: Linear Programming
LP

Simplex, duality, and modeling everything as a system of inequalities.

Discussion 10: Network Flow
Flow

Ford-Fulkerson, Max-Flow Min-Cut. Bipartite matching saves the day.

Discussion 11: Zero-Sum Games
Games

Minimax theorem and playing rock-paper-scissors mathematically.

Discussion 12: NP-Completeness
NP

SAT, 3-SAT, Vertex Cover. Proof by intimidation: 'No one else can solve this either!'

Discussion 13: Reductions
Reduction

Reducing 3-Coloring to Sudoku so you don't have to write a real algorithm.

Discussion 14: Randomized Algos
Random

Approximation algorithms, hashing, and just rolling the dice to find a solution.

Discussion 1: Asymptotics & Master Theorem Warmup

Discussion 2: Divide and Conquer O(N log N)

Discussion 3: Fast Fourier Transform (FFT) Math

Discussion 4: Graph Traversal (DFS/BFS) O(V+E)

Discussion 5: Shortest Paths Graphs

Discussion 6: Minimum Spanning Trees Greedy

Discussion 7: Dynamic Programming I DP

Discussion 8: Dynamic Programming II DP 2

Discussion 9: Linear Programming LP

Discussion 10: Network Flow Flow

Discussion 11: Zero-Sum Games Games

Discussion 12: NP-Completeness NP

Discussion 13: Reductions Reduction

Discussion 14: Randomized Algos Random