home
COMP 160: Introduction to Algorithms: reading material
This page does not change much over time. It contains course notes and videos, as well as other useful information, organized by topic.
Course Topics (not necessarily in order of schedule)
 Things to review before starting this class
 bigO notation (required for all sections below)
 Recurrences (required for all sections below)
 Sorting
 Selection
 Binary search trees
 Augmenting data structures
 Dynamic programming
 Amortization
 Graph basics
 Minimum spanning trees
 Singlesource shortest paths
 Hashing
 NPhardness
 Indicator Random Variables (covered in this course because not all comp61 sections do it; required for Quicksort and Randomized Selection)
 Extra topics
Informal summary PDF
This PDF contains some brief informal descriptions of the course material. It's useful if you're looking for a quick summary, but it only complements the class notes, it does not replace them. If you spot any errors or particularly unclear descriptions, please let me know.
A note about videos
COMP160 was recorded on video in the Fall 2016 and Spring 2017 semesters.
The original clips are still available for now, but most units have edited versions (multiple files pieced together, nonessential student questions removed, notes on screen regarding clarifications and corrections, background noise reduced, some contrast improvements, camera zoomed on screen).
However, for some of these edited versions, my voice is sometimes a bit muffled because of the background noise elimination. Tufts Technology Services will try to fix this. As this gets done, the original clips will be removed.
You are not required to watch any of these videos, but most likely 99% of what we cover will be essentially the same, so they are a good resource if you miss a lecture or want to go over things again. Live lectures will be a little more interactive, although the necessary pace doesn't allow a whole lot of interaction.
If you want another video source, check out the
MIT open courseware video lectures for Intro to Algorithms, starring Charles Leiserson and Erik Demaine (from 2005).
This is entirely optional. They cover a few things that we don't, and vice versa.
Here is the
link
(which seems to have subtitles too).
You can also view or download the free videos (without subtitles) at the iTunes store by searching for "Introduction to Algorithms", or
here.
 Things to review before starting this class
 Geometric series (Zeno's paradox). See p.1147 in CLRS. And
xkcd 994 ... xkcd 1153 (don't forget to mouseover)
 Common functions: do a light review of pages 5359 in CLRS.

Proof by contrapositive and contradiction (see
this as well).
 Induction, recursion
 It will help to be familiar with graph representation and some basic properties of trees.
 From your data structures class, arrays, linked lists, queues.
 It will help to refresh on probability and expected values, enough that you will not be intimidated by indicator random variables (See section 15).
 bigO notation (aka Theta notation)
 Prerequisite knowledge: it helps to be familiar with common functions (see 1.2 above)
 Recurrences
 The recursion tree and substitution method
 Class notes:
full
slideshow
and
condensed (the beginning of these notes are tied to Mergesort)
 Video
 Slideshow with audio describing mergesort and setting up its recurrence. This is also done in the Fall'2016 video below. How to solve the recurrence is dealt with in the Spring 2017 video section below.
 Spring 2017:
 Edited: part 1
and part 2. (45 min. total)
 Original: (there is some background hissing, and audio isn't stereo, but I think my voice can be heard more easily than the edited video. Let me know what you think).
part 1,
part 2, and
part 3. (73 min. total). See also one
observation about part 2
 From Fall 2016 (unedited) : Fall 16 video 1 starting at 18:00.
Also, Fall 16 video 2 up to 21:00.
 MIT videos: Lecture 2 from 16:50 to 37:45 for substitution, and then to 48:35 for recursion trees.
 Book: chapter 4, p.8392
 Here is a link to Prof. Souvaine's math notes on bigO and recurrences.
 The Master method
 Class notes:
full slideshow and
condensed
 Video:
 Spring 2017:
 Edited: link. (47min). Note that it is titled "part 1", but in fact it is selfcontained. "Part 2" is just Strassen's algorithm, in section 3.3.d.
 Original:
Lecture 4, part 1 and
part 2. (55min. total, excluding Strassen). Also, see a couple of observations
here.
 From Fall 2016: Fall 16 video 2
from 21:00 until 1:01:00
 MIT videos: Lecture 2 from 48:35 to end.
 Book: chapter 4, p.9396, although more intuition can be gained by reading up to p99.
 Beyond comp160: the AkraBazzi method generalizes the master method.
 Examples of using recurrences; recursive algorithms. (parts be are not critical for exams)
 Divide and conquer, and binary search.
 MIT videos: Lecture 3 up to 13:00
 Book: chapter 4, p.6567
 Computing the power of a number
 MIT videos: Lecture 3 from 13:00 up to 17:40
 Computing Fibonacci numbers
 Matrix multiplication (Strassen's method)
 VLSI embedding
 MIT videos: Lecture 3 from 55:00 to end.
 Sorting
 Insertion sort (also serves as an informal prelude to bigO)
 Mergesort (also serves as a quick intro to recurrences)
 Class notes: see beginning of class notes in section 3.1
 For Fall 16 video: see section 3.1
 MIT videos: Lecture 1, 1:03:20 to end.
 Book: chapter 2, p.3038
 Heapsort
 Quicksort
 Introduction, intuition and general behavior
 Class notes:
full slideshow
and
condensed
 Video:
 Tufts Fall 2016
 MIT videos: Lecture 4, up to 50:00
 Book: chapter 7, p.170180.
 Hungarian folk dance Quicksort video.
 Analysis: expected running time of randomized algorithm
 Alternate analysis of expected running time
 Class notes:
full slideshow and
condensed
 Video
 Tufts Fall 2016. (about 18 minutes long)
 MIT videos: Lecture 4, from 50:00 to end.
 Book: problem 7.3 on p.187
 Lower bound for comparison model
 Counting sort and radix sort
 Class notes:
full slideshow and
condensed

Video:
 Tufts 2017: (uses a better example than the Fall 2016 video)
 Tufts Fall 2016: Fall 16 video 5 from 18:35,
and
Fall 16 video 5, part 2 (somewhat out of date now)
 MIT videos: Lecture 5, from 31:20 up to 1:04:00.
After that the video has a more detailed analysis of radix sort.
It is also in the book, but you are not required to cover this.
 Book: chapter 8, p.194199.
 Other
 Selection (aka order statistics; medianfinding)
 Deterministic algorithm
 Randomized algorithm
 Class notes:
full slideshow
and condensed
 Video:
 Tufts 2016:
 MIT videos: Lecture 6, up to 43:30
 Book: Chapter 9, p.215219. The end of the analysis on p.219 may differ from what is done in class.
 With all these randomized algorithms, you might want to know how to generate
a random number: xkcd 221
 Binary search trees
 Basics
 Building a BST randomly, average depth, and relation to Quicksort.
 Redblack trees (an example of dynamic balanced BST)
 Class notes:
full slideshow
and condensed
 The condensed notes are also offered in this
version where red nodes are shown as rectangles. This ought to be more convenient for printing in black and white.
 Video:
 Tufts, Fall 2016
 MIT videos: Lecture 10.
 Book: Chapter 13, p.308322. However, continuing to study the Delete operation would be great practice.
 Augmenting data structures
 Prerequisite knowledge: binary search trees (section 6 just above)
 Intro, dynamic rank queries and selection
 Class notes:
full slideshow
and condensed
 Video:
 Tufts
 MIT videos: Lecture 11, up to 36:00
 Book: Chapter 14, p.339347.
 Range counting (almost the same as dynamic rank queries)
 Interval trees
 Class notes:
full slideshow
and condensed
 Video
 Tufts:
 MIT videos: Lecture 11, from 36:00 to end.
 Book: Chapter 14, p.348353.
 Dynamic programming
 Counting paths
 Longest common subsequence
 Longest increasing subsequence
 Rod cutting
 Amortization
 Class notes:
full slideshow
and condensed (on array doubling).
 Extra notes, on multipop stack, and binary counter: full slideshow. There is no video for this material.

Video:
 Tufts, Fall 2016:
 Blooper from a malfunctioning clicker during a Fall'16 review session.
 MIT videos: Lecture 13. Note that a different potential is used, compared to the class notes.
 Book: Chapter 17.
 Graph basics
 Representation and types of graphs (and a little bit about planarity)
 Class notes:
full slideshow
and condensed
 Video
 Tufts
 Edited version: Intro
 Edited version: Planarity
(unless mentioned otherwise, this will not be exam material)
 Original content: Fall 16 video 14 until 31:30
 MIT videos: Lecture 16, up to 23:20.
 Book: Chapter 22, p.589592.
 Breadthfirst search (BFS) and depthfirst search (DFS)
 Topological sort
 Strongly connected components
 Class notes:
full slideshow
and condensed
 Video:
 Note: the SCC section in the summary PDF was updated on Nov. 22.
 Book: Chapter 22, p.615620.
 Minimum spanning trees
 Prerequisite knowledge: graph basics, familiarity with priority queues (e.g. heaps).
 Intro and properties
 Class notes:
full slideshow
and condensed
 Video:
 Tufts: Edited from Spring'17: Part 1, and
Part 2 (until 20:22, then Kruskal's algo begins)
 MIT videos: Lecture 16, from 23:20 up to 1:00:30.
 Book: Chapter 23, p.624629.
 Kruskal's algorithm
 Prim's algorithm
 Single source shortest paths
 Prerequisite knowledge: graph basics, familiarity with priority queues (e.g. heaps).
 General properties and relaxing edges
 BellmanFord algorithm
 Algorithm for DAGs
 Dijkstra's algorithm
 Class notes:
full slideshow
and
condensed
 Video
 Tufts
 MIT videos: Lecture 17, from 26:20 to 1:19:40. (the proof of correctness is far longer than what I require)
 Book: Chapter 24, p.658662.
 JavaScript demo by Kenji Ikeda.
 Hashing (basics)
 Intro, chaining, simple uniform hashing
 Class notes:
full slideshow
and condensed
 Video:
 Book: chapter 11, p.253259, 262263. Some analysis in the book will be skipped.
 Open addressing, linear and quadrating probing, double hashing, analysis with uniform hashing assumption.
 Recommended further reading: Universal hashing, Perfect hashing, Cuckoo hashing (and more about the
cuckoo mafia)
 NPhardness
 Intro
 Class notes:
full slideshow
and
condensed
 Fall 16 video 20 until 28:00
 Book: Chapter 34, p.10481053, and 10611069.
However, I introduce the topic more informally, for instance, without mentioning "languages".
 Examples of reductions
 Other
 Use your newfound knowledge to torment your friends.
 Here are two papers about wellknown video games that can be generalized to be really hard.
__1__
__2__
 Indicator Random Variables (required for sections 4.4 and 5.2)
 Class notes:
full slideshow
and condensed
 Fall 16 video 6, and
Fall 16 video 6 part 2
 Book: Chapter 5
 Examples
 The hat check problem.
 See course notes.
 Secondary links (not involving IRVs):
Link 2 and
link 3 calculate the probability
of an outcome for this problem.
 The hiring problem.
 See course notes, or this link.
Note that the second problem in this link, involving birthdays, is dealt with separately below.
 Harmonic series (related to the hiring problem).
 Finding local maxima in permutations.
 Jump to the 30:00 mark in this youtube video,
which is part of Harvard's
Stat 110 course. This part of the lecture lasts 9 minutes.
After that is an explanation of the St. Petersburg paradox which is fun to think about.
Here's the wiki on that.
 A birthday problem. (involves IRVs with 2 subscripts)
 The 2nd example in this
link
is a variant of our good old birthday problem. I discuss this and one more variant
here.
 A problem with balls and bins.
 See the second example in this link.
Evaluation of the expected value of each IRV is a bit more complicated in this example than in previous ones.
Note that the first example in this link is equivalent to the hat check problem. It deals with fixed points in permutations.
In a permutation of the integers 1...n, a fixed point occurs when integer k is placed at position k.
Extra topics
 Fibonacci heaps.
 Approximation algorithms.