Schedule

Please keep in mind that this is very preliminary and is likely going to change.

Day Date Topics Covered Notes and Readings
Tue Jan 17 Lecture 1: Overview of 15-210 and Cost Models lecture notes
Wed Jan 18 Recitation 1 - Parenthesis matching — Assignment 1 out recitation notes
Thu Jan 19 Lecture 2: Divide-and-Conquer I: Recurrences lecture notes
Tue Jan 24 Lecture 3: Divide-and-Conquer II: MCSS and The Substitution Method draft notes
Wed Jan 25 Recitation 2 - Recurrences and Scan — Assignment 1 due recitation notes
Thu Jan 26 Lecture 4: ADT, Reduce and Scan — Assignment 2 out lecture notes
Tue Jan 31 Lecture 5: More Sequences lecture notes
Wed Feb 01 Recitation 3 - More Scan - animation ppt recitation notes
Thu Feb 02 Lecture 6: Reduction: Use A to Solve B lecture notes
Tue Feb 07 Lecture 7: Graph Representations, Sets, and Tables
— Assignment 2 due; Assignment 3 out
lecture notes
Wed Feb 08 Recitation 4 - Reduction, MapCollectReduce, Graphs recitation notes
Thu Feb 09 Lecture 8: Breadth-First Search lecture notes
Tue Feb 14 Lecture 9: Depth-First Search; Assignment 4 out lecture notes
Wed Feb 15 Recitation 5 - DFS vs BFS, Topological Sort, Staging recitation notes
Thu Feb 16 Lecture 10: Weighted Shortest Paths; Assignmet 3 due draft notes
Tue Feb 21 Lecture 11: Dikjstra's and Bellman-Ford's SSSP Algorithms; Assignment 4 due lecture notes
Wed Feb 22 Recitation 6 - Midterm review
Thu Feb 23 Lecture 12: No Class; Midterm I at 7:30pm in Rashid
Tue Feb 28 Lecture 13: Probability and Randomized Algorithms lecture notes
Wed Feb 29 Recitation 7 - Exam I Debriefing — Assignment 5 out
Thu Mar 01 Lecture 14: Search Trees I: BSTs — Split and Join lecture notes
Tue Mar 06 Lecture 15: Search Trees II: Quicksort and Treaps lecture notes
Wed Mar 07 Recitation 8 - Probability and Treaps recitation notes
Thu Mar 08 Lecture 16: Search Trees III: Treaps and Ordered Sets; Assignment 5 due lecture notes
Tue Mar 13 Spring Break - No Class
Wed Mar 14 Spring Break - No Class
Thu Mar 15 Spring Break - No Class
Tue Mar 20 Lecture 17: Graph Contraction I: Tree Contraction; Assignment 6 out lecture notes
Wed Mar 21 Recitation 9 - Tree Contraction recitation notes
Thu Mar 22 Lecture 18: Graph Contraction II: Connectivity and MST lecture notes
Tue Mar 27 Lecture 19: Graph Contration III: Parallel MST and Maximal Independent Set; Assignment 6 due--and Assignment 7 out lecture notes
Wed Mar 28 Recitation 10 - Graph Contraction recitation notes
Thu Mar 29 Lecture 20: Leftist Heap lecture notes
Tue Apr 03 Lecture 21: Sorting Lower Bounds and How to Beat It lecture notes
Wed Apr 04 Recitation 11 - Exam Review
Thu Apr 05 Lecture 22: No Class: Midterm II at 7pm in WeH7500
Tue Apr 10 Lecture 23: Dynamic Programming I lecture notes
Wed Apr 11 Recitation 12 - Exam Debriefing and DP recitation
Thu Apr 12 Lecture 24: Dynamic Programming II---Assignment 8 out draft notes
Tue Apr 17 Lecture 25: Suffix Arrays lecture notes
Wed Apr 18 Recitation 13 - More DP Practice recitation notes
Thu Apr 19 Carnival - No Class
Tue Apr 24 Lecture 26: Hashing I; Assignment 8 due lecture notes
Wed Apr 25 Recitation 14 - Hashing and Suffix Arrays; Assignment 9 out
Thu Apr 26 Lecture 27: Hashing II draft notes