Exams
Quiz 1, on Mon 10/5
Quiz 2, on Mon 11/2
Quiz 3, on Mon 12/7
|
Homeworks
H1 LaTeX, out 09/09, due 09/16
H2 LaTeX, out 09/16, due 09/23
H3 LaTeX, out 09/23, due 09/30
H4 LaTeX, out 10/12, due 10/21
H5 LaTeX, out 10/21, due 10/28
H6 LaTeX, out 11/09, due 11/16
H7 LaTeX, out 11/16, due 11/23
|
Lecture Topics and Readings
Part 1: Foundations
- Lecture 1 (Wed Sep 02): Introduction. Insertion sort and analysis.
- -- CLRS: 1, 2.1, 2.2
- Lecture 2 (Mon Sep 07): Labor Day.
-- No class today, enjoy the holiday.
- Lecture 3 (Wed Sep 09): A better way to sort: Merge sort and analysis. Asymptotic notation.
- -- CLRS: 2.3, 3
- Lecture 4 (Mon Sep 14): Recurrences I.
- -- CLRS: 4
- Lecture 5 (Wed Sep 16): Recurrences II. Intro to probabilistic analysis.
- -- CLRS: 4
- Lecture 6 (Mon Sep 21): Probabilistic Analysis. Randomized algorithms.
- -- CLRS: 5
Part 2: Sorting and Order Statistics
- Lecture 7 (Wed Sep 23): Quicksort. Randomized Quicksort.
- -- CLRS: 7
- Lecture 8 (Mon Sep 28): Medians and order statistics.
- -- CLRS: 9.
- Lecture 9 (Wed Sep 30): Lower bounds for comparison-based sorting.
Beating the lower bound: counting sort.
- -- CLRS: 8.1, 8.2, 8.3, 8.4.
- Lecture 10 (Mon Oct 05): Quiz #1
- -- CLRS: everything covered so far.
Part 3: Advanced Design and Analysis Techniques
- Lecture 11 (Wed Oct 07): Dynamic Programming I. Rod Cutting.
- -- CLRS: 15.1, 15.2.
- Lecture 12 (Mon Oct 12): Dynamic Programming II. Longest Common Subsequence.
- -- CLRS: 15.3, 15.4.
- Lecture 13 (Wed Oct 14): Greedy Algorithms. Activity selection. Huffman Codes.
- -- CLRS: 16.1, 16.2, 16.3.
- Lecture 14 (Mon Oct 19): Algorithms Fall Break Day.
- -- No class today, enjoy the fall weather.
- Lecture 15 (Wed Oct 21): Amortized Analysis.
- -- CLRS: 17.1.
Part 4: Graph Algorithms
- Lecture 16 (Mon Oct 26): Graphs and their representations. BFS.
- -- CLRS: 22.1, 22.2.
- Lecture 17 (Wed Oct 28): DFS.
- -- CLRS: 22.3.
- Lecture 18 (Mon Nov 02): Quiz #2.
- -- CLRS: everything so far, emphasis on material since Quiz #1.
- Lecture 19 (Wed Nov 04): Topological sort. Minimum spanning trees. Kruskal and Prim's algorithms.
- -- CLRS: 22.4, 23.
- Lecture 20 (Mon Nov 09): Single-source shortest paths. The Bellman-Ford algorithm.
- -- CLRS: 24 (before 24.1), 24.1.
- Lecture 21 (Wed Nov 11): Dijkstra's algorithm.
- -- CLRS: 24.3.
- Lecture 22 (Mon Nov 16): All-pairs shortest paths.
- -- CLRS: 25.2, 25.3.
- Lecture 23 (Wed Nov 18): Maximum Flow. The Ford-Fulkerson algorithm.
- -- CLRS: 26.1, 26.2.
Part 5: Selected Topics
- Lecture 24 (Mon Nov 23): Introduction to the P vs. NP problem. NP-Completeness.
- -- CLRS: 34 (selections)
- -- slides: PDF
- Lecture 25 (Wed Nov 25): Thanksgiving Break.
- -- No class today, enjoy the holiday
- Lecture 26 (Mon Nov 30): Introduction to number theory and cryptography.
- -- CLRS: 31 (selections)
- -- slides: PDF
- Lecture 27 (Wed Dec 02): Interactive Proofs and Zero-Knowledge.
- Lecture 28 (Mon Dec 07): Quiz #3.
- -- CRLS: all material so far, emphasis on material since Quiz #2.
- -- This is the last day of classes.
|
