CS 277: Lecture Schedule
The schedule below lists the topic of each lecture, with links to relevant notes, slides, and lecture videos. "DPV" refers to Algorithms by Dasgupta, Papadimitriou, and Vazirani, while "GTG" refers to Data Structures and Algorithms in Python by Goodrich, Tamassia, and Goldwasser. All future lecture topics are subject to change, but exam dates are not.
Schedule
- Wed Jan 21
- Administrivia and Python overview
Material: Chapter 1 of GTG.
[Course Syllabus, slides, notebook, video]
- Fri Jan 23
- Lab 1: Python Review [video]
- Mon Jan 26
- Recursion
Material: Chapter 4 of GTG.
[slides, notebook, video]
- Homework 1 released.
- Wed Jan 28
- Asymptotics and Big O
Material: Chapter 3 of GTG and Chapter 1 of DPV.
[scribbles, video]
- Thu Jan 29
- Lab 1 due
- Fri Jan 23
- Lab 2: Recursion and Asymptotics [notebook, video]
- Mon Feb 2
- Divide and Conquer: Multiplication
Material: Section 2.1 of DPV.
- Wed Feb 4
- Analysis of Multiplication: Guess and Check (Induction)
Material:
- Thu Feb 5
- Lab 2 due
- Fri Feb 6
- Lab 3: Divide and Conquer I
- Mon Feb 9
- Mergesort
Material: Section 2.3 of DPV.
- Homework 1 due. Homework 2 released
- Wed Feb 11
- Binary Search and Recurrences
Material: Section 2.2 of DPV.
- Thu Feb 12
- Lab 3 due
- Fri Feb 13
- Lab 4: Divide and Conquer II
- Mon Feb 16
- Introduction to Graphs
Material: Section 3.1 of DPV.
- Wed Feb 18
- Introduction to Trees
Material:
- Thu Feb 19
- Lab 4 due
- Fri Feb 20
- Midterm Review
- Mon Feb 23
- Stacks and Depth First Search in Graphs
Material: Section 3.2 of DPV.
- Homework 2 due. Homework 3 released
- Wed Feb 25
- Properties of DFS
Material: Section 3.3 of DPV.
- Fri Feb 27
- Lab 5: Graphs, Trees, and Search
- Feb 26 - Mar 1
- Midterm 1: CBTF
- Mon Mar 2
- DFS: Directed Acyclic graphs, Topological sort
Material: Section 3.3 and 3.4 of DPV
- Wed Mar 4
- Queues and Breadth First Search
Material: Section 4.1 and 4.2 of DPV
- Thu Mar 5
- Lab 5 due
- Fri Mar 6
- Lab 6: DFS and BFS
- Mon Mar 9
- Shortest Paths and Dijkstra
Material: Section 4.3 and 4.4 of DPV
- Homework 3 due. Homework 4 released
- Wed Mar 11
- Data Structures: Heaps
Material: Section 4.5 of DPV.
- Thu Mar 12
- Lab 6 due
- Fri Mar 13
- Lab 7: Shortest Paths in Graphs
- Mar 14 - Mar 22
- Spring Break
- Mon Mar 23
- Data Structure: Binary Search Trees
Material: Section 11.1 of GTG.
- Wed Mar 25
- Tree Traversals.
Material: Section 8.4 of GTG.
- Thu Mar 26
- Lab 7 due
- Fri Mar 27
- Midterm Review
- Mon Mar 30
- Dynamic Programming: Longest Increasing subsequence.
Material: Section 6.1 and 6.2 of DPV
- Homework 4 due. Homework 5 released
- Wed Apr 1
- Dynamic Programming: All Pairs Shortest paths.
Material: Section 6.6 of DPV.
- Fri Apr 3
- Lab 8: Binary Search Trees and Tree traversals
- Apr 2 - Apr 5
- Midterm 2: CBTF
- Mon Apr 6
- Dynamic Programming: Edit Distance
Material: Section 6.3 of DPV.
- Wed Apr 8
- Dynamic Programming: Knapsack and Independent sets in Trees
Material: Section 6.4 and 6.7
- Thu Apr 9
- Lab 8 due
- Fri Apr 10
- Lab 9: Dynamic Programming
- Mon Apr 13
- Clustering: Introduction and examples
Material:
- Homework 5 due. Homework 6 released
- Wed Apr 15
- Clustering: Center-based, Density-based, spectral
Material:
- Thu Apr 16
- Lab 9 due
- Fri Apr 17
- Lab 10: Clustering
- Mon Apr 20
- Sampling: Introduction and Applications
Material:
- Wed Apr 22
- Sampling: Analysis, Considerations
Material:
- Thu Apr 23
- Lab 10 due
- Fri Apr 24
- Lab 11: Sampling
- Mon Apr 27
- Linear Programming: Introduction and Applications
Material: Section 7.1 of DPV
- Homework 6 due.
- Wed Apr 29
- Linear Programming: Modeling and Reductions
Material: Section 7.2 and 7.3
- Thu Apr 30
- Lab 11 due
- Fri May 1
- Lab: Linear Programming
- Mon May 4
- NP: Search and SAT
Material: Section 8.1 of DPV.
- Wed May 6
- NP: Completeness and Reductions
Material: Section 8.2 and 8.3 of DPV.
- May 8 - May 14
- Final Exam: CBTF