Spring 2018 dates
Check this page 24 hours after each class (scroll down to the date) for suggested reading and links.
- Final Exam: Monday, May 7, 3-6pm
The exam consists of two parts:
- A part that focuses on the material covered since Exam 3
- A part that is comprehensive, covering the overall syllabus of Comp 160
- Recitation: Monday, April 30
Course review and problem Solving
- Lecture 23: Thursday, April 26, LAST CLASS
- Revisiting key topics in Comp 160 and adding additional depth and/or additional intuition (e.g. amortized analysis of red=black trees, augmented trees, problems that have polynomial algorithms and close cousins that are NP-hard).
- Reading: No new reading. Some handouts will be posted on Piazza either before or after class.
- Lecture 22: Tuesday, April 24
- Recitation: Monday, April 23
- Lecture 21: Thursday, April 19
- 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
- Exam 3: Tuesday, April 10
- 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: Monday, April 9
- Review of Lectures 17 and 18.
- Lecture 18: Thursday, April 5
- Strongly Connected Components.
- Reading:
section 10.4
- Note: the section on SCC in the summary PDF was updated on Nov. 22.
- Lecture 17: Tuesday, April 3
- Recitation: Monday, April 2
- Review of Lectures 14, 15, and 16.
- 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.
- Lecture 15: Monday, March 26: Prof. Anselm Blumer
- Lecture 14: Thursday, March 15: Prof. Anselm Blumer
- Augmented trees, and the relationship between random BSTs and Quicksort.
- Reading:
Section 7
and
section 6.2
- Snow Day: Tuesday, March 13
- Recitation: Monday, March 12
- Lecture 13: Thursday, March 8
- Intro to BSTs, and red-black trees.
- Reading:
Sections 6.1 and 6.3. Also read problem #17-4 on pages 474-75 in CLRS.
- Lecture 12: Tuesday, March 6
- Recitation: Monday, March 5
- Lecture 11: Thursday, March 1
- Lecture 10: Tuesday, February 27
- Amortization. (mainly array doubling)
- Reading:
Section 9.
- Recitation: Monday, February 26
- 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
- Lecture 7: Thursday, February 8
- Lecture 6: Tuesday, February 6
- Recitation: Monday, February 5
- Reviewed the selection algorithm
- Considered the problem of reporting in sorted order the sqrt(n) largest items from an unordered set of n items.
- Discussed three possible solutions to this problem.
- Lecture 5: Thursday, February 1
- Deterministic selection (median-finding)
- Reading: section 5.1
- Lecture 4: Tuesday, January 30
- The last bit of recurrences by substitution, and the master method.
-
Reading: Section 3.1 and 3.2
- Recitation: Monday, January 29
- Calculating the maximum of a set of n items
- Expanding recurrences
- Leading up intuitively to the Master Theorem
- Lecture 3: Thursday, January 25
- More recurrences by trees and substitution. Start the master method.
- Reading: Section 3.1 and possibly start Section 3.2.
- Lecture 2: Tuesday, January 23
- More big-O, then mergesort and its recurrence.
- Reading: All of Section 2 (Slides 35-72 of the full slideshow),
Section 4.2, and as much of
Section 3.1 as we can.
- Recitation: Monday, January 22
- Problems discussed posted in Piazza