CS 38: Introduction to Algorithms (Winter 2014)

Instructor: Chris Umans

• Udaya Ghai
• Zeyu Guo
• Albert Gural
• Kenneth Hung
• Chung Eun Kim
• Nicholas Schiefer
• Paul Zhang
• Xander Zheng

Ombudspeople: TBD

Office: Annenberg 311

Times: Tues/Thurs 10:30-11:55 in Annenberg 105

Office hours:

• Sundays (7-8) in Annenberg 107 (Xander)
• Sundays (8-9) in Annenberg 107 (Zeyu)
• Sundays (9-10) in Annenberg 107 (Paul)
• Mondays (3-4) in Annenberg 311 (Chris)
• Mondays (7-8) in Annenberg 105 (Kenneth)
• Mondays (8-9) in Annenberg 105 (Chung)
• Mondays (9-10) in Annenberg 106 (Nicholas/Albert)
• Mondays (10-11) in Annenberg 106 (Udaya)

Announcements:

• Graded material can be picked up from Diane Goodfellow in Annenberg 246. Have a wonderful summer!

Handouts:

• Syllabus (pdf)

Lecture Slides:

• Lecture 1: Introduction and motivation, worst case asymptotic analysis, stable matchings example, BFS (ppt, pdf) [p. 590-597]
• Lecture 2: BFS, DFS, topological sort, strongly-connected component decomposition, heaps and heapsort, sorting lower bound (ppt, pdf) [p. 597-615, 151-159, 191-194]
• Lecture 3-4: Greedy algorithms: Dijkstra's, coin-changing, job scheduling, MCST (Prim's and Kruskal's) (ppt, pdf) [p. 658-662, 414-427, 624-636]
• Lecture 5: Greedy algorithms: Dijkstra's (review), Huffman codes, data structures, Union-Find (ppt, pdf, Union-Find pdf) [p. 428-437, 414-427, 561-581]
• Lecture 6: Union-Find, potential function method of amortized analysis, Fibonacci heaps (ppt, pdf, Fibonacci pdf) [p. 459-463, 505-526]
• Lecture 7: Divide and Conquer algorithms: Mergesort, Quicksort with random pivot, selection with random pivot, deterministic selection, closest pair (ppt, pdf [p. 30-36, 180-184, 214-222, 1039-1044]
• Lecture 8: Divide and Conquer algorithms: the DFT and FFT, polynomial multiplication, polynomial division with remainder, integer multiplication (ppt, pdf) [p. 898-920]
• Lecture 9: Divide and Conquer algorithms: Strassen's matrix multiplication; Dynamic programming: weighted interval scheduling, knapsack, matrix-chain-multiplication (ppt, pdf) [p. 370-390]
• Lecture 10: Dynamic programming: longest common subsequence, edit distance, Bellman-Ford shortest paths (ppt, pdf) [p. 390-397, 651-655 ]
• Lecture 11: Dynamic programming: negative cycles, all-pairs-shortest-paths; network flow, min-flow-max-cut theorem, capacity-scaling algorithm (ppt, pdf) [p. 693-697, 708-727]
• Lecture 12: Network flow: shortest-augmenting paths, blocking-flows, improved analysis for unit-capacity simple graphs, bipartite matching (ppt, pdf) [p. 709-736 ]
• Lecture 13: Edge-disjoint paths, the Assignment Problem, Linear programming (ppt, pdf) [p.844-857]
• Lecture 14: Ditch Day!
• Lecture 15: Linear programming: simplex algorithm, duality (ppt, pdf) [p.]
• Lecture 16: Linear programming: strong duality, ellipsoid algorithm; review of NP-completeness (ppt, pdf) [p.]
• Lecture 17: Coping with intractability: special cases, fixed-parameter algorithms, approximation algorithms for VC, Knapsack (ppt, pdf) [p.]
• Lecture 18: Coping with intractability: approximation algorithms for Set Cover, TSP, center selection; randomness in algorithms (ppt, pdf) [p.]
• Lecture 19: Randomness: 8/7 approximation for max-3-sat, universal hashing, Chernoff bounds and load balancing (ppt, pdf) [p.]
• Lecture 20: Topics: property testing, streaming algorithms, semidefinite programming (SDP) and approximation (ppt, pdf, streaming pdf, sdp pdf)

Problem Sets and Exams:

• Problem set 1: (pdf, LaTeX source) Solutions (pdf) (pts:27; mean:22.1; median:24; stddev:3.6)
• Problem set 2: (pdf, LaTeX source) Solutions (pdf) (pts: 30; mean: 25.3; median: 26; stddev: 3.74)
• Problem set 3: (pdf, LaTeX source) Solutions (pdf) (pts: 21; mean: 18.9; median: 19; stddev: 1.83)
• Midterm: (pdf, LaTeX source) Solutions (pdf) (pts: 24; mean: 21.4; median: 22; stddev: 2.76)
• Problem set 4: (pdf, LaTeX source) Solutions (pdf) (pts: 24; mean: 20.7; median: 21.5; stddev: 2.85)
• Problem set 5: (pdf, LaTeX source) Solutions (pdf) (pts: 18; mean: 15.8; median: 16.5; stddev: 2.18)
• Problem set 6: (pdf, LaTeX source) Solutions (pdf) (pts: 15; mean: 13.8; median: 14; stddev: 1.27)
• Problem set 7: (pdf, LaTeX source) Solutions (pdf) (pts: 15; mean: 14.0; median: 14; stddev: 1.29)
• Final: (pdf, LaTeX source) Solutions (pdf) (pts: 15; mean: 12.3; median: 13; stddev: 2.38)