home
COMP 160: Introduction to Algorithms (Fall 2017)
Exam 4: Friday, December 15
Lecture 23, Thursday, December 7
 Greg covered: NPcompleteness 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 AllPairs Shortest Paths. Also an informal intro to NPcompleteness (up to defining reductions)
 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 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.
 Reading:
section 10.4
 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)
 Reading:
section 8.4
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.
 Reading:
Section 7
and
section 6.2
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.
 Reading:
Section 9 and
section 4.4.a
Lecture 11: Thursday, October 12
 Prof. Blumer covered amortization. (mainly array doubling)
 Reading:
Section 9.
Lecture 10: Tuesday, October 10
 Prof. Blumer covered: more IRVs (hatcheck 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
section 3.3.d
Lecture 6: Thursday, September 21
Lecture 5: Tuesday, September 19
 Greg covered: deterministic selection (medianfinding)
 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 bigO, then mergesort and its recurrence
 Reading:
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 bigO and Omega
 Reading: Section 4.1 and
the start of Section 2.