Algorithms Illuminated (Parts 1-4)
by Tim Roughgarden · 2020
A comprehensive four-part series on algorithms: asymptotic notation and divide-and-conquer (Part 1), graph algorithms and data structures (Part 2), greedy algorithms and dynamic programming (Part 3), and NP-hard problems (Part 4).
193Extracted Problems
24Chapters
0Linked to DB
193Book Total
AlgorithmsDivide & ConquerGraphsDynamic ProgrammingNP-CompletenessTextbook
193 shown
- 1-1Derive recurrence for Karatsuba splitting into three partsDivide&ConquerMedium1-2Implement MergeSort and count inversions in a permutationDivide&ConquerSortingEasy1-3Prove by induction MergeSort sorts any array correctlySortingProofMedium1-4Analyze number of recursive calls in Karatsuba for n-digit inputDivide&ConquerMedium1-5Give O(n log n) algorithm for pairs (i<j) with a_i > 2*a_jDivide&ConquerCountingHard1-6Design O(n) algorithm to check valid merge of two sorted sequencesMergeArraysMedium1-7Prove Karatsuba works for n not a power of 2Divide&ConquerProofEasy1-8Problem 1.8Medium
- 2-1Prove f(n)=O(g(n)) implies g(n)=Omega(f(n))AsymptoticProofEasy2-2Determine if n^1.001+n log n = Theta(n^1.001) or Theta(n log n)AsymptoticMedium2-3Arrange by growth: n log n, n^2, 2^n, log n!, n^0.5, log^2 nAsymptoticEasy2-4Give f,g where f!=O(g) and g!=O(f) (incomparable)AsymptoticMedium2-5Prove/disprove: if f=O(g) and h=O(g) then f=O(h)AsymptoticProofMedium2-6Prove n! = O(n^n) and n! = omega(2^n)AsymptoticMathMedium2-7Show log(n!) = Theta(n log n) via StirlingAsymptoticMathHard2-8Prove master theorem case: T(n)=aT(n/b)+cn^k, a>b^k => T(n)=Theta(n^{log_b a})AsymptoticMasterMethodHard
- 3-1Implement D&C closest-pair and analyze running timeDivide&ConquerGeometryHard3-2Count post-sort inversions: pairs (i<j) with a_i < a_jDivide&ConquerSortingEasy3-3Generalize Strassen for 7x7 matrices - how many multiplications?Divide&ConquerMatrixHard3-4Design D&C max subarray sum in O(n log n)Divide&ConquerArraysMedium3-5Count significant inversions (a_i > 2*a_j) using modified merge sortDivide&ConquerCountingMedium3-6Show closest-pair works for Manhattan distanceDivide&ConquerGeometryMedium3-7Prove D&C closest-pair runs in O(n log n)Divide&ConquerGeometryMedium3-8Problem 3.8Medium
- 4-1Solve T(n)=9T(n/3)+n via master methodMasterMethodEasy4-2Solve T(n)=2T(n/2)+n log n via master methodMasterMethodEasy4-3Solve T(n)=T(2n/3)+1 - which algorithm?MasterMethodBinarySearchEasy4-4Solve T(n)=3T(n/4)+n log n - which case?MasterMethodMedium4-5Describe algorithm for each master theorem caseMasterMethodMedium4-6Prove master theorem case 1: T(n)=aT(n/b)+cn^k, a>b^k => T(n)=Theta(n^{log_b a})MasterMethodProofHard4-7Solve T(n)=2T(n/2)+n/log n - can master theorem apply?MasterMethodHard4-8Problem 4.8Medium
- 5-1Trace QuickSort on [4,1,3,5,2] with last-element pivotQuickSortSortingEasy5-2Expected comparisons for randomized QuickSort on length nQuickSortRandomizedMedium5-3Implement median-of-three pivot, analyze improvementQuickSortMedium5-4Design QuickSort variant with O(n log n) worst-caseQuickSortDivide&ConquerHard5-5Prove expected QuickSort comparisons is O(n log n)QuickSortRandomizedHard5-6Show QuickSort recursion depth O(log n) with high probabilityQuickSortRandomizedMedium5-7Implement 3-way partition QuickSort for duplicatesQuickSortSortingMedium5-8Problem 5.8Medium
- 6-1Trace RSelect finding 3rd smallest in [7,2,9,4,3,8,5]SelectionRandomizedEasy6-2Show DSelect recurrence solves to O(n)SelectionDivide&ConquerMedium6-3Prove median of medians is >=30% and <=70% of all elementsSelectionProofMedium6-4Implement DSelect with groups of 7, analyze recurrenceSelectionHard6-5Design algorithm for kth smallest in sorted matrixSelectionBinarySearchMedium6-6Given two sorted arrays, find median of union in O(log(min(m,n)))SelectionBinarySearchMedium6-7Prove RSelect runs in expected O(n) even with adversarial inputSelectionRandomizedHard6-8Problem 6.8Medium
- 7-1Represent directed graph with lists vs matrices - compare sparse/dense spaceGraphRepresentationEasy7-2Prove reachable vertices from source computed in O(V+E)GraphEasy7-3Design algorithm to check connectivity via BFS/DFSGraphConnectivityEasy7-4Compute transitive closure via Floyd-WarshallGraphClosureMedium7-5Problem 7.5Hard7-6Problem 7.6Easy7-7Problem 7.7Easy7-8Problem 7.8Medium
- 8-1Trace BFS on 7-vertex graph, find shortest paths from sBFSGraphEasy8-2Implement topological sort using DFS, detect cyclesDFSTopSortMedium8-3Run Kosaraju two-pass SCC on 8-vertex directed graphDFSSCCHard8-4Show reversing all DAG edges reverses topological orderDAGTopSortMedium8-5Design algorithm to count simple paths between two DAG verticesDAGDPMedium8-6Prove undirected graph has <=2 components after removing one vertexGraphConnectivityEasy8-7Prove every DAG has at least one source and one sinkDAGProofEasy8-8Problem 8.8Medium
- 9-1Trace Dijkstra on weighted 6-vertex graph from ADijkstraSSSPEasy9-2Prove Dijkstra correct for non-negative weightsDijkstraProofHard9-3Implement Dijkstra with heap, analyze O((E+V) log V)DijkstraHeapMedium9-4Construct counterexample where Dijkstra fails with negative weightsDijkstraCounterexampleEasy9-5Design Dijkstra variant for top-k shortest pathsDijkstraKShortestPathsHard9-6Prove Dijkstra processes vertices in non-decreasing distanceDijkstraProofMedium9-7Implement bidirectional Dijkstra from source and destinationDijkstraOptimizationMedium9-8Problem 9.8Medium
- 10-1Illustrate binary heap from array, perform extract-minHeapEasy10-2Prove BUILD-MAX-HEAP runs in O(n), not O(n log n)HeapProofMedium10-3Implement min-heap with decrease-key in O(log n)HeapMedium10-4Design d-ary heap, analyze insert/extract-min timesHeapMedium10-5Prove heap sort always O(n log n) regardless of inputHeapSortingEasy10-6Implement heap priority queue for Dijkstra, analyze speedupHeapDijkstraMedium10-7Find median of stream using two heapsHeapStreamingMedium10-8Problem 10.8Medium
- 11-1Insert into AVL tree, perform rotations to restore balanceTreeBSTEasy11-2Prove randomly built BST has O(log n) expected heightBSTRandomizedHard11-3Implement sorted set using balanced BST (AVL/RB)BSTTreeMedium11-4Show inorder traversal sequence of a BSTBSTTreeEasy11-5Design BST supporting split/join in O(log n)TreeBSTMedium11-6Prove AVL height <= 1.44*log2(n+2)-1.328TreeAVLHard11-7Find successor of element in BST in O(h)BSTTreeEasy11-8Problem 11.8Medium
- 12-1Show chaining for keys [10,22,31,4,15,28] in table size 7HashChainingEasy12-2Implement linear vs quadratic probing, compare clusteringHashOpenAddressingMedium12-3Design Bloom filter, compute false positive rate for k hashes, m bitsHashBloomFilterHard12-4Prove uniform hashing gives <=1/(1-alpha) expected unsuccessful probesHashProbabilityMedium12-5Design hash table with constant worst-case operations (perfect hashing)HashDesignHard12-6Show Cuckoo hashing insertion, prove expected O(1) amortizedHashCuckooHard12-7Problem 12.7Easy12-8Problem 12.8Medium
- 13-1Prove greedy min-max-lateness scheduling optimal via exchangeGreedySchedulingHard13-2Design greedy interval scheduling for max non-overlapping intervalsGreedySchedulingEasy13-3Find counterexample where greedy coin change failsGreedyCounterexampleEasy13-4Prove greedy fractional knapsack optimalGreedyKnapsackMedium13-5Design greedy minimum platforms for train schedulingGreedySchedulingMedium13-6Prove exchange lemma: swapping preserves feasibilityGreedyProofHard13-7Solve task scheduling with deadlines/profits using greedyGreedySchedulingMedium13-8Problem 13.8Medium
- 14-1Build Huffman tree for frequencies [a:45,b:13,c:12,d:16,e:9,f:5]GreedyHuffmanEasy14-2Prove Huffman optimal via exchange argument on treeGreedyHuffmanHard14-3Implement Huffman encode/decode for text fileGreedyHuffmanMedium14-4Show prefix-free condition equivalent to full binary treeGreedyHuffmanMedium14-5Generalize Huffman to ternary codes (alphabet size 3)GreedyHuffmanHard14-6Compute optimal bits for message from character frequenciesGreedyHuffmanEasy14-7Problem 14.7Easy14-8Problem 14.8Medium
- 15-1Trace Prim on weighted 6-vertex graph from AMSTPrimEasy15-2Run Kruskal on 7-vertex, 12-edge graphMSTKruskalEasy15-3Prove cut property: lightest crossing edge in every MSTMSTProofMedium15-4Implement union-find with path compression/union by rankUnionFindMSTMedium15-5Prove cycle property: heaviest cycle edge not in any MSTMSTProofMedium15-6Design max-spacing k-clustering using MSTMSTClusteringMedium15-7Show Prim with heap runs in O((E+V) log V)MSTPrimHard15-8Prove Kruskal correctness via cut propertyMSTKruskalMedium15-9Design second-best MST algorithmMSTHard
- 16-1Compute max-weight independent set in path [1,4,5,4] via DPDPGraphEasy16-2Solve 0/1 knapsack capacity 10 with given itemsDPKnapsackEasy16-3Prove optimal solution reconstruction from DP table correctDPProofMedium16-4Solve subset-sum: find subset summing to targetDPSubsetSumEasy16-5Design DP partition: equal-sum subsets?DPPartitionMedium16-6Solve unbounded knapsack (unlimited reuse) via DPDPKnapsackMedium16-7Prove weighted independent set DP has optimal substructureDPProofMedium16-8Problem 16.8Medium
- 17-1Compute edit distance kitten->sitting, show alignmentDPStringsEasy17-2Design DP for optimal BST given key probabilitiesDPBSTHard17-3Implement Kadane max-sum subarray, prove correctnessDPArraysEasy17-4Compute LCS of ABCBDAB and BDCABADPStringsEasy17-5Design DP for optimal convex polygon triangulationDPGeometryHard17-6Solve matrix chain multiplication [5,4,6,2,7]DPMatrixMedium17-7Design O(n log n) LIS DPDPLISMedium17-8Problem 17.8Medium
- 18-1Trace Bellman-Ford on 5-vertex graph with negative edgeBellmanFordSSSPEasy18-2Prove Bellman-Ford detects negative cycles from sourceBellmanFordNegCycleMedium18-3Run Floyd-Warshall on 4 vertices, show distance matricesFloydWarshallAPSPEasy18-4Prove Floyd-Warshall optimal substructureFloydWarshallProofMedium18-5Design O(n^2*2^n) DP for TSP using bitmaskDPTSPHard18-6Show all-pairs shortest path reduces to single-source caseAPSPSSSPMedium18-7Problem 18.7Easy18-8Problem 18.8Medium
- 19-1Why TSP believed harder than MST: decision vs optimization?NPTSPEasy19-2Prove: P=NP implies every NP problem solves in polynomial timeNPComplexityMedium19-3Show polynomial SAT solver implies P=NPNPSATHard19-4Classify: sorting, MST, max clique, 3-coloring, shortest path as P or NP-completeNPComplexityEasy19-5Define poly-time reducibility, show transitiveNPReductionMedium19-6Explain NP-hard vs NP-complete with examplesNPComplexityEasy19-7Problem 19.7Easy19-8Problem 19.8Medium
- 20-1Design 2-approximation for vertex cover, prove ratioApproximationVertexCoverMedium20-2Apply local search to max-cut: flip vertices to improveLocalSearchMaxCutMedium20-3Prove greedy set cover achieves O(log n) approximationApproximationSetCoverHard20-4Design 2-approximation for metric TSP via MST doublingApproximationTSPMedium20-5Show greedy max cut achieves >= half optimalApproximationMaxCutMedium20-6Prove MAX-3SAT not approximable within 7/8 unless P=NPApproximationPCPHard20-7Design factor-2 approximation for makespan on identical machinesApproximationSchedulingMedium20-8Problem 20.8Medium
- 21-1Design O(n^2*2^n) DP TSP, run on 5-vertex complete graphExactTSPHard21-2Apply color-coding for path of length k in O(2^k n^{O(1)})ExactColorCodingHard21-3Use inclusion-exclusion to count set covers in O(2^m poly(n))ExactSetCoverHard21-4Show 3-coloring in O(1.3289^n) via branch/boundExactGraphColoringHard21-5Design meet-in-the-middle SUBSET SUM O(2^{n/2})ExactSubsetSumMedium21-6Prove max independent set in O(1.618^n) via branchingExactBranchingHard21-7Show SAT in O(1.5^n) via DPLL with unit propagationExactSATMedium21-8Problem 21.8Medium
- 22-1Reduce 3SAT to INDEPENDENT SET via clause-variable gadgetNPReductionHard22-2Prove VERTEX COVER NP-complete from INDEPENDENT SETNPReductionMedium22-3Reduce SUBSET SUM to PARTITIONNPReductionMedium22-4Prove HAMILTONIAN CYCLE NP-complete from 3SATNPReductionHard22-5Show CLIQUE NP-complete from 3SATNPReductionMedium22-6Prove 3-COLOR NP-complete from 3SAT using OR-gadgetNPReductionHard22-7Reduce VERTEX COVER to DOMINATING SETNPReductionHard22-8Problem 22.8Medium
- 23-1Explain co-NP vs NP, give co-NP problem examplesComplexitycoNPMedium23-2Show NP != co-NP implies P != NPComplexityProofMedium23-3Define polynomial hierarchy PH, relation to P/NPComplexityPHHard23-4Prove SAT phase transition at clause/variable ratio ~4.26ComplexitySATHard23-5Overview of circuit complexity and P/poly classComplexityCircuitsMedium23-6Significance of Exponential Time Hypothesis for algorithm designComplexityETHMedium23-7Problem 23.7Easy23-8Problem 23.8Medium
- 24-1Describe FCC auction as optimization, identify NP-hard aspectsCaseStudyEasy24-2Design greedy approximation for spectrum allocationCaseStudyApproximationMedium24-3Why truthfulness matters in auction designCaseStudyMechanismDesignMedium24-4Show VCG mechanism applied to spectrum allocationCaseStudyMechanismDesignHard24-5Analyze complexity of VCG payments computationCaseStudyComplexityMedium24-6Problem 24.6Easy24-7Problem 24.7Easy24-8Problem 24.8Medium