Problem library

Find a problem

Search by course or topic.

Search problems

Area

AllMathPhysics

SubjectCourseTopic

Topic choices for Algorithms are shortened. Search still covers every problem.

More filters

StatusSkillProblem styleFind a private labelPrivate labelFavorites

Clear

Browsing still works.Sign in to add progress, saved problems and private labels.

Progress labels

IndependentSolved with helpIncorrect / unresolvedDraft in progressNot attemptedReview due

Problem results

ProblemsBuild a practice set

ALG:010117Strict greater-than keeps equal tagged keys in order; eight comparisons and six shifts sort the five-record array

View access options

Alg Insertion Sort Stable PrefixAlg Insertion Sort Comparison Shift Count

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Mixed review

Progress not loaded

ALG:010218A merge counts every leftover left key, so the seven-key array has thirteen inversions, not three

View access options

Alg Mergesort Inversion Cross CountAlg Mergesort Leftover Left Increment

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010219Quickselect on the nine-key array uses pivot 5 then pivot 7, compares eleven times, and returns 6

View access options

Alg Quickselect Target Side OnlyAlg Quickselect Prescribed Pivot Count

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010220Karatsuba multiplies 1234 by 5678 with three base-100 products; 6164 is not the middle coefficient

View access options

Alg Karatsuba Three Product IdentityAlg Karatsuba Place Value Assembly

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010221The unique maximum subarray of the nine-key instance is the block 2 through 7 and sums to 11

View access options

Alg Max Subarray Crossing OR KadaneAlg Max Subarray Nonempty Unique Block

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010322Huffman merges the two lightest trees; largest-first and raw depth are not WPL

View access options

Huffman Greedy Merge TraceHuffman Sibling Exchange Wpl

PrivateLabels unavailable

Private saving unavailable

Greedy algorithms and exchange proofsAlgorithms · Mixed review

Progress not loaded

ALG:010323Kruskal accepts a lightest cut edge and rejects every intra-component edge

View access options

Kruskal Component ScanMst Cut Property Safety

PrivateLabels unavailable

Private saving unavailable

Greedy algorithms and exchange proofsAlgorithms · Mixed review

Progress not loaded

ALG:010424Weighted half-open intervals need a predecessor DP, not a cardinality exchange

View access options

Weighted Interval PredecessorDP Prefix Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010425The capacity-8 knapsack optimum is items 2 and 4; fractions and off-by-one cells are not 0/1

View access options

Zero One Knapsack TableKnapsack Take Skip Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010426The unique minimum four-matrix product is (A1 A2)(A3 A4) at cost 405

View access options

Matrix Chain Recurrence TableMatrix Chain Split Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010527A DAG longest s-t path is a topological max-DP with minus-infinity unreachable labels

View access options

Dag Topo Longest PathUnreachable Minus Infinity Init

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010528Strong connectivity is mutual reachability: the SCCs of a chain of cycles form a path DAG

View access options

Kosaraju Scc TraceStrong VS One Way Reachability

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010529A feasible flow of 14 and the source cut of capacity 14 certify the max-flow min-cut value

View access options

Ford Fulkerson ResidualMaxflow Mincut Certificate

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:0106303SAT reduces to Independent Set by clause triangles and complementary conflict edges

View access options

3sat Independent Set ReductionComplementary Conflict Edges

PrivateLabels unavailable

Private saving unavailable

Reductions, NP-completeness, and approximationAlgorithms · Mixed review

Progress not loaded

ALG:010631Both endpoints of a maximal matching 2-approximate Vertex Cover, tightly on a star

View access options

Maximal Matching Vertex CoverApproximation Factor Two

PrivateLabels unavailable

Private saving unavailable

Reductions, NP-completeness, and approximationAlgorithms · Mixed review

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920011Let T(1)=1, and for every integer n\ge2, let Find an exact formula for T(n) when n is a power of 2.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920012Let T(n)=1 for integers 1\le n\le2, and for n\ge3, let Determine a tight asymptotic bound.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920013Let T(n)=1 for integers 0\le n\le1, and for n\ge2, let Determine a tight asymptotic bound.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920014Let T(n)=1 for integers 0\le n\le1, and for n\ge2, let Determine a tight asymptotic bound, proving explicit upper a…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920015Consider: ```text Split(n): if n == 1: perform one unit of local work return Split(floor(n/2)) Split(ceil(n/2)) per…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920016Two algorithms have running times defined on powers of 2 by and Derive exact closed forms, determine tight asymptot…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920017Consider insertion sort: ```text for j = 2 to n: key = A[j] i = j - 1 while i >= 1 and A[i] > key: A[i + 1] = A[i]…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920018Let A[1..n] be sorted in nondecreasing order, let x be a key, and consider: ```text lo = 1 hi = n + 1 while lo < hi…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920019For integers a\ge b\ge0, (a,b)\ne(0,0), consider Euclid's algorithm: ```text while b != 0: r = a mod b a = b b = r…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920020For a real number x and a nonnegative integer n, consider: ```text Pow(x, n): if n == 0: return 1 y = Pow(x, floor(…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920021Let A[1..p] and B[1..q] be nondecreasing arrays.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920022Let A[1..n] be an array and P a constant-time predicate.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920023An array A[1..n], n\ge2, contains distinct comparable keys.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920024Consider: ```text for i = 1 to n - 1: if A[i] > A[i + 1]: swap A[i] and A[i + 1] return A ``` Determine whether the…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920025Given an array A[1..n] of real numbers, n\ge1, design a divide-and-conquer algorithm returning the maximum sum of a…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920026Let n\ge1, k=\lceil\log_2(n+1)\rceil, and let `bits[0..k-1]` initially contain zeros, with index 0 least significant.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920027In the unit-cost RAM model, analyze the following code for independent positive integers n,m: ```text count = 0 for…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920028A randomized recursive procedure on input size n\ge1 performs exactly cn local work, where c>0, chooses K uniformly…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920029For an array A[1..n] of distinct comparable keys, an inversion is a pair (i,j) with i<j and A[i]>A[j].

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920030Given a nondecreasing integer array A[0..n-1] and an integer x, return the smallest and largest indices at which x…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920031An array A[0..n-1] was formed by cyclically rotating a strictly increasing array.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920032A bitonic array contains distinct numbers that strictly increase to one maximum and then strictly decrease; either…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920033A conceptually infinite array contains a finite strictly increasing sequence followed by infinitely many +\infty se…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920034Given nondecreasing arrays A,B of lengths m,n, and 1\le k\le m+n, return the k-th smallest element of their combine…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920035An array A[0..n-1] has pairwise distinct values.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Problem library

Find a problem

Search by course or topic.

Search problems

Area

AllMathPhysics

SubjectCourseTopic

Topic choices for Algorithms are shortened. Search still covers every problem.

More filters

StatusSkillProblem styleFind a private labelPrivate labelFavorites

Clear

Browsing still works.Sign in to add progress, saved problems and private labels.

Progress labels

IndependentSolved with helpIncorrect / unresolvedDraft in progressNot attemptedReview due

Problem results

ProblemsBuild a practice set

ALG:010117Strict greater-than keeps equal tagged keys in order; eight comparisons and six shifts sort the five-record array

View access options

Alg Insertion Sort Stable PrefixAlg Insertion Sort Comparison Shift Count

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Mixed review

Progress not loaded

ALG:010218A merge counts every leftover left key, so the seven-key array has thirteen inversions, not three

View access options

Alg Mergesort Inversion Cross CountAlg Mergesort Leftover Left Increment

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010219Quickselect on the nine-key array uses pivot 5 then pivot 7, compares eleven times, and returns 6

View access options

Alg Quickselect Target Side OnlyAlg Quickselect Prescribed Pivot Count

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010220Karatsuba multiplies 1234 by 5678 with three base-100 products; 6164 is not the middle coefficient

View access options

Alg Karatsuba Three Product IdentityAlg Karatsuba Place Value Assembly

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010221The unique maximum subarray of the nine-key instance is the block 2 through 7 and sums to 11

View access options

Alg Max Subarray Crossing OR KadaneAlg Max Subarray Nonempty Unique Block

PrivateLabels unavailable

Private saving unavailable

Divide-and-conquer algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010322Huffman merges the two lightest trees; largest-first and raw depth are not WPL

View access options

Huffman Greedy Merge TraceHuffman Sibling Exchange Wpl

PrivateLabels unavailable

Private saving unavailable

Greedy algorithms and exchange proofsAlgorithms · Mixed review

Progress not loaded

ALG:010323Kruskal accepts a lightest cut edge and rejects every intra-component edge

View access options

Kruskal Component ScanMst Cut Property Safety

PrivateLabels unavailable

Private saving unavailable

Greedy algorithms and exchange proofsAlgorithms · Mixed review

Progress not loaded

ALG:010424Weighted half-open intervals need a predecessor DP, not a cardinality exchange

View access options

Weighted Interval PredecessorDP Prefix Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010425The capacity-8 knapsack optimum is items 2 and 4; fractions and off-by-one cells are not 0/1

View access options

Zero One Knapsack TableKnapsack Take Skip Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010426The unique minimum four-matrix product is (A1 A2)(A3 A4) at cost 405

View access options

Matrix Chain Recurrence TableMatrix Chain Split Reconstruction

PrivateLabels unavailable

Private saving unavailable

Dynamic programming and state designAlgorithms · Mixed review

Progress not loaded

ALG:010527A DAG longest s-t path is a topological max-DP with minus-infinity unreachable labels

View access options

Dag Topo Longest PathUnreachable Minus Infinity Init

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010528Strong connectivity is mutual reachability: the SCCs of a chain of cycles form a path DAG

View access options

Kosaraju Scc TraceStrong VS One Way Reachability

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:010529A feasible flow of 14 and the source cut of capacity 14 certify the max-flow min-cut value

View access options

Ford Fulkerson ResidualMaxflow Mincut Certificate

PrivateLabels unavailable

Private saving unavailable

Graph optimization and traversal algorithmsAlgorithms · Mixed review

Progress not loaded

ALG:0106303SAT reduces to Independent Set by clause triangles and complementary conflict edges

View access options

3sat Independent Set ReductionComplementary Conflict Edges

PrivateLabels unavailable

Private saving unavailable

Reductions, NP-completeness, and approximationAlgorithms · Mixed review

Progress not loaded

ALG:010631Both endpoints of a maximal matching 2-approximate Vertex Cover, tightly on a star

View access options

Maximal Matching Vertex CoverApproximation Factor Two

PrivateLabels unavailable

Private saving unavailable

Reductions, NP-completeness, and approximationAlgorithms · Mixed review

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920011Let T(1)=1, and for every integer n\ge2, let Find an exact formula for T(n) when n is a power of 2.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920012Let T(n)=1 for integers 1\le n\le2, and for n\ge3, let Determine a tight asymptotic bound.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920013Let T(n)=1 for integers 0\le n\le1, and for n\ge2, let Determine a tight asymptotic bound.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920014Let T(n)=1 for integers 0\le n\le1, and for n\ge2, let Determine a tight asymptotic bound, proving explicit upper a…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920015Consider: ```text Split(n): if n == 1: perform one unit of local work return Split(floor(n/2)) Split(ceil(n/2)) per…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920016Two algorithms have running times defined on powers of 2 by and Derive exact closed forms, determine tight asymptot…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920017Consider insertion sort: ```text for j = 2 to n: key = A[j] i = j - 1 while i >= 1 and A[i] > key: A[i + 1] = A[i]…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920018Let A[1..n] be sorted in nondecreasing order, let x be a key, and consider: ```text lo = 1 hi = n + 1 while lo < hi…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920019For integers a\ge b\ge0, (a,b)\ne(0,0), consider Euclid's algorithm: ```text while b != 0: r = a mod b a = b b = r…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920020For a real number x and a nonnegative integer n, consider: ```text Pow(x, n): if n == 0: return 1 y = Pow(x, floor(…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920021Let A[1..p] and B[1..q] be nondecreasing arrays.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920022Let A[1..n] be an array and P a constant-time predicate.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920023An array A[1..n], n\ge2, contains distinct comparable keys.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920024Consider: ```text for i = 1 to n - 1: if A[i] > A[i + 1]: swap A[i] and A[i + 1] return A ``` Determine whether the…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920025Given an array A[1..n] of real numbers, n\ge1, design a divide-and-conquer algorithm returning the maximum sum of a…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920026Let n\ge1, k=\lceil\log_2(n+1)\rceil, and let `bits[0..k-1]` initially contain zeros, with index 0 least significant.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920027In the unit-cost RAM model, analyze the following code for independent positive integers n,m: ```text count = 0 for…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920028A randomized recursive procedure on input size n\ge1 performs exactly cn local work, where c>0, chooses K uniformly…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920029For an array A[1..n] of distinct comparable keys, an inversion is a pair (i,j) with i<j and A[i]>A[j].

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920030Given a nondecreasing integer array A[0..n-1] and an integer x, return the smallest and largest indices at which x…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920031An array A[0..n-1] was formed by cyclically rotating a strictly increasing array.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920032A bitonic array contains distinct numbers that strictly increase to one maximum and then strictly decrease; either…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920033A conceptually infinite array contains a finite strictly increasing sequence followed by infinitely many +\infty se…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920034Given nondecreasing arrays A,B of lengths m,n, and 1\le k\le m+n, return the k-th smallest element of their combine…

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

ALG:9920035An array A[0..n-1] has pairwise distinct values.

View access options

Correctness ComplexityAlgorithms Problem Solving

PrivateLabels unavailable

Private saving unavailable

Correctness proofs and asymptotic complexityAlgorithms · Calculation

Progress not loaded

Problem results

ALG:9920001Let all logarithms have base 2, and let all functions have domain the positive integers.

ALG:9920002Arrange the following functions into asymptotic equivalence classes, ordering the classes from smallest to largest…

ALG:9920003Let f,g:\mathbb N\to(0,\infty).

ALG:9920004For each positive integer n, define Determine a tight asymptotic bound for S(n).

ALG:9920005In the unit-cost RAM model, each execution of `count = count + 1` costs one unit.

ALG:9920006Consider the following code, where n\ge2 is an integer and every arithmetic operation has unit cost: ```text count…

ALG:9920007Let `popcount(n)` denote the number of 1-bits in the ordinary base-2 representation of a positive integer n.

ALG:9920008For a positive integer n, consider: ```text count = 0 for i = 1 to n: j = 1 while j <= n: count = count + 1 if j >=…

ALG:9920009In the following code, `ceil_sqrt(i)` returns \lceil\sqrt i\rceil in unit time.

ALG:9920010Given an integer n\ge4, design nonrecursive pseudocode containing a designated unit-cost statement that executes \T…

Find a problem

Problem results

ALG:9920001Let all logarithms have base 2, and let all functions have domain the positive integers.

ALG:9920002Arrange the following functions into asymptotic equivalence classes, ordering the classes from smallest to largest…

ALG:9920003Let f,g:\mathbb N\to(0,\infty).

ALG:9920004For each positive integer n, define Determine a tight asymptotic bound for S(n).

ALG:9920005In the unit-cost RAM model, each execution of `count = count + 1` costs one unit.

ALG:9920006Consider the following code, where n\ge2 is an integer and every arithmetic operation has unit cost: ```text count…

ALG:9920007Let `popcount(n)` denote the number of 1-bits in the ordinary base-2 representation of a positive integer n.

ALG:9920008For a positive integer n, consider: ```text count = 0 for i = 1 to n: j = 1 while j <= n: count = count + 1 if j >=…

ALG:9920009In the following code, `ceil_sqrt(i)` returns \lceil\sqrt i\rceil in unit time.

ALG:9920010Given an integer n\ge4, design nonrecursive pseudocode containing a designated unit-cost statement that executes \T…