Prof. Souvaine will cover Johnson's algorithm for All-Pairs Shortest Paths (APSP) and begin an informal intro to NP-completeness (up to defining reductions)
For the last 15 minutes, Rebecca Newman will talk about the intersection of Algorithms and Computational Biology.
Reading: for APSP, see
these notes starting at page 111,
and
this video starting around 43:20.
For NP, see
section 14.1 and 14.2 up to page 5 condensed / page 24 full notes.
Lecture 20: Tuesday, April 17
The Time Complexity of Prim's MST algorithm. Also, Single Source Shortest Path (SSSP).
Reading: The rest of section 11, and
section 12 (May not get to SSSP for DAGs in class, but it's easy and you should read it).
Monday, April 16 is a HOLIDAY
Lecture 19: Thursday, April 12
Minimum Spanning Trees: Intro, Kruskal's algorithm, and description of Prim's (not the time complexity)
Lecture 16: Thursday, March 29: Prof. Anselm Blumer
More dynamic programming (rod cutting, and an intro to optimal static BST)
Reading:
section 8.4 Optimal static BST will not be on the exam. You can read about it in CLRS chapter 15 and the
course notes, and you can watch this video.
Exam 2: Tuesday, March 27 (Material through Lecture 13.)
Please be 5-minutes early, if possible.
Please use the entire auditorium, and leave one empty seat between you and your neighbor on each side.
Recitation: Thursday, February 22 at 9:30AM (Monday Schedule)
Lecture 9: Tuesday, February 20
More IRVs (resuming at the hat-check problem). Division method for hashing. Open addressing. Brief description of Universal hashing and Perfect hashing.
Reading: Section 15
and section 13.2.
Universal and perfect hashing are not in the course notes and will not be on the exam. If interested see the textbook.
Exam 1: Thursday, February 15
Please be 5-minutes early, if possible.
Please use the entire auditorium, and leave one empty seat between you and your neighbor on each side.
Lecture 8: Tuesday, February 13
Intro to hashing / Chaining / Simple uniform hashing. Intro to expectation / IRVs.
Reading: Section 13.1 (the end, on "choosing hash functions", is FYI. However, CLRS Theorem 11.2 will be discussed in detail).
Section 15 (up to page 33 of full notes)
Recitation: Monday, February 12
Exam review.
Lecture 7: Thursday, February 8
Counting sort and Radix sort. And possibly Strassen's algorithm.