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.
Here's the the preface, table of contents for Part 1, and sample sections.
There are four volumes:
 Part 1: The Basics (published September 2017; second printing, July 2018)
 Part 2: Graph Algorithms and Data Structures (forthcoming in summer 2018)
 Part 3: Greedy Algorithms and Dynamic Programming (forthcoming in early 2019)
 Part 4: Algorithms for NPComplete Problems (forthcoming in late 2019)
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
 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)
 Discussion Forums
 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.
 Mathematical Background
 Additional Links