Practice problems with hints and solutions · ProofAnvil Browsing still works.Sign in to use progress, saved problems and private labels. Problem search and previews remain available. Progress labels
IndependentSolved with helpIncorrect / unresolvedDraft in progressNot attemptedReview due
Problem results
ProblemCourse & topicStatus
Alg Insertion Sort Stable PrefixAlg Insertion Sort Comparison Shift Count
Correctness proofs and asymptotic complexityAlgorithms · Mixed review
—Alg Mergesort Inversion Cross CountAlg Mergesort Leftover Left Increment
Divide-and-conquer algorithmsAlgorithms · Mixed review
—Alg Quickselect Target Side OnlyAlg Quickselect Prescribed Pivot Count
Divide-and-conquer algorithmsAlgorithms · Mixed review
—Alg Karatsuba Three Product IdentityAlg Karatsuba Place Value Assembly
Divide-and-conquer algorithmsAlgorithms · Mixed review
—Alg Max Subarray Crossing OR KadaneAlg Max Subarray Nonempty Unique Block
Divide-and-conquer algorithmsAlgorithms · Mixed review
—Huffman Greedy Merge TraceHuffman Sibling Exchange Wpl
Greedy algorithms and exchange proofsAlgorithms · Mixed review
—Kruskal Component ScanMst Cut Property Safety
Greedy algorithms and exchange proofsAlgorithms · Mixed review
—Weighted Interval PredecessorDP Prefix Reconstruction
Dynamic programming and state designAlgorithms · Mixed review
—Zero One Knapsack TableKnapsack Take Skip Reconstruction
Dynamic programming and state designAlgorithms · Mixed review
—Matrix Chain Recurrence TableMatrix Chain Split Reconstruction
Dynamic programming and state designAlgorithms · Mixed review
—Dag Topo Longest PathUnreachable Minus Infinity Init
Graph optimization and traversal algorithmsAlgorithms · Mixed review
—Kosaraju Scc TraceStrong VS One Way Reachability
Graph optimization and traversal algorithmsAlgorithms · Mixed review
—Ford Fulkerson ResidualMaxflow Mincut Certificate
Graph optimization and traversal algorithmsAlgorithms · Mixed review
—3sat Independent Set ReductionComplementary Conflict Edges
Reductions, NP-completeness, and approximationAlgorithms · Mixed review
—Maximal Matching Vertex CoverApproximation Factor Two
Reductions, NP-completeness, and approximationAlgorithms · Mixed review
—ALG:9920001Mathematical problem title
Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Correctness ComplexityAlgorithms Problem Solving
Correctness proofs and asymptotic complexityAlgorithms · Calculation
—Showing 24 of 315 matching problems.
Strict greater-than keeps equal tagged keys in order; eight comparisons and six shifts sort the five-record array
A merge counts every leftover left key, so the seven-key array has thirteen inversions, not three
Quickselect on the nine-key array uses pivot 5 then pivot 7, compares eleven times, and returns 6
Karatsuba multiplies 1234 by 5678 with three base-100 products; 6164 is not the middle coefficient
The unique maximum subarray of the nine-key instance is the block 2 through 7 and sums to 11
Huffman merges the two lightest trees; largest-first and raw depth are not WPL
Kruskal accepts a lightest cut edge and rejects every intra-component edge
Weighted half-open intervals need a predecessor DP, not a cardinality exchange
The capacity-8 knapsack optimum is items 2 and 4; fractions and off-by-one cells are not 0/1
The unique minimum four-matrix product is (A1 A2)(A3 A4) at cost 405
A DAG longest s-t path is a topological max-DP with minus-infinity unreachable labels
Strong connectivity is mutual reachability: the SCCs of a chain of cycles form a path DAG
A feasible flow of 14 and the source cut of capacity 14 certify the max-flow min-cut value
3SAT reduces to Independent Set by clause triangles and complementary conflict edges
Both endpoints of a maximal matching 2-approximate Vertex Cover, tightly on a star
Let all logarithms have base 2, and let all functions have domain the positive integers.
Arrange the following functions into asymptotic equivalence classes, ordering the classes from smallest to largest…
Let f,g:\mathbb N→(0,∞). For each positive integer n, define… In the unit-cost RAM model, each execution of count = count + 1 costs one unit.
Consider the following code, where n≥2 is an integer and every arithmetic operation has unit cost: ```text count… Let popcount(n) denote the number of 1-bits in the ordinary base-2 representation of a positive integer n.
For a positive integer n, consider: ```text count = 0 for i = 1 to n: j = 1 while j <= n: count = count + 1 if j…
In the following code, ‘ceilsqrt(i)‘ returns \lceil\sqrt i⌉ in unit time.