Algorithms Illuminated

Official blurb: In Algorithms Illuminated, Tim Roughgarden teaches the basics of algorithms in the most accessible way imaginable. This Omnibus Edition contains the complete text of Parts 1-4, with thorough coverage of asymptotic analysis, graph search and shortest paths, data structures, divide-and-conquer algorithms, greedy algorithms, dynamic programming, and NP-hard problems. Hundreds of worked examples, quizzes, and exercises, plus comprehensive online videos, help readers become better programmers; sharpen their analytical skills; learn to think algorithmically; acquire literacy with computer science's greatest hits; and ace their technical interviews.

Videos and additional resources: (Click on one of the following topics to expand.)

• Videos (Part 1)
  • Full playlist
  • 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)
  • Big-O Notation (Section 2.2)
  • Basic Examples (Section 2.3)
  • Big-Omega and Big-Theta Notation (Section 2.4)
  • Additional Examples (Section 2.5)
  • The Divide-and-Conquer 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)
  • Choosing a Good Pivot (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 Linear-Time Selection (Section 6.1)
  • Randomized Linear-Time Selection (Analysis) (Section 6.2)
  • Deterministic Linear-Time Selection (Section 6.3)
  • Deterministic Linear-Time Selection (Analysis), Part 1 (Section 6.4, part 1)
  • Deterministic Linear-Time 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)
  • Full playlist
  • 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)
  • Breadth-First Search (Section 8.2, Part 1)
  • BFS and Shortest Paths (Section 8.2, Part 2)
  • BFS and Undirected Connected Components (Section 8.3)
  • Depth-First 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:00-4: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:30-26: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 (Part 3)
  • Full playlist
  • Introduction to Greedy Algorithms (Section 13.1)
  • A Scheduling Problem (Section 13.2)
  • Developing a Greedy Algorithm (Section 13.3)
  • Scheduling: Correctness Proof (Part 1) (Section 13.4, Part 1)
  • Scheduling: Correctness Proof (Part 2) (Section 13.4, Part 2)
  • Scheduling: Correctness Proof (Part 3) (Section 13.4, Part 3)
  • Codes (Section 14.1)
  • Codes as Trees (Section 14.2)
  • Huffman's Greedy Algorithm (Part 1) (Section 14.3, Part 1)
  • Huffman's Greedy Algorithm (Part 2) (Section 14.3, Part 2)
  • Huffman's Algorithm: Correctness Proof (Part 1) (Section 14.4, Part 1)
  • Huffman's Algorithm: Correctness Proof (Part 2) (Section 14.4, Part 2)
  • Minimum Spanning Trees: Problem Definition (Section 15.1)
  • Prim's MST Algorithm (Section 15.2)
  • Speeding Up Prim's Algorithm via Heaps (Part 1) (Section 15.3, Part 1)
  • Speeding Up Prim's Algorithm via Heaps (Part 2) (Section 15.3, Part 2)
  • Prim's Algorithm: Correctness Proof (Part 1) (Section 15.4, Part 1) [Note: this video provides an alternative treatment to that in the book.]
  • Prim's Algorithm: Correctness Proof (Part 2) (Section 15.4, Part 2) [Note: this video provides an alternative treatment to that in the book.]
  • Kruskal's MST Algorithm (Section 15.5)
  • Speeding Up Kruskal's Algorithm via Union-Find (Part 1) (Section 15.6, Part 1)
  • Speeding Up Kruskal's Algorithm via Union-Find (Part 2) (Section 15.6, Part 2) [Note: this video provides an alternative treatment to that in the book.]
  • Lazy Unions (Section 15.6, Part 3) [Note: this video is closer to the union-find implementation in the book.]
  • Kruskal's Algorithm: Correctness Proof (Section 15.7) [Note: this video provides an alternative treatment to that in the book.]
  • Application: Single-Link Clustering (Section 15.8)
  • The Weighted Independent Set Problem (Section 16.1)
  • A Linear-Time Algorithm for WIS in Path Graphs (Part 1) (Section 16.2, Part 1)
  • A Linear-Time Algorithm for WIS in Path Graphs (Part 2) (Section 16.2, Part 2)
  • A Reconstruction Algorithm (Section 16.3)
  • Principles of Dynamic Programming (Section 16.4)
  • The Knapsack Problem (Part 1) (Section 16.5, Part 1)
  • The Knapsack Problem (Part 2) (Section 16.5, Part 2)
  • The Knapsack Problem (Part 3) (Section 16.5, Part 3)
  • Sequence Alignment (Part 1) (Section 17.1, Part 1)
  • Sequence Alignment (Part 2) (Section 17.1, Part 2)
  • Optimal Binary Search Trees (Part 1) (Section 17.2, Part 1)
  • Optimal Binary Search Trees (Part 2) (Section 17.2, Part 2)
  • Optimal Binary Search Trees (Part 3) (Section 17.2, Part 3)
  • Optimal Binary Search Trees (Part 4) (Section 17.2, Part 4)
  • Optimal Binary Search Trees (Part 5) (Section 17.2, Part 5)
  • Shortest Paths with Negative Edge Lengths (Section 18.1)
  • The Bellman-Ford Algorithm (Part 1) (Section 18.2, Part 1)
  • The Bellman-Ford Algorithm (Part 2) (Section 18.2, Part 2)
  • The Bellman-Ford Algorithm (Part 3) (Section 18.2, Part 3)
  • The Bellman-Ford Algorithm (Part 4) (Section 18.2, Part 4)
  • The All-Pairs Shortest Path Problem (Section 18.3)
  • The Floyd-Warshall Algorithm (Part 1) (Section 18.4, Part 1)
  • The Floyd-Warshall Algorithm (Part 2) (Section 18.4, Part 2)
• Videos (Part 4)
  • Full playlist
  • Overview and Prerequisites (Section 19.0)
  • MST vs. TSP: An Algorithmic Mystery (Section 19.1)
  • Possible Levels of Expertise (Section 19.2)
  • Easy and Hard Problems (Section 19.3)
  • Algorithmic Strategies for NP-Hard Problems (Section 19.4)
  • Proving NP-Hardness: A Simple Recipe (Section 19.5)
  • Rookie Mistakes (Section 19.6)
  • Makespan Minimization (Part 1) (Section 20.1, Part 1)
  • Makespan Minimization (Part 2) (Section 20.1, Part 2)
  • Maximum Coverage (Part 1) (Section 20.2, Part 1)
  • Maximum Coverage (Part 2) (Section 20.2, Part 2)
  • Influence Maximization (Part 1) (Section 20.3, Part 1)
  • Influence Maximization (Part 2) (Section 20.3, Part 2)
  • 2-OPT Heuristic for the TSP (Part 1) (Section 20.4, Part 1)
  • 2-OPT Heuristic for the TSP (Part 2) (Section 20.4, Part 2)
  • Principles of Local Search (Part 1) (Section 20.5, Part 1)
  • Principles of Local Search (Part 2) (Section 20.5, Part 2)
  • The Bellman-Held-Karp Dynamic Programming Algorithm for the TSP (Section 21.1, Part 1)
  • The Bellman-Held-Karp Dynamic Programming Algorithm for the TSP (Section 21.1, Part 2)
  • The Alon-Yuster-Zwick Color Coding Algorithm for Finding Long Paths (Section 21.2, Part 1)
  • The Alon-Yuster-Zwick Color Coding Algorithm for Finding Long Paths (Section 21.2, Part 2)
  • Problem-Specific Algorithms vs. Magic Boxes (Section 21.3)
  • Mixed Integer Programming (MIP) Solvers (Section 21.4)
  • Satisfiability (SAT) Solvers (Section 21.5)
  • Reductions Revisited (Section 22.1)
  • 3-SAT and the Cook-Levin Theorem (Section 22.2)
  • The Big Picture (Section 22.3)
  • Independent Set Is NP-Hard (Section 22.4)
  • Directed Hamiltonian Path Is NP-Hard (Section 22.5)
  • The TSP Is NP-Hard (Section 22.6)
  • Subset Sum Is NP-Hard (Section 22.7)
  • Amassing Evidence of Intractability (Section 23.1)
  • Decision, Search, and Optimization (Section 23.2)
  • NP: Problems with Easily Recognized Solutions (Section 23.3)
  • The P!=NP Conjecture (Section 23.4)
  • The Exponential Time Hypothesis (Section 23.5)
  • NP-Completeness (Section 23.6)
  • Repurposing Wireless Spectrum (Section 24.1)
  • Greedy Heuristics for Buying Back Licenses (Part 1) (Section 24.2, Part 1)
  • Greedy Heuristics for Buying Back Licenses (Part 2) (Section 24.2, Part 2)
  • Feasibility Checking (Part 1) (Section 24.3, Part 1)
  • Feasibility Checking (Part 2) (Section 24.3, Part 2)
  • Implementation as a Descending Clock Auction (Section 24.4)
  • The Final Outcome (Section 24.5)
  • A Field Guide to Algorithm Design (Epilogue)
• Videos (Bonus)
  • Karger's random contraction algorithm for graph cuts
    • Graphs and Minimum Cuts
    • Random Contraction Algorithm
    • Review of Conditional Probability
    • Analysis of the Random Contraction Algorithm
    • Counting Minimum Cuts
  • Red-black trees
    • Red-Black Trees: The Basics
    • Insertion in a Red-Black Tree
  • More on hashing
    • Universal Hash Functions: Motivation
    • Universal Hash Functions: Definition and Example
    • Hash Table Performance with Chaining
    • Hash Table Performance with Open Addressing
  • A Greedy Algorithm for Optimal Caching
  • More on minimum spanning trees
    • Proof of the Cut Property [See also Problem 15.7.]
    • State-of-the-Art and Open Questions
  • More on Clustering
  • State-of-the-art union-find implementations
    • Union-by-Rank
    • Analysis of Union-by-Rank
    • Path Compression
    • Path Compression: The Hopcroft-Ullman Analysis (Part 1)
    • Path Compression: The Hopcroft-Ullman Analysis (Part 2)
    • The Ackermann Function
    • Path Compression: Tarjan's Analysis (Part 1)
    • Path Compression: Tarjan's Analysis (Part 2)
  • More on the Bellman-Ford algorithm
    • A Space Optimization
    • Internet Routing (Part 1)
    • Internet Routing (Part 2)
  • More on all-pairs shortest paths
    • A Reweighting Technique
    • Johnson's Algorithm (Part 1)
    • Johnson's Algorithm (Part 2)
  • More on approximately correct heuristic algorithms
    • A Greedy Heuristic Algorithm for the Knapsack Problem (Part 1) (see also Problem 20.3 in AI Part 4)
    • A Greedy Heuristic Algorithm for the Knapsack Problem (Part 2) (see also Problem 20.3 in AI Part 4)
    • A Greedy Heuristic Algorithm for the Knapsack Problem (Part 3) (see also Problem 20.3 in AI Part 4)
    • A Dynamic Programming Heuristic Algorithm for the Knapsack Problem (Part 1) (see also Problem 20.11 in AI Part 4)
    • A Dynamic Programming Heuristic Algorithm for the Knapsack Problem (Part 2) (see also Problem 20.11 in AI Part 4)
    • A Dynamic Programming Heuristic Algorithm for the Knapsack Problem (Part 3) (see also Problem 20.11 in AI Part 4)
  • More on local search
    • Local Search for the Maximum Cut Problem (Part 1) (see also Problem 20.14 in AI Part 4)
    • Local Search for the Maximum Cut Problem (Part 2) (see also Problem 20.14 in AI Part 4)
    • Local Search for the 2-SAT Problem (Part 1)
    • Local Search for the 2-SAT Problem (Part 2)
    • Local Search for the 2-SAT Problem (Part 3)
  • More on ineffecient exact algorithms
    • The Vertex Cover Problem
    • Smarter Search for Vertex Cover (Part 1)
    • Smarter Search for Vertex Cover (Part 2)
  • The wider world of algorithms
    • Stable Matching
    • Matching, Flows, and Braess's Paradox
    • Linear Programming and Beyond
• Slides
  • Parts 1 and 2
  • Part 3
  • Part 4
• Discussion Forums and Errata
  • Algorithms Illuminated Discussion Forum
  • Please report errors for Part 1, Part 2, Part 3, and Part 4.
• 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(n-1)/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 10-element 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 divide-and-conquer algorithm from Section 3.2, rather than brute-force search.)
  • Programming Problem 5.6: QuickSort
    • Test case #1: This file contains 10 integers, representing a 10-element 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 median-of-3 as the pivot (not counting the comparisons used to compute the pivot).
    • Test case #2: This file contains 100 integers, representing a 100-element 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 median-of-3 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 median-of-3 is always chosen as the pivot?
  • Programming Problem 6.5: Randomized Linear-Time Selection
    • Test case #1: This file contains 10 integers, representing a 10-element array. What is the median (i.e., the 5th-smallest element)? (Solution: 5469.)
    • Test case #2: This file contains 100 integers, representing a 100-element array. What is the median (i.e., the 50th 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 linear-time 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 linear-time selection algorithms.
  • Programming Problem 8.10: Computing Strongly Connected Components
    • Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0
    • Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0
    • Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0
    • Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0
    • Test case #5: A 12-vertex 20-edge 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 shortest-path 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 shortest-path 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: 2-SUM
    • 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 one-line 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?
  • Programming Problem 13.4: Greedy Scheduling
    • Test case: (contributed by Jeremy Brown) This file contains a list of 12 jobs with weights and lengths. It has the format:
      [number_of_jobs]
      [job_1_weight] [job_1_length]
      [job_2_weight] [job_2_length]
      ...
      What is the weighted sum of completion times of the schedule output by the GreedyDiff and GreedyRatio algorithms? (Break ties in favor of jobs with larger weights.) (Answer: 68615 and 67247, respectively.)
    • Challenge data set: Repeat the previous problem with the set of 10000 jobs listed in this file.
  • Programming Problem 14.6: Huffman Codes
    • In this problem the file format is:
      [number_of_symbols]
      [weight of symbol #1]
      [weight of symbol #2]
      ...
      Test cases: (contributed by Rupendra Bandyopadhyay) For the 10- and 15-symbol problem instances described in test case #1 and test case #2, what is the minimum and maximum length of a codeword in the corresponding optimal prefix-free code? (Answer: 2 and 5 for test case #1, 3 and 6 for test case #2.)
    • Challenge data set: Repeat the previous problem with the 1000-symbol problem instance described in this file.
  • Programming Problem 15.9: Minimum Spanning Trees
    • In this problem the file format is:
      [number_of_vertices] [number_of_edges]
      [one_endpoint_of_edge_1] [other_endpoint_of_edge_1] [edge_1_cost]
      [one_endpoint_of_edge_2] [other_endpoint_of_edge_2] [edge_2_cost]
      ...
      Edge costs can be negative, and are not necessarily distinct.
      Test case: (contributed by Quentin Appleby) What is the cost of an MST in the graph described in this file? (Answer: 14)
    • Challenge data set: Repeat the previous problem for the graph described in this file. Which algorithm has a faster straightforward implementation, Prim's or Kruskal's algorithm? Which is faster, the heap-based implementation of Prim's algorithm or the union-find-based implementation of Kruskal's algorithm?
  • Programming Problem 16.6: Weighted Independent Set
    • In this problem, each file describes the weights of vertices in a path graph and has the format:
      [number_of_vertices_in_path_graph]
      [weight of first vertex]
      [weight of second vertex]
      ...
      Test case: (contributed by Logan Travis) What is the value of a maximum-weight independent set of the 10-vertex path graph described in this file, and which vertices belong to the MWIS? (Answer: 2617, and the vertices 2, 4, 7, and 10).
    • Challenge data set: Repeat the previous problem for the 1000-vertex path graph described in this file.
  • Programming Problem 16.7: Knapsack
    • In this problem, each file describes an instance of the knapsack problem and has the format:
      [knapsack_size][number_of_items]
      [value_1] [weight_1]
      [value_2] [weight_2]
      ...
      You can assume that all numbers are positive. You should assume that item weights and the knapsack capacity are integers.
      Test case: What is the value of an optimal solution to the knapsack instance described in this file? (Answer: 2493893)
    • Challenge data set: Repeat the previous problem for the knapsack instance described in this file. This instance is so big that the straightforward iterative implementation described in the book uses an infeasible amount of time and space. So you will have to be creative to compute an optimal solution. One idea is to go back to a recursive implementation, solving subproblems --- and, of course, caching the results to avoid redundant work --- only on an "as needed" basis. Also, be sure to think about appropriate data structures for storing and looking up solutions to subproblems.
  • Programming Problem 17.8: Sequence Alignment
    • This file describes an instance of the sequence alignment problem. The format of the file is:
      1st line: length of X and length of Y
      2nd line: gap cost and mismatch cost (the latter is the same for every pair of distinct symbols)
      3rd line: X sequence
      4th line: Y sequence
      (Answer: the NW score is 224.)
  • Programming Problem 17.8: Optimal Binary Search Trees
    • This file describes an instance of the optimal binary search tree problem. The format of the file is:
      1st line: number specifying the number n of keys
      2nd line: n frequencies as comma-separated integer values
      (Answer: the value of an optimal solution is 2780.)
  • Programming Problem 18.8: All-Pairs Shortest Paths
    • In this problem, each file describes a directed graph. The first line of the file indicates the number of vertices and edges, respectively. Each subsequent line describes an edge (the first two numbers are its tail and head, respectively) and its length (the third number). NOTE: edge lengths might be negative, and the graphs may or may not be negative cycles.
      Test cases: (contributed by Matt Davis) What is the shortest shortest path in the graphs decribed in this file and in this file? (I.e., the minimum, over choices of an origin s and a destination t, of a shortest s-t path in the graph.) (If the graph has a negative cycle, your algorithm should detect that fact.) (Answer: -2 and "contains a negative cycle," respectively.)
    • Challenge data set: Repeat the previous problem for the graphs described in the following files: graph #1, graph #2, graph #3, and graph #4.
  • Programming Problems 19.9, 20.15, 20.16, 21.14, and 21.15: The Traveling Salesman Problem
    • Input files have two possible formats.
      Format #1:
      [number_of_vertices] [number_of_edges]
      [one_endpoint_of_edge_1] [other_endpoint_of_edge_1] [edge_1_cost]
      [one_endpoint_of_edge_2] [other_endpoint_of_edge_2] [edge_2_cost]
      ...
      Format #2: (for Euclidean instances) The first line indicates the number of vertices. Each vertex is a point in the plane, and each subsequent line indicates the x- and y-coordinates of a single vertex. (The cost of the edge between two vertices is then the Eulidean distance between its endpoints.)
      Test case #1: This file describes the instance in Quiz 19.2 (in format #1). (Optimal tour cost: 13)
      Test case #2: This file describes the instance in Quiz 20.7 (in format #1). (Optimal tour cost: 23)
      Test case #3: (contributed by Eric Hulburd) This file describes an 8-vertex Euclidean instance (in format #2). (Optimal tour cost (rounded): 12.36)
      Challenge data set: (for exact computation by e.g. Bellman-Held-Karp or a MIP solver) This file describes a 25-vertex Euclidean instance (in format #2).
      Bigger challenge data sets: (e.g., to experiment with greedy heuristics or local search) Countless examples here.
  • Programming Problem 24.5: Graph Coloring (via SAT solvers)
    • MiniSAT (or see recent SAT competitions for many more solvers).
    • Test cases: (to test out your SAT solvers) The file format is
      [number_of_variables] [number_of_constraints]
      [first_literal_of_constraint_1][second_literal_of_constraint_1]
      [first_literal_of_constraint_2][second_literal_of_constraint_2]
      ...
      (Both test cases have exactly two literals in each constraint.) Each literal is described by a number denoting the variable and a "-" sign denoting logical "not". For example, the second line of the first test case file is "-16808 75250," which indicates the constraint "(not x_{16808}) or x_{75250}."
      Test case #1 (answer: satisfiable)
      Test case #2 (answer: unsatisfiable)
    • Challenge data sets (SAT): For challenging SAT instances, see recent SAT competitions.
    • Challenge data sets (graph coloring): Explore the benchmark instances here or derive a graph from the FCC Incentive Auction data here.
  • For additional test cases and to contribute your own, visit this GitHub repo.
• Mathematical Background
  • Lehman, Leighton, and Meyer, Mathematics for Computer Science (2018 version). See also the shorter 2004 version.
  • Wikibook on Discrete Probability
• Additional Links
  • A Second Course in Algorithms [a sequel course, on YouTube]
  • A Hungarian folk dance implementation of QuickSort (!)
  • The Oracle of (Kevin) Bacon
  • FCC Incentive Auction Data

The content above has been sourced from the book website of Professor Tim Roughgarden. 

I highly recommend accessing his personal website for additional high-quality learning resources.

Please note that I do not own the copyright to the content presented here.