Algorithms Illuminated: Additional Resources
Algorithms Illuminated is a book series
by Tim Roughgarden,
based on online courses that are currently running on
the Coursera
and
Stanford Lagunita platforms.
There are four volumes:
Instructors can request an exam copy by contacting
the publisher at soundlikeyourselfpublishing@gmail.com.
This page offers several
resources to help you replicate as much of the online course
experience as you like.
(Click on one of the following topics to expand.)
 Videos (Part 1)
 Why Study Algorithms?
(Section 1.1)
 Integer Multiplication
(Section 1.2)
 Karatsuba Multiplication
(Section 1.3)
 MergeSort: Motivation and Example
(Section 1.4, part 1)
 MergeSort: Pseudocode
(Section 1.4, part 2)
 MergeSort: Analysis
(Section 1.5)
 Guiding Principles for the Analysis of Algorithms
(Section 1.6)
 Asymptotic Notation: The Gist
(Section 2.1)
 BigO Notation
(Section 2.2)
 Basic Examples
(Section 2.3)
 BigOmega and BigTheta Notation
(Section 2.4)
 Additional Examples
(Section 2.5)
 The DivideandConquer Paradigm
(Section 3.1; part 1 of Section 3.2)
 Counting Inversions in O(n log n) Time
(Section 3.2, part 2)
 Strassen's Matrix Multiplication Algorithm
(Section 3.3)
 An O(n log n)Time Algorithm for Closest Pair (Part 1)
(Section 3.4, part 1)
 An O(n log n)Time Algorithm for Closest Pair (Part 2)
(Section 3.4, part 2)
 Master Method: Motivation
(Section 4.1)
 Master Method: Formal Statement
(Section 4.2)
 Master Method: Six Examples
(Section 4.3)
 Proof of the Master Method (Part 1)
(Section 4.4, part 1)
 Master Method: Interpretation of the Three Cases
(Section 4.4, part 2)
 Proof of the Master Method (Part 2)
(Section 4.4, part 3)
 QuickSort: Overview
(Section 5.1)
 Partitioning Around a Pivot Element
(Section 5.2)
 The Importance of Good Pivots; Randomized QuickSort
(Sections 5.3 and 5.4)
 QuickSort Analysis (Part 1)
(Section 5.5, part 1)
 QuickSort Analysis (Part 2)
(Section 5.5, part 2)
 QuickSort Analysis (Part 3)
(Section 5.5, part 3)
 Sorting Requires Omega(n log n) Comparisons
(Section 5.6)
 Randomized LinearTime Selection
(Section 6.1)
 Randomized LinearTime Selection (Analysis)
(Section 6.2)
 Deterministic LinearTime Selection
(Section 6.3)
 Deterministic LinearTime Selection (Analysis), Part 1
(Section 6.4, part 1)
 Deterministic LinearTime Selection (Analysis), Part 2
(Section 6.4, part 2)
 Proofs by Induction and the Correctness of QuickSort
(Appendix A)
 Quick Review of Discrete Probability
(Appendix B)
 Videos (Part 2)
 Graphs: The Basics (from 2:06 to 6:39)
(Sections 7.1 and 7.2)
 Graph Representations
(Sections 7.3 and 7.4)
 Graph Search Overview
(Section 8.1)
 BreathFirst Search
(Section 8.2, Part 1)
 BFS and Shortest Paths
(Section 8.2, Part 2)
 BFS and Undirected Connected Components
(Section 8.3)
 DepthFirst Search
(Section 8.4)
 Topological Sort
(Section 8.5)
 Computing Strongly Connected Components (Part 1)
(Section 8.6, Part 1)
 Computing Strongly Connected Components (Part 2)
(Section 8.6, Part 2)
 The Structure of the Web
(Section 8.7)
 Shortest Paths and Dijkstra's Algorithm
(Sections 9.1 and 9.2, Part 1)
 Dijkstra's Algorithm: Examples
(Section 9.2, Part 2)
 Correctness of Dijkstra's Algorithm
(Section 9.3)
 Implementation and Running Time of Dijkstra's Algorithm (0:004:30)
(Section 9.4)
 Data Structures Overview
(Section 10.1)
 Heaps: Operations and Applications
(Sections 10.2 and 10.3)
 Speeding Up Dijkstra's Algorithm With Heaps (4:3026:27)
(Section 10.4)
 Heaps: Implementation Details
(Section 10.5)
 Balanced Search Trees: Operations and Applications
(Sections 11.1 and 11.2)
 Search Trees: Implementation Details (Part 1)
(Section 11.3, Part 1)
 Search Trees: Implementation Details (Part 2)
(Section 11.3, Part 2)
 Rotations
(Section 11.4)
 Hash Tables: Operations and Applications
(Sections 12.1 and 12.2)
 Hash Tables: Implementation (Part 1)
(Sections 12.3 and 12.4, Part 1)
 Hash Tables: Implementation (Part 2)
(Sections 12.3 and 12.4, Part 2)
 Hash Tables: Pathological Data Sets
(Section 12.3 and 12.4, Part 3)
 Bloom Filters: The Basics
(Section 12.5)
 Bloom Filters: Heuristic Analysis
(Section 12.6)
 Videos (Bonus)
 Karger's random contraction algorithm for graph cuts
 Redblack trees
 More on hashing
 Discussion Forums and Errata
 Test Cases and Data Sets for Programming Projects

General advice: use the small test
cases to help debug your program before tackling the challenge data set.

Programming Problem 1.6: Karatsuba multiplication
 Test cases:
For this problem, you can generate test cases just by plugging
numbers into a calculator. For example, 99,999 * 9,999 equals
999,890,001.
 Challenge problem: What is the product of
3141592653589793238462643383279502884197169399375105820974944592
and
2718281828459045235360287471352662497757247093699959574966967627?

Programming Problem 3.5: Counting inversions
 Sanity check: First, check that your algorithms counts 0
inversions for a sorted array, and n(n1)/2 inversions for a reverse
sorted array (e.g., 28 inversions for [ 8 7 6 5 4 3 2 1 ]).
 Test case:
This file contains 10
integers, representing a 10element array. Your program should count
28 inversions in this array.
 Challenge data set:
This file
contains all of the integers between 1 and 100,000
(inclusive) in some order, with no integer repeated.
The ith row of the file indicates the ith entry of
an array. How many inversions does this array have? (Obviously, to
get the most out of this assignment, you should implement the fast
divideandconquer algorithm from Section 3.2, rather than bruteforce search.)

Programming Problem 5.6: QuickSort
 Test case #1:
This file contains 10
integers, representing a 10element array. Your program should count
25 comparisons if you always use the first element as the pivot,
31 comparisons if you always use the last element as the pivot,
and 21 comparisons if you always use the medianof3 as the pivot (not counting the comparisons used to compute the pivot).
 Test case #2:
This file contains 100
integers, representing a 100element array. Your program should count
620 comparisons if you always use the first element as the pivot,
573 comparisons if you always use the last element as the pivot,
and 502 comparisons if you always use the medianof3 as the pivot (not counting the comparisons used to compute the pivot).
 Challenge data set:
This file
contains all of the integers between 1 and 10,000
(inclusive) in some order, with no integer repeated.
The ith row of the file indicates the ith entry of
an array. How many comparisons does QuickSort make on this input when the first element is always chosen as the pivot? If the last element is always chosen as the pivot? If the medianof3 is always chosen as the pivot?

Programming Problem 6.5: Randomized LinearTime Selection
 Test case #1:
This file contains 10
integers, representing a 10element array.
What is the median (i.e., the 5thsmallest element)?
(Solution: 5469.)
 Test case #2:
This file contains 100
integers, representing a 100element array.
What is the median (i.e., the 500th order statistic)? (Solution: 4715.)
 Challenge data set:
Form an array in which the first element is the first 10 digits of pi,
the second element is the next 10 digits of pi, and so on.
(The digits of pi are
available here.)
Make the array as big as you can (perhaps 100,000 elements, or 1 million
elements, or ...).
What is the median of the array?
[Aside: do you think this array has any duplicate
elements?]
 Bonus challenge: Implement the deterministic lineartime
selection algorithm from Section 6.3. For the challenge data set
above, compare the maximum array lengths solvable in a reasonable
amount of time (e.g., one hour) with the randomized and
deterministic lineartime selection algorithms.

Programming Problem 8.10: Computing Strongly Connected Components
 Test case #1: A 9vertex 11edge graph.
Top 5 SCC sizes: 3,3,3,0,0
 Test case #2: An 8vertex 14edge graph.
Top 5 SCC sizes: 3,3,2,0,0
 Test case #3: An 8vertex 9edge graph.
Top 5 SCC sizes: 3,3,1,1,0
 Test case #4: An 8vertex 11edge graph.
Top 5 SCC sizes: 7,1,0,0,0
 Test case #5: A 12vertex 20edge graph.
Top 5 SCC sizes: 6,3,2,1,0
 Challenge data set:
This file describes the edges of a directed graph. Vertices are
labeled as positive integers from 1 to 875714. Each row indicates one
edge of the graph (the tail and head vertices, in that order).
For example, the eleventh row ("2 13019")
indicates that there is an edge directed from vertex 2 to vertex 13019.
What are the sizes of the biggest five strongly connected components?

Programming Problems 9.8 and 10.8: Implementing Dijkstra's Algorithm
 Test case: This
file describes an undirected graph with 8 vertices (see below
for the file format). What are the shortestpath distances from
vertex 1 to every other vertex? (Answer, for vertices 1 through
8, in order: 0,1,2,3,4,4,3,2.)
 Challenge data set:
This file contains an adjacency
list representation of an undirected graph with 200 vertices
labeled 1 to 200. Each row indicates the edges incident to the given
vertex along with their (nonnegative) lengths.
For example, the sixth row has a "6" as its first entry indicating
that this row corresponds to vertex 6. The next entry of
this row "141,8200" indicates that there is an undirected edge between vertex 6
and vertex 141 that has length 8200. The rest of the pairs in this row
indicate the other vertices adjacent to vertex 6 and the lengths of
the corresponding edges. Vertex 1 is the starting vertex.
What are the shortestpath distances from vertex 1 to the following
ten vertices?: 7,37,59,82,99,115,133,165,188,197.

Programming Problem 11.3: The Median Maintenance Problem
 Test case: This file represents a stream of 10 numbers. What are the last 4 digits of the sum of the
kth medians? (See below for the definition of the kth median.) (Answer: 9335.)
 Challenge data set: This
file contains a list of the integers from 1 to 10000 in unsorted
order; you should treat this as a stream of numbers, arriving one by
one. By the kth median, we mean the median of the first k numbers in the stream (the
((k+1)/2)th smallest number among the first k if k is odd, the (k/2)th smallest if k is even).
What are the last 4 digits of the sum of the kth medians (with k going from 1 to 10000)?
Which data structure makes your algorithm faster: two heaps, or a search tree?

Programming Problem 12.4: 2SUM
 Test case: This file describes an array with 9 integers. For how many target values t in the interval [3,10] are there distinct numbers x,y in the input array such that x+y=t?
(Note: ensuring distinctness requires a oneline addition to the algorithm in Section 12.2.2.) (Answer: 8)
 Challenge data set:
This file contains one million
integers, both positive and negative (possibly with
repetitions!), with the ith row specifying the ith entry of the input array.
For how many target values t in the interval [10000,10000] are there distinct numbers x,y in the input array such that x+y=t?

For additional test cases and to contribute your own,
visit this GitHub repo.
 Mathematical Background
 Additional Links