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)

  1. Things to review before starting this class
  2. big-O notation (required for all sections below)
  3. Recurrences (required for all sections below)
  4. Sorting
  5. Selection
  6. Binary search trees
  7. Augmenting data structures
  8. Dynamic programming
  9. Amortization
  10. Graph basics
  11. Minimum spanning trees
  12. Single-source shortest paths
  13. Hashing
  14. NP-hardness
  15. Indicator Random Variables (covered in this course because not all comp61 sections do it; required for Quicksort and Randomized Selection)

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, non-essential 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 I 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. There is no guarantee that what professor Blumer covers will match these videos or the corresponding course notes, but we will try to keep things consistent.

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.

  1. Things to review before starting this class
    1. Geometric series (Zeno's paradox). See p.1147 in CLRS. And xkcd 994 ... xkcd 1153 (don't forget to mouse-over)
    2. Common functions: do a light review of pages 53-59 in CLRS.
    3. A few things from COMP 61 such as proofs and induction, graph connectivity and trees.
    4. From your data structures class, arrays, linked lists, queues.
    5. It will help to refresh on probability and expected values, enough that you will not be intimidated by indicator random variables (See section 15).

  2. big-O notation (aka Theta notation)
    • Prerequisite knowledge: it helps to be familiar with common functions (see 1.2 above)

  3. Recurrences
    1. 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 video 1 starting at 18:00. Also, Fall 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.83-92
    2. 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 self-contained. "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 video 2 from 21:00 until 1:01:00
        • MIT videos: Lecture 2 from 48:35 to end.
      • Book: chapter 4, p.93-96, although more intuition can be gained by reading up to p99.
      • Beyond comp160: the Akra-Bazzi method generalizes the master method.
    3. Examples of using recurrences; recursive algorithms. (parts b-e are not critical for exams)
      1. Divide and conquer, and binary search.
        • MIT videos: Lecture 3 up to 13:00
        • Book: chapter 4, p.65-67
      2. Computing the power of a number
        • MIT videos: Lecture 3 from 13:00 up to 17:40
      3. Computing Fibonacci numbers
      4. Matrix multiplication (Strassen's method)
      5. VLSI embedding
        • MIT videos: Lecture 3 from 55:00 to end.

  4. Sorting
    1. Insertion sort (also serves as an informal prelude to big-O)
    2. Mergesort (also serves as a quick intro to recurrences)
      • Class notes: see beginning of class notes in section 3.1
      • For Fall video: see section 3.1
      • MIT videos: Lecture 1, 1:03:20 to end.
      • Book: chapter 2, p.30-38
    3. Heapsort
    4. Quicksort
      1. 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.170-180.
        • Hungarian folk dance Quicksort video.
      2. Analysis: expected running time of randomized algorithm
      3. Alternate analysis of expected running time
    5. Lower bound for comparison model
    6. 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 video 5 from 18:35, and Fall 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.194-199.
    7. Other

  5. Selection (aka order statistics; median-finding)
    1. Deterministic algorithm
    2. Randomized algorithm
      • Class notes: full slideshow and condensed
      • Video:
        • Tufts 2016:
        • MIT videos: Lecture 6, up to 43:30
      • Book: Chapter 9, p.215-219. 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

  6. Binary search trees
    1. Basics
    2. Building a BST randomly, average depth, and relation to Quicksort.
    3. Red-black trees (an example of dynamic balanced BST)

  7. Augmenting data structures
    • Prerequisite knowledge: binary search trees (section 6 just above)
    1. Intro, dynamic rank queries and selection
    2. Range counting (almost the same as dynamic rank queries)
    3. Interval trees

  8. Dynamic programming
    1. Counting paths
    2. Longest common subsequence
    3. Longest increasing subsequence
    4. Rod cutting

  9. 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.

  10. Graph basics
    1. 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 video 14 until 31:30
        • MIT videos: Lecture 16, up to 23:20.
      • Book: Chapter 22, p.589-592.
    2. Breadth-first search (BFS) and depth-first search (DFS)
    3. Topological sort
    4. Strongly connected components

  11. Minimum spanning trees
    • Prerequisite knowledge: graph basics, familiarity with priority queues (e.g. heaps).
    1. 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.624-629.
    2. Kruskal's algorithm
    3. Prim's algorithm

  12. Single source shortest paths
    • Prerequisite knowledge: graph basics, familiarity with priority queues (e.g. heaps).
    1. General properties and relaxing edges
    2. Bellman-Ford algorithm
    3. Algorithm for DAGs
    4. Dijkstra's algorithm

  13. Hashing (basics)
    1. Intro, chaining, simple uniform hashing
    2. Open addressing, linear and quadrating probing, double hashing, analysis with uniform hashing assumption.
    3. Recommended further reading: Universal hashing, Perfect hashing, Cuckoo hashing (and more about the cuckoo mafia)

  14. NP-hardness
    1. Intro
      • Class notes: full slideshow and condensed
      • Fall video 20 until 28:00
      • Book: Chapter 34, p.1048-1053, and 1061-1069. However, I introduce the topic more informally, for instance, without mentioning "languages".
    2. Examples of reductions
    3. Other
      • Use your new-found knowledge to torment your friends.
      • Here are two papers about well-known video games that can be generalized to be really hard. __1__ __2__

  15. Indicator Random Variables (required for sections 4.4 and 5.2)
    • Class notes: full slideshow and condensed
    • Fall video 6, and Fall video 6 part 2
    • Book: Chapter 5
    • Examples
      1. 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.
      2. 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).
      3. 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.
      4. 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.
      5. 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.