home
COMP 160: Introduction to Algorithms (Fall 2017)
Links to within this page:
Fall 2017 remaining calendar (subject to change)
All remaining lectures are by Greg
Nov. 23  No class
 Nov. 28  Minimum spanning trees (intro and Kruskal's algorithm).
 Nov. 30  More MST (Prim's algorithm), and intro to singlesource shortest paths.
Homework 7 due (worth 2%)
 Dec. 05  A little more SSSP, and then some NPcompleteness
 Dec. 07  More on NPcompleteness if necessary, and some computational geometry.
Homework 8 due (worth 3%)
 Dec. 15  Exam 4 (graphs), and cumulative final (69pm, location TBD)
Fall 2017 lectures
Lecture 19: Tuesday, November 21
 Covered: strongly connected components.
 Reading:
section 10.4
 Note: I will look into revising the very end of the proof in the course notes. There's nothing wrong with it as is, but I might rephrase things to match how it concluded in class. I will also update the section on SCC in the summary PDF (this Wednesday).
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.
Spring 2017 lectures . We will probably follow roughly the same schedule in Fall'17.
Lecture 22, Thursday, April 27
Lecture 21, Tuesday, April 25
Lecture 20: Thursday, April 20
Lecture 19: Tuesday, April 18
 Minimum spanning trees: intro and Kruskal's algorithm. Also a short recap of SCC.
 Reading: section 11.1 and 11.2
Lecture 18: Thursday, April 13
 Greg covered topological sort, and strongly connected components (except for the second example and final recap of proof of correctness)
 Reading: section 10.3 and 10.4
Lecture 17: Tuesday, April 11
 Greg covered an intro to graphs, BFS, and DFS.
 Reading: section 10.1 and 10.2 (except the part on planar graphs)
Exam 3: Thursday, April 6
Lecture 16: Tuesday, April 4
 Prof. Blumer did a review for exam 3.
Lecture 15: Thursday, March 30
 Prof. Blumer covered more dynamic programming (LCS, LIS, rod cutting)
 Reading:
section 8
Lecture 14: Tuesday, March 28
 Prof. Blumer covered augmented trees, and introduced dynamic programming.
 Reading:
Sections 7 and 8.1
Exam 2: Thursday, March 16
Lecture 13: Thursday, March 9
 Prof. Blumer did a review for exam 2.
Lecture 12: Tuesday, March 7
Lecture 11: Thursday, March 2
 Prof. Blumer covered amortization.
 Reading:
Section 9.
There is no video for multipop and binary counter, but there is a video introducing amortization using array doubling.
Lecture 10: Tuesday, February 28
Lecture 9: Tuesday, February 21
 Prof. Blumer covered the rest of the notes on hashing (open addressing, etc).
 Reading:
Section 13.1. Also, see Theorems 11.1 and 11.2 in CLRS, which provide more detail than the course notes.
 You should practice IRVs in section 15. This will help for homework 5, and for the upcoming lecture on randomized selection and quicksort.
Exam 1: Thursday, February 16
Lecture 8: Tuesday, February 14
 Prof. Blumer covered intro to expectation, and hashing with chaining (including more details than what's in my course notes)
 Reading: Section 13.1 and
the beginning of section 15 are related.
You could also take a look at my old comp61
notes on probability. Not all of it has to do with this class though.
Lecture 7: canceled because of snow, but students are expected to learn about counting sort and radix sort.
 Greg posted a new video on counting sort and radix sort. The example used is better than the one from last semester.

Reading: Section 4.6
Lecture 6: Tuesday, February 7
Lecture 5: Thursday, February 2
 Greg covered: deterministic selection (medianfinding)
 Reading: section 5.1
Lecture 4: Tuesday, January 31
 Greg covered: the master method

Reading: Section 3.2 (and 3.3.d)
Lecture 3: Thursday, January 26
 Greg covered: more examples of solving recurrences by substitution
 Reading: Section 3.1
Lecture 2: Tuesday, January 24
 Prof. Blumer covered: bigO proofs, 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)
Lecture 1: Thursday, January 19
 Prof. Blumer covered: Intro, Insertion sort, and brief definition of bigO and Omega
 Reading: Section 4.1 and
the start of Section 2.