COMP 160: Introduction to Algorithms (Fall 2017)
Exam 4: Friday, December 15
Lecture 23, Thursday, December 7
- Greg covered: NP-completeness reductions. Constructing convex hulls.
- Reading: section 14. Nothing for convex hulls (see my comp163 page or ask me if interested)
Lecture 22, Tuesday, December 5
- Greg covered Johnson's algorithm for All-Pairs Shortest Paths. Also an informal intro to NP-completeness (up to defining reductions)
- Reading: for APSP, see
these notes starting at page 111,
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 21: Thursday, November 30
- Greg covered the time complexity of Prim's MST algorithm. Also, SSSP.
- Reading: The rest of section 11, and
section 12 (I didn't cover SSSP for DAGs in class, but it's easy and you should read it).
Lecture 20: Tuesday, November 28
Lecture 19: Tuesday, November 21
- Greg covered strongly connected components.
- Note: the section on SCC in the summary PDF was updated on Nov. 22.
Exam 3: Thursday, November 16
Lecture 18: Tuesday, November 14
Lecture 17: Thursday, November 9
- Prof. Blumer covered more dynamic programming (rod cutting, and an intro to optimal static BST)
Optimal static BST will not be on the exam. You can read about it in CLRS chapter 15 and my
course notes, and you can watch this video.
Tuesday, November 7: no class
Lecture 16: Thursday, November 2
Lecture 15: Tuesday, October 31
- Prof. Blumer covered augmented trees, and the relationship between random BSTs and Quicksort.
Exam 2: Thursday, October 26
Lecture 14: Tuesday, October 24
Lecture 13: Thursday, October 19
Lecture 12: Tuesday, October 17
- Prof. Blumer covered the binary counter problem (amortization), and an intro to Quicksort.
Section 9 and
Lecture 11: Thursday, October 12
- Prof. Blumer covered amortization. (mainly array doubling)
Lecture 10: Tuesday, October 10
- Prof. Blumer covered: more IRVs (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, October 5
Lecture 9: Tuesday, October 3
- Prof. Blumer covered: 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 was discussed in more detail).
Section 15 (up to page 33 of full notes)
Lecture 8: Thursday, September 28
- Greg did a bit of review. Class spent time solving problem 10 from the practice set.
Lecture 7: Tuesday, September 26
- Greg covered: counting sort and radix sort. Also, Strassen's algorithm (not exam material).
Reading: Section 4.6, and
Lecture 6: Thursday, September 21
Lecture 5: Tuesday, September 19
- Greg covered: deterministic selection (median-finding)
- Reading: section 5.1
Lecture 4: Thursday, September 14
- Greg covered: the last bit of recurrences by substitution, and the master method.
Reading: Section 3.1 and 3.2
Lecture 3: Tuesday, September 12
- Greg covered: solving recurrences by substitution
- Reading: Section 3.1 (all but the last two pages of the condensed pdf; or last 15 pages of full slideshow)
Lecture 2: Thursday, September 7
- Greg covered: more about big-O, then mergesort and its recurrence
All of Section 2,
Section 4.2, and the beginning of
Section 3.1 (up to determining the time complexity of mergesort with a tree)
Lecture 1: Tuesday, September 5
- Prof. Blumer covered: Intro, Insertion sort, and brief definition of big-O and Omega
- Reading: Section 4.1 and
the start of Section 2.