Algorithms Illuminated is a DIY book series
by Tim Roughgarden,
inspired by online courses that are currently running on
the Coursera
and EdX
(Part 1/Part 2) platforms.
There are four volumes:
TOCs and sample sections:
Part 1;
Part 2;
Part 3;
Part 4.
Ordering info: Bookstores can order copies through Ingram. Individuals can order copies through Amazon (see links above).
Exam copies:
Instructors, book reviewers, and foreign publishers/translators can request an exam copy by contacting
the publisher at soundlikeyourselfpublishing@gmail.com.
Translations: Chinese (Posts & Telecom Press), Korean (Insight Publishing), Russian (Piter Publishing).
Stay updated:
Sign up for occasional email announcements about the book series, or follow algo_class on Twitter.
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)
 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)
 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)
 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 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)
 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)
 BreadthFirst 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 (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 UnionFind (Part 1)
(Section 15.6, Part 1)
 Speeding Up Kruskal's Algorithm via UnionFind (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 unionfind 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: SingleLink Clustering
(Section 15.8)
 The Weighted Independent Set Problem
(Section 16.1)
 A LinearTime Algorithm for WIS in Path Graphs (Part 1)
(Section 16.2, Part 1)
 A LinearTime 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 BellmanFord Algorithm (Part 1)
(Section 18.2, Part 1)
 The BellmanFord Algorithm (Part 2)
(Section 18.2, Part 2)
 The BellmanFord Algorithm (Part 3)
(Section 18.2, Part 3)
 The BellmanFord Algorithm (Part 4)
(Section 18.2, Part 4)
 The AllPairs Shortest Path Problem
(Section 18.3)
 The FloydWarshall Algorithm (Part 1)
(Section 18.4, Part 1)
 The FloydWarshall 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 NPHard Problems
(Section 19.4)
 Proving NPHardness: 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)
 2OPT Heuristic for the TSP (Part 1)
(Section 20.4, Part 1)
 2OPT 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 BellmanHeldKarp Dynamic Programming Algorithm for the TSP
(Section 21.1, Part 1)
 The BellmanHeldKarp Dynamic Programming Algorithm for the TSP
(Section 21.1, Part 2)
 The AlonYusterZwick Color Coding Algorithm for Finding Long Paths
(Section 21.2, Part 1)
 The AlonYusterZwick Color Coding Algorithm for Finding Long Paths
(Section 21.2, Part 2)
 ProblemSpecific 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)
 3SAT and the CookLevin Theorem
(Section 22.2)
 The Big Picture
(Section 22.3)
 Independent Set Is NPHard
(Section 22.4)
 Directed Hamiltonian Path Is NPHard
(Section 22.5)
 The TSP Is NPHard
(Section 22.6)
 Subset Sum Is NPHard
(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)
 NPCompleteness
(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
 Redblack trees
 More on hashing
 A Greedy Algorithm for Optimal Caching
 More on minimum spanning trees
 More on Clustering
 Stateoftheart unionfind implementations
 More on the BellmanFord algorithm
 More on allpairs shortest paths
 More on approximately correct heuristic algorithms
 More on local search
 More on ineffecient exact algorithms
 The wider world of algorithms
 Slides
 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 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 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?

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 15symbol 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 prefixfree 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 1000symbol 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 heapbased implementation of Prim's algorithm or the unionfindbased 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 maximumweight independent set of the 10vertex 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 1000vertex 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 commaseparated integer values
(Answer: the value of an optimal solution is 2780.)

Programming Problem 18.8: AllPairs 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 st 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 ycoordinates 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 8vertex Euclidean instance (in format #2). (Optimal tour cost (rounded): 12.36)
Challenge data set: (for exact computation by e.g. BellmanHeldKarp or a MIP solver) This file describes a 25vertex 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
 Additional Links