This schedule is tentative, and will be updated as the semester progresses.
- Topic: Class intro. Warmup with searching (linear and binary) and sorting (bubble sort, insertion sort, selection sort). Analysis: The RAM model. Asymptotic analysis and asymptotic notation. Case studies.
Notes: L-intro | ex-bubblesort | ex-selsort | L-analysis | ex-inssort | ex-analysis1 | ex-analysis2
- Slides: S-intro.pdf | S-asymptotic.pdf
- Reading Assignment: CLRS 1, 2, 3
- Lab: Lab1 (big-O)
- Topic: Summations and recurrence relations. Mergesort.
Notes: L-summations | ex-sum | L-recurrences | ex-rec1 | ex-rec2 | ex-rec3 | ex-rec4 | ex-rec1-sol
- Reading Assignment: CLRS A, 2.3, 4.4
- Lab: Lab2 (recurrences)
- Topic: More recurrences. Heaps and heapsort.
Notes: L-heaps | ex-heaps
- Slides: S-heaps.pdf
- Reading Assignment: CLRS 6
- Lab: Lab3 (heaps)
- Topic: Quicksort.
Sorting lower bound and sorting in linear time.
Notes: L-quicksort | ex-quicksort | L-sortlb | ex-linearsort | L-linsort
- Reading Assignment: CLRS 7, 8
- Lab: Lab4 (quicksort)
- Topic: Selection. Divide-and-conquer algorithms (Strassen, maximum sub-array)
Notes: L-selection| ex-selection | L-divideandconquer| ex-maxps
- Reading Assignment: CLRS 9, 4.1, 4.2
- Lab: Lab5 (selection)
- Topic: Dynamic programming.
Notes: L-dynprogr | ex-rod
- Reading Assignment: CLRS 15.1
- Lab: Lab6 (dynamic programming)
- Topic: Dynamic programming and greedy algorithms.
Notes: L-LCS | L-weightedinterval | L-greedy
- Reading Assignment: CLRS 15.4, 16.1, 16.2
- Lab: Lab7 (more dynamic programming and greedy)
- Topic: Graphs: BFS, DFS.
Notes: L-graphbasics | L-bfsdfs | L-basicproblems | L-kevinbacon
- Reading Assignment: CLRS 22.1 – 22.3
Internet: Lecture slides by Kevin Wayne: graphs-basics (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/03Graphs.pdf)
- Lab: Lab8 (graphs)
- Topic: Graphs: Topological sort. Strongly connected components.
Notes: L-topsort | L-scc
- Reading Assignment: CLRS 22.4, 22.5
- Lab: Lab9 (graphs)
- Topic: Graphs: Minimum spanning tree (Kruskal and Prim’s algorithms). Union-find structure.
- Reading Assignment: CLRS 23
Internet: Lecture slides greedy-algorithms (source:http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsII.pdf) | Kruskal demo demo-kruskal (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoKruskal.pdf) | Prim demo demo-prim (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoPrim.pdf) by Kevin Wayne.
- Lab: Lab10 (graphs)
- Topic: Graphs: Single-source shortest paths (Bellman-Ford and Dijkstra’s algorithms).
- Reading Assignment: CLRS 24.1-24.3
Dijkstra demo by Kevin Wayne demo-dijkstra (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04DemoDijkstra.pdf)
- Lab: Lab11 (graphs)
- Topic: Last class: Crash course into NP-completeness.
Questions from technical interviews.
- Reading Assignment: (CLRS 34)
Internet: Lecture slides by Kevin Wayne intractability (source: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf)
Exam 2 will be in-class, on (check final exam date in polaris).