Revision approach
- Algorithm design obligations
- States and choices
- Correctness argument
- Work and peak storage
- Independent subproblems
- Subproblem reuse
- Safe local choices
- Feasibility pruning
- Objective bounds
- Strategy name alone insufficient
👁 Full explanation
Design an algorithm by specifying its states, choices and correctness argument, then count its work and peak storage. A familiar strategy name is not enough: independent subproblems, reuse, safe local choices, feasibility pruning and objective bounds lead to different methods. - Fix the cost model
- Input size and input case
- Primitive operation
- Arithmetic model
- Sum/recurrence before asymptotic choice
👁 Full explanation
For cost questions fix input size, case, primitive operation and arithmetic model. Write the sum or recurrence before selecting an asymptotic bound. - Design-technique practice
- Small execution traces
- Discarded alternatives: no better required answer
- Justify elimination
👁 Full explanation
For each design technique practice a small trace and explain why its discarded alternatives cannot improve the required answer. - Essential analysis distinctions
- Exact algorithm versus heuristic
- Decision versus optimization
- Tight bound versus valid upper bound
👁 Full explanation
Distinguish an exact algorithm from a heuristic, a decision problem from an optimization problem, and a tight bound from a merely valid upper bound.
DAA01
Problem specification and correctness
[Exam Focus]- Problem specification and algorithm properties
- Inputs, output, constraints
- Empty-solution policy
- Finite, definite, executable methods
- Source-language independence
- Feasible: satisfies constraints
- Optimal: best feasible
- Conditional branches: legitimate control flow
👁 Full explanation
State inputs, output, constraints and empty-solution policy. Algorithms are finite, definite executable methods independent of source language; feasible satisfies constraints, optimal is best feasible. Conditional branches are legitimate control flow. - Correctness proof obligations
- Invariant initialization
- Invariant preservation
- Invariant at termination
- Recursion: base cases
- Recursion: inductive reduction
- Testing finds failures
- Finite tests ≠ universal correctness proof
👁 Full explanation
Prove an invariant initially, after each step and at termination; for recursion prove base cases and the inductive reduction. Testing finds failures but finite tests do not prove correctness for all inputs.
5 related practice questions
Blueprint: DAA1 · Note references: DAA-M, DAA-N, DAA-S
- Problem specification and algorithm properties
DAA02
Cost models and input size
[Exam Focus]- Cost models and input size
- Array length n
- Graph vertices V, edges E
- Integer bit length
- RAM: bounded-word arithmetic/access constant
- Arbitrary-precision arithmetic costs
- Long-output printing costs
- Elapsed time: hardware, compiler, cache
- I/O and competing load effects
👁 Full explanation
Analysis counts operations and storage as functions of input size: array length n, graph vertices V/edges E, or the number of bits in integers. A RAM model commonly gives constant cost to bounded-word arithmetic/access. Arbitrarily large integer arithmetic and printing long outputs need their own costs. Elapsed measurements also depend on hardware, compiler, cache, I/O and competing load. - Analysis methods and resource metrics
- Experimental/dynamic: actual runs
- Asymptotic: abstract growth
- Probabilistic: expectations
- No universal taxonomy exclusion
- Graph/dynamic analysis labels not inherently invalid
- Auxiliary space excludes input
- I/O complexity: transfers
- Representation affects costs
- Data type complexity: nonstandard metric name
👁 Full explanation
Experimental/dynamic measurement observes actual runs; asymptotic analysis abstracts growth; probabilistic analysis studies expectations. There is no universal taxonomy proving “graph analysis” or “dynamic analysis” is invalid. Auxiliary space excludes input; I/O complexity counts transfers. Representation affects costs; “data type complexity” is not a standard metric name.
13 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Cost models and input size
DAA03
Input cases versus bounds
[Exam Focus]- Input-case definitions
- Fixed input size n
- Best: minimum cost
- Worst: maximum cost
- Average: specified input distribution
- Randomized expectation: internal choices
- One fixed input possible
- Smallest input ≠ best case
👁 Full explanation
At fixed size n, best case minimizes cost, worst case maximizes it, and average case takes an expectation under a specified input distribution. Randomized expected cost may average internal choices for one fixed input. Smallest input size is not best case. - Bounds independent of cases
- O/Ω/Θ: function bounds
- Independent of case or resource
- Worst upper bound: all size-n inputs
- O ≠ worst case
- Constant best case not universal
- Quadratic worst case not universal
👁 Full explanation
O/Ω/Θ bound functions independently of case or resource. A worst-case upper bound covers every size-n input, but O does not mean worst case. Constant best case and quadratic worst case are not universal.
14 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Input-case definitions
DAA04
Formal asymptotic bounds
[Exam Focus]- Formal asymptotic relations
- Eventually nonnegative f,g
- O: f(n)≤c·g(n), n≥n₀
- Fixed c>0
- Ω: reversed inequality
- Θ: both bounds
- o: f/g→0
- ω: f/g→∞
- Ratio existence condition
- Θ: growth up to constant factors
- No exact-seconds/equal-case implication
👁 Full explanation
For eventually nonnegative f, g, f∈O(g) means f(n)≤c·g(n) for all n≥n 0, with fixed c>0. Ω reverses that inequality; Θ requires both bounds. Little-o means f/g→0, and little-ω means f/g→∞ where the ratio exists. Θ specifies growth up to constant factors, not exact seconds or identical best/worst cases. - Asymptotic proof scope
- Whole tail inequality
- Selected values insufficient
- Transitive upper-bound chains
- Nonnegative sums: largest growth dominates
👁 Full explanation
Prove the inequality for the whole tail, not selected values. Transitivity allows chained upper bounds; sums are dominated by the largest nonnegative growth term. - Worked example Bound witnesses and incorrect inequality
- 10n+5≤15n, n≥1
- c=15,n₀=1
- 3n²+4n+1≤8n², n≥1
- 7n²+3n+5≤8n²: false at n=1
- Correct witness: c=15,n₀=1
👁 Full explanation
Worked microexample10n+5≤15n for n≥1, so c=15,n 0=1 works. Also 3n²+4n+1≤8n² for n≥1. The inequality 7n²+3n+5≤8n² is false at n=1; c=15 works for all n≥1.
16 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Formal asymptotic relations
DAA05
Growth ordering and loose bounds
[Exam Focus]- Representative growth ordering
- 1<log n<n<n log n
- n log n<n²<n³<…
- Fixed b>1: polynomial<b^n<n!
- Log bases: constant-factor difference
- n log n,n²: superlinear
- log n: sublinear
- Polynomial: fixed input-size exponent
👁 Full explanation
Representative growth is 1,log n,n,n log n,n²,n³,…,b^n,n! for fixed b>1. Log bases differ by a constant. Both n log n and n² are superlinear; log n is sublinear. Polynomial growth has a fixed exponent in input size. - Loose bounds and finite-input speed
- O(n²) implies O(n³)
- Upper bounds needn't be tight
- Multiple valid offered bounds
- Growth ordering alone: insufficient finite-speed prediction
- Big-O alone: insufficient finite-speed prediction
👁 Full explanation
O(n²) also implies O(n³): upper bounds need not be tight. Several asymptotic bounds can hold simultaneously for the same function. Neither representative growth ordering nor Big-O labels alone determine finite-input speed. - Worked example Ratio comparison example
- f=4n²; g=8n
- f/g=n/2→∞
- f∈Ω(g)
- f∈ω(g)
- f∉O(g)
- f∉Θ(g)
👁 Full explanation
Worked microexampleFor f=4n² and g=8n, f/g=n/2→∞. Therefore f∈Ω(g) and evenω(g), while f is neither O(g) nor Θ(g).
16 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Representative growth ordering
DAA06
Loop counts and additive costs
[Exam Focus]- Loop-count arithmetic
- Sequential costs add
- Independent nested counts multiply
- Dependent loops require sums
- Constant body × n: Θ(n)
- Σᵢ₌₁ⁿi=n(n+1)/2=Θ(n²)
- Doubling until i≥n: ⌈log₂n⌉
- Doubling formula condition: n>1
- 10n loop: linear
- Constant-cost output assumption
👁 Full explanation
Sequential costs add; independent nested loop counts multiply. A dependent loop requires summation. n iterations of a constant body give Θ(n); ∑i=1.. n i=n(n+1)/2 gives Θ(n²). Doubling i=1,2,4,… until i≥n takes ceil(log 2 n) iterations for n>1. A 10n loop is linear under constant-cost output. - Expected total and exact counts
- Fixed size: m operations
- Each expected cost f(n)
- Linearity: expected total=m f(n)
- Independence unnecessary
- Changing sizes: Σf(nᵢ)
- Tests/increments/arithmetic/assignments affect coefficients
👁 Full explanation
If m operations each have expected cost f(n) at the same fixed size, expected total is m f(n), by linearity of expectation; independence is unnecessary. If sizes change, sum f(n_i). Exact coefficients depend on whether tests, increments, arithmetic and assignments count separately. - Worked example Exact loop-count convention
- Two initializations
- n+1 tests
- n increments
- 2n body operations
- One return
- Total: 4n+4
- Different primitives change exact count
- Growth remains Θ(n)
👁 Full explanation
Worked microexampleFor sum=0; for(i=1;i<=n;i++) sum=sum+1; return sum: counting two initializations, n+1 tests, n increments,2n body operations and one return gives 4n+4. A different primitive-cost convention changes this exact expression, not Θ(n).
5 related practice questions
Blueprint: DAA1 · Note references: DAA-M, DAA-N, DAA-S
- Loop-count arithmetic
DAA07
Conditional loops and malformed code
[Exam Focus]- Conditional nested-loop summation
- i=0..n−1; j=i..i²−1
- k=0..j−1 only when j%i==0
- i=0,1: empty j ranges
- No remainder by zero evaluated
- i≥2: j=i,2i,…,(i−1)i
- Inner work=iΣₘ₌₁ⁱ⁻¹m
- i²(i−1)/2=Θ(i³)
- Sum over i: Θ(n⁴)
- Condition checks: Θ(n³)
👁 Full explanation
For the loop i=0.. n−1, j=i.. i²−1, and k=0.. j−1 only when j%i==0, i=0 and 1 have empty j ranges, so no remainder by zero is evaluated. For i≥2, successful j values are i,2i,…,(i−1)i. The inner work is i∑m=1.. i−1 m=i²(i−1)/2=Θ(i³). Summing over i gives Θ(n⁴); condition checks add only Θ(n³). - Loop assumptions and malformed-code traps
- Offered n⁵,n⁷: valid loose upper bounds
- Neither bound tight
- Mathematical integers
- Constant-cost output
- Signed C++ i*i overflow: undefined
- Mixed-language syntax: repair before runtime claim
- Parameter n redeclaration: syntax defect
- return @;3: syntax defect
- Syntax defects ≠ logarithmic algorithms
👁 Full explanation
Neither n⁵ nor n⁷ is tight for this loop, though both are valid Big-O upper bounds. This assumes mathematical integers and constant-cost output; literal signed C++ overflow in i*i is undefined, and executable runtime analysis requires valid syntax in a specified language. Redeclaring parameter n and using return @;3 are syntax errors; neither establishes logarithmic complexity.
2 related practice questions
Blueprint: DAA1 · Note references: DAA-M, DAA-N, DAA-S
- Conditional nested-loop summation
DAA08
Peak storage and recursion
[Exam Focus]- Peak storage accounting
- Simultaneously live storage
- Cumulative allocations ≠ peak space
- Requested input/auxiliary/stack convention
- n active constant frames: Θ(n)
- log n constant frames: Θ(log n)
- Total calls ≠ peak recursion depth
👁 Full explanation
Space complexity measures peak simultaneously live storage, not the sum of every allocation ever made. Count input, auxiliary structures and stack according to the requested convention. n active recursion levels with constant-size frames need Θ(n) stack; depth log n with constant frames needs Θ(log n). The number of total calls does not determine peak depth. - Hidden storage and time-space tradeoffs
- Array slicing/copying overhead
- Index-based pseudocode may omit copies
- Tail-call elimination: language/runtime-dependent
- Ordinary C++/Java: no assumed elimination
- Cached subproblem results save time
- Caching consumes memory
👁 Full explanation
Slicing/copying arrays can add storage omitted by an index-based pseudocode analysis. Tail-call elimination is language/runtime-dependent and cannot be assumed for ordinary C++/Java recursion. Resource tradeoffs include caching subproblem results to save time while consuming memory.
4 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Peak storage accounting
DAA09
Recurrences and substitution
[Exam Focus]- Recurrence construction and expansion
- Every recursive call
- Nonrecursive work
- Base case
- T(n)=T(n−1)+Θ(1)→Θ(n)
- T(n)=T(n/2)+Θ(1)→Θ(log n)
- T(n)=2T(n/2)+Θ(n)
- Logarithmic levels × Θ(n)
- Result: Θ(n log n)
👁 Full explanation
Include every recursive call, nonrecursive work and base case. Expansion gives T(n)=T(n−1)+Θ(1)→Θ(n), and T(n)=T(n/2)+Θ(1)→Θ(log n). For 2T(n/2)+Θ(n), logarithmically many levels each cost Θ(n), giving Θ(n log n). - Substitution proof method
- Guess bound
- Induction with constants
- Base-case verification
- Lower-order correction may close induction
- Unequal/decrementing recurrences: separate analysis
👁 Full explanation
Substitution guesses a bound and proves it inductively with constants/base cases; a lower-order correction may close the induction. Unequal/decrementing recurrences need separate analysis.
3 related practice questions
Blueprint: DAA1 · Note references: DAA-M, DAA-N, DAA-S
- Recurrence construction and expansion
DAA10
Master theorem and recursion trees
[Exam Focus]- Master theorem and recursion tree
- T(n)=aT(n/b)+f(n)
- a≥1; b>1
- p=log_b a
- Level i: a^i nodes
- Node size: n/b^i
- Polynomially smaller f: Θ(n^p)
- f=Θ(n^p): Θ(n^p log n)
- Polynomially larger f: Θ(f(n))
- Case 3 regularity: a f(n/b)≤c f(n)
- Fixed c<1
👁 Full explanation
For T(n)=aT(n/b)+f(n), a≥1, b>1, let p=log_b a. Level i has a^i nodes of size n/b^i. Compare f with n^p: a polynomial gap below gives Θ(n^p); f=Θ(n^p) gives Θ(n^p log n); a polynomial gap above gives Θ(f(n)) if a f(n/b)≤c f(n) for fixed c<1. The third case needs this regularity condition. - Master theorem limitations
- Log-factor boundary: extension or summation
- State base work
- Include leaf costs
- T(n)=T(n−1)+n: outside this version
- Unequal-split quicksort: outside this version
👁 Full explanation
A log-factor boundary may need an extended theorem or explicit summation. State base work and include leaves. This version does not apply to T(n)=T(n−1)+n or unequal-split quicksort. - Worked example Master theorem worked cases
- 4T(n/2)+n→Θ(n²), case 1
- 2T(n/2)+n→Θ(n log n), case 2
- T(n/2)+n²→Θ(n²), case 3
- 4T(n/2)+n²→Θ(n² log n), case 2
👁 Full explanation
Worked microexample4T(n/2)+n gives Θ(n²);2T(n/2)+n gives Θ(n log n); T(n/2)+n² gives Θ(n²). Each follows a different case. Also 4T(n/2)+n² gives Θ(n² log n), case 2.
4 related practice questions
Blueprint: DAA1 · Note references: DAA-M, DAA-N, DAA-S, DAA-MASTER
- Master theorem and recursion tree
DAA11
Comparison-sorting lower bounds
[Exam Focus]- Comparison-sort decision-tree lower bound
- Distinct-key orderings: n! leaves
- Height h: at most 2^h leaves
- h≥log₂(n!)=Ω(n log n)
- Mergesort matches worst-case bound
- Array indexing allowed
👁 Full explanation
A comparison decision tree needs at least n! leaves for distinct-key orderings. Height h allows at most 2^h leaves, so h≥log 2(n!)=Ω(n log n); merge sort matches this worst-case bound. Array indexing is not forbidden. - Lower-bound model boundaries
- Counting/radix: structured keys
- Outside comparison-only model
- Recurrences: particular algorithm analysis
- Decision tree: entire comparison class
- Supplied inappropriate-technique justifications: all unsound
👁 Full explanation
Counting/radix sorting exploits structured keys outside the comparison-only model. Recurrences analyze particular algorithms; this decision tree bounds the entire comparison class. Assess a lower-bound argument by its computational model and reasoning rather than by a technique label alone.
2 related practice questions
Blueprint: DAA1, DAA3 · Note references: DAA-M, DAA-N, DAA-S, DAA-LOWER
- Comparison-sort decision-tree lower bound
DAA12
Choosing algorithm design strategies
[Exam Focus]- Design strategies from structural conditions
- Divide-and-conquer: smaller largely independent instances
- Combine subproblem results
- DP: reuse defined subproblem states
- Greedy: feasible safe local commitment
- Backtracking: grow/retract when constraints fail
- Branch-and-bound: best possible objective test
- Prune when incumbent cannot be beaten
👁 Full explanation
Divide and conquer solves smaller largely independent instances and combines results. DP reuses a defined set of subproblem states. Greedy commits to a feasible local choice only when a safety argument supports it. Backtracking grows/retracts candidates when constraints fail; branch and bound also rejects candidates whose best possible objective cannot beat an incumbent. - Ambiguous strategy descriptions
- Subproblems/choices/incremental/optimization: several strategies
- Exponential runtime insufficient for method choice
- Specify overlap
- Specify local-choice safety
- Specify revisability and exactness
- Specify usable bounds
- Module selection-sort classification: erroneous
- Ordinary selection: repeatedly choose one minimum
👁 Full explanation
“Breaks into subproblems,” “sequence of choices,” “incremental,” or “optimization” alone describes several strategies. Exponential runtime is an outcome, not enough information to select a method. Specify overlap, local-choice safety, revisability, exactness and usable bounds. Ordinary selection sort repeatedly selects one minimum; it is not a divide-and-conquer algorithm.
17 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Design strategies from structural conditions
DAA13
Binary search and paired extrema
[Exam Focus]- Binary-search invariant and costs
- Sorted random-access data
- Inclusive low/high bounds
- mid=low+(high−low)//2
- high=mid−1 or low=mid+1
- Stop: found or low>high
- T(n)=T(n/2)+Θ(1)
- Worst: Θ(log n); best: Θ(1)
- Iterative auxiliary space: Θ(1)
- Recursive auxiliary space: Θ(log n)
👁 Full explanation
Binary search requires sorted random-access data. Maintain inclusive low/high bounds, compute mid=low+(high−low)//2, and replace high with mid−1 or low with mid+1 according to the comparison. Stop when found or low>high. T(n)=T(n/2)+Θ(1): worst Θ(log n), best Θ(1); iterative auxiliary space Θ(1), recursive Θ(log n). - Simultaneous minimum/maximum comparisons
- Two unconditional comparisons per element
- Scan comparisons: 2n−2, every order
- Pair elements: compare within pair
- Smaller→minimum; larger→maximum
- Even n: 3n/2−2 comparisons
- Balanced recursion: 2T(n/2)+Θ(1)=Θ(n)
- Two-if scan: no n−1 best case
👁 Full explanation
Finding both extrema by two unconditional comparisons per element costs 2n−2 comparisons, regardless of order. Pair elements first, compare within each pair, then compare the smaller with minimum and larger with maximum: even n uses 3n/2−2 comparisons. A balanced recursive version has T(n)=2T(n/2)+Θ(1)=Θ(n). An unconditional two-if scan does not have an n−1-comparison best case.
1 related practice question
Blueprint: DAA1, DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Binary-search invariant and costs
DAA14
Merge sort
[Exam Focus]- Merge-sort invariant and procedure
- Split by indices
- Recursively sort halves
- Temporary result: smaller remaining front
- Output prefix sorted
- Prefix contains smallest consumed elements
- Append unexhausted suffix
- Stable ties: left half first
👁 Full explanation
Split by indices, recursively sort each half, then repeatedly copy the smaller remaining front element into a temporary result. The merge invariant says the output prefix is sorted and contains the smallest elements already consumed. Append the unexhausted suffix. Equal keys must be taken from the left half first to preserve stability. - Ordinary array merge-sort analysis
- T(n)=2T(n/2)+Θ(n)=Θ(n log n)
- All input orders
- Auxiliary buffer: Θ(n)
- Recursion depth: Θ(log n)
- +O(n) alone: upper bound only
- Tightness requires linear merge work
- Base cases: empty/singleton subarrays
👁 Full explanation
Ordinary array merge sort has T(n)=2T(n/2)+Θ(n)=Θ(n log n) across input orders, Θ(n) auxiliary buffer and Θ(log n) recursion depth. A written +O(n) recurrence alone establishes an upper bound; the tight result also uses linear merge work. Empty/singleton subarrays are base cases. - Worked example Merge-sort worked trace
- [4,1,3,2]→[4,1] and [3,2]
- Sorted halves: [1,4] and [2,3]
- Select 1,2,3; append 4
- Original sortedness unnecessary
👁 Full explanation
Worked microexample[4,1,3,2] splits into[4,1] and[3,2], which sort to[1,4] and[2,3]. Merge selects 1,2,3 and appends 4. No assumption that the original array is already sorted is needed.
10 related practice questions
Blueprint: DAA1, DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Merge-sort invariant and procedure
DAA15
Quicksort variants and costs
[Exam Focus]- Quicksort partition variants
- Choose pivot, partition, recurse
- Two pointers: advance i below pivot
- Retreat j above pivot
- i≤j: swap, advance both
- Bound scans
- Equal values: ensure progress
- Recurse on resulting ranges
- Hoare boundaries: pivot not necessarily final
- Lomuto: pivot commonly final
- Keep return conventions distinct
👁 Full explanation
Choose a pivot, partition, then sort the resulting smaller ranges. In a two-pointer scheme, advance i while values are below pivot and j while above; when i≤j, swap and advance both. Bound the scans and ensure progress on equal values. Recurse on the resulting ranges. Hoare-style partition boundaries need not put the pivot at its final position; Lomuto-style partition commonly does. Do not mix their return conventions. - Quicksort costs and refinements
- Balanced splits: Θ(n log n)
- Highly unbalanced splits: Θ(n²)
- Random pivots: expected Θ(n log n)
- Expectation ≠ deterministic guarantee
- Median-of-three retains adversarial cases
- Three-way partition: repeated keys
- Standard quicksort: unstable
- Expected stack Θ(log n); worst Θ(n)
- Recurse smaller side, iterate larger
- Refined stack bound: O(log n)
👁 Full explanation
Balanced splits give Θ(n log n); repeatedly highly unbalanced splits give Θ(n²). Random pivots give expected Θ(n log n), not a deterministic guarantee. Median-of-three does not eliminate adversarial cases; three-way partitioning helps repeated keys. Standard quicksort is unstable, uses expected Θ(log n) stack but worst Θ(n); recursing on the smaller side and iterating on the larger bounds stack by O(log n).
7 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Quicksort partition variants
DAA16
Sorting choices and costs
- Elementary sorting choices
- Insertion: larger sorted-prefix keys shift
- Insertion: strict comparisons preserve stability
- Optimized bubble: adjacent inversion swaps
- Bubble stop: no-swap pass
- Insertion/bubble: Θ(n) best, Θ(n²) worst
- Selection: repeated suffix minimum
- Selection: Θ(n²) comparisons every order
- Selection: normally unstable
- All three: Θ(1) auxiliary array space
👁 Full explanation
Insertion shifts larger sorted-prefix keys: stable with strict comparisons, Θ(n) best and Θ(n²) worst. Optimized bubble sort swaps adjacent inversions and stops after a no-swap pass: stable, Θ(n) best, Θ(n²) worst. Selection repeatedly finds a suffix minimum: Θ(n²) comparisons in every order, normally unstable. These use Θ(1) auxiliary array space. - Heap, merge, quicksort tradeoffs
- Max-heap construction: Θ(n)
- Extract/restore: O(log n) per item
- Heapsort total: O(n log n)
- Heapsort: Θ(1) auxiliary space
- Heapsort: ordinarily unstable
- Heapsort ≠ standard divide-and-conquer
- Mergesort: stability/worst-case guarantees
- Quicksort practical advantage: implementation/workload-dependent
👁 Full explanation
Heap sort builds a max-heap in Θ(n), then extracts/restores in O(log n) per item: O(n log n) total, Θ(1) auxiliary space, ordinarily unstable. It is not standard D&C. Merge sort offers stability/worst-case guarantees; quicksort’s practical advantage depends on implementation/workload.
4 related practice questions
Note references: DAA-M, DAA-N, DAA-S
- Elementary sorting choices
DAA17
Strassen matrix multiplication
[Exam Focus]- Matrix multiplication divide/combine costs
- Ordinary n×n: n products/sums per entry
- Ordinary multiplication: Θ(n³)
- Eight products: 8T(n/2)+Θ(n²)=Θ(n³)
- Strassen: seven block products
- Block sums and differences
- 7T(n/2)+Θ(n²)=Θ(n^log₂7)
- Strassen exponent: approximately 2.807
👁 Full explanation
Ordinary n×n multiplication computes n products/sums per output entry: Θ(n³). Eight half-size block products still give 8T(n/2)+Θ(n²)=Θ(n³). Strassen uses seven products plus block sums/differences:7T(n/2)+Θ(n²)=Θ(n^log 2 7)≈Θ(n^2.807). - Strassen assumptions and tradeoffs
- Zero-padding preserves required product
- Smaller exponent versus extra additions
- Temporary storage overhead
- Possible numerical issues
- Ordinary base case: small matrices
- Specify exact versus floating-point arithmetic
👁 Full explanation
Zero-padding preserves the required product. The smaller exponent trades extra additions/temporary storage and possible numerical issues against multiplication work. Use an ordinary base case for small matrices and specify exact versus floating-point arithmetic.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Matrix multiplication divide/combine costs
DAA18
Maximum contiguous subarray
[Exam Focus]- Maximum subarray by divide-and-conquer
- Contiguous subarray ≠ arbitrary subsequence
- Compare best left/right/crossing
- Crossing: left suffix+right prefix
- Best crossing found in Θ(n)
- 2T(n/2)+Θ(n)=Θ(n log n)
👁 Full explanation
A maximum subarray is contiguous; it is not an arbitrary subsequence. Divide-and-conquer compares the best left, best right and best crossing result. The crossing result is the best suffix of the left half plus best prefix of the right, found in Θ(n). This yields 2T(n/2)+Θ(n)=Θ(n log n). - Kadane dynamic programming
- end[i]=max(A[i],end[i−1]+A[i])
- Keep largest ending sum
- Time: Θ(n)
- Extra space: Θ(1)
- Nonempty initialization: A[0], not zero
- All-negative result: largest element
- Empty allowed: zero possible
- Unqualified strategy question: D&C and DP
👁 Full explanation
Kadane’s DP keeps the best sum ending at i: end[i]=max(A[i], end[i−1]+A[i]); keep the largest end seen. This is Θ(n) time and Θ(1) extra space. For a required nonempty subarray initialize from A[0], not zero; all-negative input then returns its largest element. Empty-allowed variants may return zero. Both D&C and DP can solve the maximum-subarray problem; specify the algorithm before assigning its complexity. - Worked example Maximum-subarray examples
- [−2,3,−1,4,−5] ending: −2,3,2,6,1
- Optimum 6: [3,−1,4]
- [−4,−2]: nonempty answer −2
👁 Full explanation
Worked microexampleFor[−2,3,−1,4,−5], ending sums are−2,3,2,6,1; optimum 6 comes from[3,−1,4]. For[−4,−2], a nonempty answer is−2.
1 related practice question
Blueprint: DAA2 · Note references: DAA-S, DAA-MAX
- Maximum subarray by divide-and-conquer
DAA19
Greedy proofs and counterexamples
[Exam Focus]- Greedy safety and exchange proofs
- Locally attractive feasible choice
- Commit without later undoing
- Optimal substructure alone insufficient
- Exchange greedy choice into optimum
- No worsening of cost
- Recurse after exchange
- MST cut proof: exchange argument
👁 Full explanation
A greedy algorithm repeatedly selects a locally attractive feasible option without later undoing it. Optimal substructure alone does not prove this safe. An exchange proof inserts the greedy choice into an optimum without worsening cost; recurse. MST cut proofs use this exchange. - Greedy limits and valid applications
- Simple decisions, low overhead
- Irrevocable errors
- Problem-specific applicability
- Greedy heuristic ≠ approximation guarantee
- Coins {1,3,4}; target 6
- Largest-first: 4+1+1; optimum: 3+3
- Activity selection: earliest finish
- Maximize count: nonoverlapping unweighted intervals
- Exchange first activity for earlier finish
- At least as much remaining room
👁 Full explanation
Advantages are often simple decisions and low overhead; limitations are irrevocable errors and problem-specific applicability. A heuristic has no approximation guarantee merely because it is greedy. For coins{1,3,4} and target 6, largest-first gives 4+1+1 while 3+3 uses fewer coins. Activity selection instead has a safe earliest-finish rule for maximizing the number of nonoverlapping unweighted intervals; replacing the first chosen activity in an optimum with an earlier-finishing one leaves at least as much room.
12 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Greedy safety and exchange proofs
DAA20
Fractional versus indivisible knapsack
[Exam Focus]- Fractional knapsack greedy rule
- Positive weights/profits
- Divisible items
- Decreasing value/weight order
- Whole fitting items, then fitting fraction
- Exchange lower-density for higher-density weight
- Value cannot decrease
- Sorting O(n log n); scan linear
- Zero-weight beneficial items: handle separately
- Avoid division by zero
👁 Full explanation
For positive weights/profits and divisible items, sort by decreasing value/weight, take complete items while they fit, then the fitting fraction of the next. The exchange argument replaces lower-density selected weight by available higher-density weight; value cannot decrease. Sorting costs O(n log n), followed by a linear scan. Handle zero-weight beneficial items separately rather than divide by zero. - Indivisibility breaks ratio proof
- Capacity 10
- Items (6,12),(5,8),(5,8)
- Ratio-greedy value: 12
- 0/1 optimum: 8+8=16
- Specify fractional/0/1/unbounded knapsack
- Feasibility ≠ optimality
👁 Full explanation
This proof depends on divisibility. With capacity 10 and items(6,12),(5,8),(5,8), ratio-greedy chooses value 12; the two weight 5 items give 16 under 0/1 rules. Specify whether the knapsack problem is fractional,0/1 or unbounded. Feasibility alone does not guarantee optimality. - Worked example Fractional knapsack worked trace
- Weights 15,10,18; values 24,15,25
- Capacity 20
- Take weight 15 item
- Take half weight 10 item
- Value=24+7.5=31.5
- Initial capacity 20 ≠ item count
👁 Full explanation
Worked microexampleWeights 15,10,18 and values 24,15,25 with capacity 20: take the weight 15 item and half the weight 10 item. Value 24+7.5=31.5; initial remaining capacity must be 20, not the number of items.
3 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Fractional knapsack greedy rule
DAA21
Unit-time job sequencing
[Exam Focus]- Unit-job scheduling assumptions and rule
- One machine
- Initially available jobs
- Unit durations; integer deadlines
- Profit only for on-time completion
- Nonnegative-profit jobs: decreasing profit
- Latest free slot finishing by deadline
- No feasible slot: reject
- Latest placement preserves tighter-deadline slots
- Profit-first exchange for feasible unit-job sets
👁 Full explanation
Assume one machine, initially available jobs, unit durations, integer deadlines and profit only for on-time completion. Process nonnegative-profit jobs by decreasing profit; place each in the latest free slot finishing by its deadline, or reject it. Latest placement preserves earlier slots for tighter deadlines; feasible unit-job sets support profit-first exchange. - Job sequencing complexity and limitations
- Sorting plus slot scans
- O(n log n+nD)
- Cap D at n
- Equal-profit ordering arbitrary
- Earlier deadline tie rule optional
- Variable durations invalidate rule
- Release times invalidate rule
👁 Full explanation
Sorting plus slot scans costs O(n log n+nD), with D capped at n. Equal-profit order is arbitrary; earlier deadline is optional. Variable durations/release times invalidate this rule. - Worked example Job sequencing worked certificate
- Slots 1…5: J₂,J₄,J₃,J₅,J₁
- Profits: 180+300+190+120+200=990
- All deadlines hold
- J₆ cannot finish by 2
- Five largest profits: 990 upper bound
- Matching bound certifies optimum
👁 Full explanation
Worked microexampleSlots finishing 1…5 contain J 2,J 4,J 3,J 5,J 1. Profits 180+300+190+120+200=990; deadlines hold. J 6 cannot finish by 2. The five largest profits sum to 990, giving a matching upper bound.
3 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Unit-job scheduling assumptions and rule
DAA22
Optimal merging and Huffman coding
[Exam Focus]- Optimal merge pattern
- Combine two smallest weights
- Add sum to total
- Reinsert sum
- Min-heap: O(n log n) time
- Space: O(n)
- p+q: moved-record cost
- Nonempty lists: p+q−1 worst comparisons
- Actual comparisons may be fewer
👁 Full explanation
Combine the two smallest weights, add their sum to total cost, and reinsert it. A min-heap gives O(n log n) time/O(n) space. Cost p+q counts moved records; worst-case comparisons are p+q−1 for nonempty lists, and actual comparisons may be fewer. - Huffman prefix coding and proof
- Frequencies as weights
- 0/1 branches to leaf symbols
- Prefix-free code
- Cost=Σfrequency×depth
- Two least frequencies: deepest siblings
- Exchange, contract, induct
- Ties change codes, preserve optimum cost
- Header overhead may outweigh tiny-file savings
👁 Full explanation
Huffman uses frequencies as weights and 0/1 branches to leaf symbols, making a prefix-free code. Cost is∑frequency×depth. An exchange makes the two least frequencies deepest siblings; contract them and induct. Ties can change codes without changing optimal cost. Header overhead can outweigh tiny-file savings. - Worked example Merge/Huffman worked weights
- Weights 2,3,5,6
- 2+3=5
- 5+5=10
- 10+6=16
- Total weighted merge cost: 31
- Same construction: minimum weighted prefix-code length
👁 Full explanation
Worked microexampleFor weights 2,3,5,6: merge 2+3=5, then 5+5=10, then 10+6=16. Total weighted merge cost 31; the same tree construction minimizes weighted prefix-code length.
4 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Optimal merge pattern
DAA23
MST algorithms and cut proofs
[Exam Focus]- MST properties and uniqueness
- Connected weighted undirected graph
- Spans vertices without cycles
- Minimum total edge weight
- V−1 edges
- Negative edges allowed
- Equal weights: possible multiple MSTs
- Distinct weights suffice for uniqueness
- A tree is a graph
👁 Full explanation
For a connected weighted undirected graph, an MST spans every vertex without cycles and minimizes total edge weight; it has V−1 edges. Negative edges are allowed. Equal weights may yield multiple MSTs; distinct weights suffice for uniqueness. A tree is itself a graph. - Prim, Kruskal, cut-exchange proof
- Prim: cheapest tree-to-outside crossing edge
- Kruskal: globally sorted edges
- Union-find: accept different-component endpoints
- Light cut edge exchange into optimum
- No increased total weight
- Matrix Prim: O(V²)
- Binary-heap Prim: O(E log V)
- Kruskal: O(E log E)
- Dense-graph comparison: implementation-dependent
- Disconnected input: minimum spanning forest
👁 Full explanation
Prim repeatedly adds the cheapest edge crossing from its current tree to an outside vertex. Kruskal sorts edges globally, accepting one only when union-find says its endpoints are in different components. The cut proof exchanges a light crossing edge into some optimum without raising its weight. Matrix Prim costs O(V²); binary-heap Prim O(E log V), and Kruskal O(E log E). Dense-graph comparisons depend on these implementations. Disconnected input gives a minimum spanning forest. - Worked example MST triangle examples
- AB=1,BC=2,AC=4
- Kruskal accepts AB,BC
- Total cost: 3
- All edges 1: any two optimal
- Equal-weight example: uniqueness fails
👁 Full explanation
Worked microexampleTriangle AB=1,BC=2,AC=4: Kruskal accepts AB and BC for cost 3. If every edge is 1, any two edges give an MST, so uniqueness fails.
8 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- MST properties and uniqueness
DAA24
Dijkstra shortest paths
[Exam Focus]- Dijkstra initialization and relaxation
- dist[source]=0; others ∞
- Predecessors initially unset
- Extract minimum-distance unsettled u
- dist[v]=min(dist[v],dist[u]+w(u,v))
- Improvement: update predecessor
- Minimum ∞: remaining vertices unreachable
- Stop after destination finalized
- Discovery alone insufficient for stopping
👁 Full explanation
Initialize dist[source]=0, others∞ and predecessors unset. Repeatedly extract the unsettled vertex u of minimum distance; relax each edge by dist[v]=min(dist[v], dist[u]+w(u, v)), updating predecessors when improved. Once the minimum is∞, remaining vertices are unreachable. A destination may be finalized before stopping, not merely discovered. - Dijkstra proof, failure, costs
- Nonnegative edges preserve finalized distances
- Later unsettled paths cannot improve finalized
- s→a=2; s→b=5; b→a=−4
- Finalize a=2: miss later distance 1
- Binary-heap/list: O((V+E)log V)
- Matrix scanning: O(V²)
- MST: total connection cost
- Dijkstra: each source-path distance
👁 Full explanation
Nonnegative edges ensure a later path through unsettled vertices cannot improve a finalized distance. With s→a=2, s→b=5, b→a=−4, finalizing a at 2 misses the later distance 1. Binary-heap/list implementation costs O((V+E)log V), matrix scanning O(V²). An MST minimizes total connection cost; Dijkstra minimizes each source-path distance, a different objective.
6 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Dijkstra initialization and relaxation
DAA25
DP states and correctness
[Exam Focus]- Dynamic-programming specification and proof
- State meaning and choices
- Recurrence and bases
- Dependency order
- Better subsolution must improve full solution
- Failed replacement: missing state information
- Cover all legal final choices
- Generate feasible candidates
- Induct in dependency order
- Store reconstruction choices
👁 Full explanation
Define state meaning, choices, recurrence, bases and dependency order. Prove replacing a subsolution by a better one improves the full solution; otherwise state information may be missing. Show the recurrence covers all legal final choices and generates feasible candidates, then induct in dependency order. Store choices for reconstruction. - DP signatures and complexity
- Overlapping states motivate reuse
- Optimal substructure supports optimization
- DP also counts and decides
- Optimization not universally required
- Multiple users per state not required
- Cost=states×work per state
- DP may remain exponential
👁 Full explanation
Overlapping states motivate reuse; optimal substructure supports optimization. These are textbook signatures, not requirements that every DP problem optimize or every state have multiple users. DP also counts/decides. Cost=states×work per state and can remain exponential.
14 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Dynamic-programming specification and proof
DAA26
Memoization, tabulation, Fibonacci
[Exam Focus]- Memoization versus tabulation
- Memoization: recursive cache check
- Store solved state results
- Tabulation: explicit dependency order
- Chosen domain may exclude irrelevant states
- Cache keys: all relevant parameters
- Recursion/locality/sparsity affect cost
👁 Full explanation
Memoization recursively checks a cache before solving a state and stores its result. Tabulation orders dependencies explicitly; chosen domains may exclude irrelevant states. Cache keys include all relevant parameters; recursion/locality/sparsity affect implementation cost. - Fibonacci reuse and arithmetic assumptions
- Naive branches recompute F(n−2)
- Naive call count: Θ(φ^n)
- O(2^n): valid loose bound
- F(0)=0; F(1)=1
- F(i)=F(i−1)+F(i−2)
- Memo/tabulation: Θ(n) unit-cost additions
- Two recent values: Θ(1) machine words
- Arbitrary precision: growing bit storage
- Naive overlap ≠ independent D&C ideal
👁 Full explanation
Naive Fibonacci recomputes F(n−2) across branches: call count is Θ(φ^n), with O(2^n) a valid loose upper bound. F(0)=0, F(1)=1 and F(i)=F(i−1)+F(i−2) yield Θ(n) unit-cost additions with memoization/tabulation. Keeping only two recent values uses Θ(1) machine words; arbitrary-precision output needs growing bit storage. This naive overlapping recursion is not the independent-subproblem ideal of D&C.
5 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Memoization versus tabulation
DAA27
DAG paths and Bellman–Ford
[Exam Focus]- DAG/multistage shortest-path DP
- Reverse topological cost-to-go
- F(t)=0
- F(u)=min₍ᵤ,ᵥ₎[w(u,v)+F(v)]
- Missing routes: ∞
- Record minimizing next vertex
- Alternative: forward source-distance propagation
- Adjacency-list complexity: Θ(V+E)
- Negative edges harmless without cycles
- Module forward/backward labels inconsistent
- Follow recurrence dependencies
👁 Full explanation
For a DAG or multistage graph, compute cost-to-go in reverse topological order: F(t)=0 and F(u)=min over outgoing(u, v) of[w(u, v)+F(v)]. Missing routes have∞. Record the minimizing next vertex. Equivalently propagate source distances forward. Complexity is Θ(V+E) with adjacency lists; negative edges are harmless without cycles. Follow the recurrence’s dependencies when choosing the evaluation direction. - Bellman–Ford and strategy ambiguity
- General graphs
- Relax all edges: up to V−1 passes
- Additional pass: reachable negative-cycle test
- Complexity: O(VE)
- Single-source shortest path ≠ uniquely greedy
- Graph assumptions select algorithm
👁 Full explanation
For a general graph, Bellman–Ford relaxes all edges for up to V−1 passes and tests an additional pass for a reachable negative cycle: O(VE). Thus “single-source shortest path” does not uniquely imply greedy; graph assumptions determine the algorithm. - Worked example DAG cost-to-go example
- s→a=2,s→b=5,a→t=4,b→t=−1
- F(a)=4; F(b)=−1
- F(s)=min(6,4)=4
- Optimal route via b
👁 Full explanation
Worked microexamples→a=2,s→b=5,a→t=4,b→t=−1 gives F(a)=4,F(b)=−1 and F(s)=min(6,4)=4 via b.
4 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- DAG/multistage shortest-path DP
DAA28
Floyd–Warshall and reachability
[Exam Focus]- Floyd–Warshall initialization and invariant
- All-pairs distances
- D[i,i]=0
- D[i,j]: minimum direct-edge weight
- Missing edges: ∞
- Negative self-loop: min(0,weight)
- k outermost
- D[i,j]=min(D[i,j],D[i,k]+D[k,j])
- Before phase k: earlier intermediates only
- Guard unreachable sums
- Guard numeric overflow
👁 Full explanation
For all-pairs distances initialize D[i, i]=0, D[i, j] to the minimum direct edge weight, and missing edges to∞. Preserve a negative self-loop by taking min(0, its weight). For k outermost, update D[i, j]=min(D[i, j], D[i, k]+D[k, j]); before phase k, intermediates are restricted to earlier vertices. Guard unreachable sums and numeric overflow. - Floyd–Warshall scope and reachability variant
- Time: Θ(V³)
- Storage: Θ(V²)
- Negative diagonal: negative cycle
- Pairs traversing cycle: no finite minimum
- Warshall reachability: OR/AND replace min/+
- Floyd cost ≠ universal APSP optimum
- Sparse nonnegative graph: repeated Dijkstra
- Other models permit other methods
👁 Full explanation
Three loops give Θ(V³) time and Θ(V²) storage. A negative diagonal afterward identifies a negative cycle; pairs able to traverse it have no finite minimum walk distance. Warshall reachability replaces min/+ by OR/AND. Floyd’s cost is not a universal best-achievable bound for all APSP settings; sparse nonnegative graphs permit repeated Dijkstra and other models permit other methods. - Worked example Floyd–Warshall improvement retention
- D[a,b]=4; D[b,c]=2
- Initial D[a,c]=11
- Phase b: D[a,c]→6
- Later phases retain improvement
- Module reprints 11: incorrect
👁 Full explanation
Worked microexampleIf D[a,b]=4,D[b,c]=2,D[a,c]=11, phase b reduces D[a,c] to 6. Later phases must retain that improvement rather than restoring 11.
6 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Floyd–Warshall initialization and invariant
DAA29
0/1 knapsack and dominance
[Exam Focus]- 0/1 knapsack state and recurrence
- Integer capacity W
- K[i,w]: first-i maximum within capacity w
- Base: K[0,w]=0
- weightᵢ>w: K[i,w]=K[i−1,w]
- Otherwise max(K[i−1,w],valueᵢ+K[i−1,w−weightᵢ])
- Previous row: each item at most once
- Backtrack changed values: recover items
👁 Full explanation
For integer capacity W, K[i, w] is maximum value using the first i items within capacity w. Initialize K[0, w]=0. If weight_i>w, use K[i−1, w]; otherwise take max(K[i−1, w], value_i+K[i−1, w−weight_i]). The previous-row reference ensures each item is used at most once. Backtrack changed values to recover chosen items. - Knapsack complexity and dominance
- Time O(nW): pseudo-polynomial
- Binary W encoding: O(log W) bits
- Storage: O(W)
- 0/1 updates: capacities downward
- Upward updates: item reuse, unbounded variant
- Sparse states: (weight,profit)
- Dominating state: no greater weight
- Dominating state: no smaller profit
- Same remaining items required
👁 Full explanation
Time O(nW) is pseudo-polynomial because W takes only O(log W) binary input bits. Storage can be O(W); update capacities downward for 0/1 selection. Upward iteration allows reuse and solves an unbounded variant. In sparse(weight, profit) states, discard an option dominated by another with no greater weight and no smaller profit, provided both have the same remaining items. - Worked example Knapsack optimum and dominance example
- Weights 2,3,4; values 1,2,5
- Capacity W=6
- Choose weights 2+4
- Optimal value: 6
- (weight 5,profit 3) dominated
- Dominating state: (weight 4,profit 5)
👁 Full explanation
Worked microexampleWeights 2,3,4, values 1,2,5 and W=6 yield value 6 by choosing weights 2+4. A state(weight 5,profit 3) is dominated by(weight 4,profit 5).
2 related practice questions
Blueprint: DAA1, DAA2, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- 0/1 knapsack state and recurrence
DAA30
LCS and reconstruction
[Exam Focus]- LCS prefix-state recurrence
- Subsequence: order preserved, gaps allowed
- L[i,j]: prefix lengths i,j
- Empty-prefix rows/columns: 0
- Compare X[i−1] with Y[j−1]
- Match: L[i,j]=1+L[i−1,j−1]
- Mismatch: max(L[i−1,j],L[i,j−1])
- Short-note correction: prefix lengths versus indices
👁 Full explanation
A subsequence preserves order but need not be contiguous. For prefixes of lengths i, j define L[i, j]. Empty-prefix rows/columns are 0. If X[i−1]=Y[j−1], set L[i, j]=1+L[i−1, j−1]; otherwise use max(L[i−1, j], L[i, j−1]). Keep prefix lengths i and j distinct from the zero-based character indices i−1 and j−1. - LCS evaluation and reconstruction
- Increasing rows/columns
- Matching characters: diagonal reconstruction
- Otherwise follow equal-optimum neighbour
- Ties: different valid LCSs
- Time: Θ(mn)
- Full table: Θ(mn) storage
- Value-only two rows: O(min(m,n))
- Reconstruction: retained decisions or another technique
👁 Full explanation
Fill rows/columns in increasing order. Reconstruct by taking matching characters diagonally or following a neighbor with the same optimal value; ties may produce different LCSs. Time Θ(mn), table storage Θ(mn); two rows reduce value-only storage to O(min(m, n)), while ordinary reconstruction needs retained decisions or another technique. - Worked example LCS versus longest common substring
- X=ABC; Y=AC
- LCS=AC; length=2
- Substring matching: different recurrence
- Substring mismatch resets to zero
👁 Full explanation
Worked microexampleX=ABC,Y=AC: LCS is AC, length 2. Contiguous-substring matching would require a different recurrence, resetting a mismatch to zero.
1 related practice question
Blueprint: DAA2 · Note references: DAA-S, DAA-LCS
- LCS prefix-state recurrence
DAA31
Matrix-chain and optimal-BST interval DP
[Exam Focus]- Matrix-chain interval DP
- Aᵢ dimensions: p[i−1]×p[i]
- Base: M[i,i]=0
- M[i,j]=min_{i≤k<j}(M[i,k]+M[k+1,j]+p[i−1]p[k]p[j])
- Increasing interval length
- Store optimal split
- 10×30,30×5,5×60
- (AB)C: 4500; A(BC): 27000
- Time O(n³); space O(n²)
- Fixed multiplication order; variable parenthesization
👁 Full explanation
For matrix A_i of size p[i−1]×p[i], M[i, i]=0 and M[i, j]=min over i≤k<j of(M[i, k]+M[k+1, j]+p[i−1]p[k]p[j]). Fill by increasing interval length and store the split. Three matrices 10×30,30×5,5×60 cost 4500 under(AB)C versus 27000 under A(BC). Time O(n³), space O(n²); multiplication order stays fixed while parentheses change. - Optimal-BST interval DP
- Sorted-key successes pᵢ; gap failures qᵢ
- W(i,j)=Σ_{k=i}^j pₖ+Σ_{k=i−1}^j qₖ
- Comparison-count base: C(i,i−1)=0
- C(i,j)=W(i,j)+min_r(C(i,r−1)+C(r+1,j))
- Store optimal root r
- CLRS dummy-depth empty cost: qᵢ₋₁
- Final-value difference: fixed total gap weight
- Basic time O(n³); space O(n²)
👁 Full explanation
For an OBST use sorted-key success weights p_i and gap failure weights q_i. Let W(i, j)=∑p_i.. p_j+∑q_(i−1).. q_j. Under the comparison-count convention, C(i, i−1)=0 and C(i, j)=W(i, j)+min_r(C(i, r−1)+C(r+1, j)); store r. CLRS-style dummy-node depths instead initialize empty cost to q_(i−1); final values differ by the fixed total gap weight. Basic time O(n³), space O(n²).
Blueprint: DAA2 · Note references: DAA-M, DAA-INTERVAL
- Matrix-chain interval DP
DAA32
Reliability design under budget
[Exam Focus]- Reliability redundancy model
- Independent device failures
- mᵢ parallel copies; device reliability rᵢ
- Stage φᵢ(mᵢ)=1−(1−rᵢ)^mᵢ
- Series total: ∏φᵢ
- Integer copies mᵢ≥1
- Budget: Σmᵢcᵢ≤B
- Extra copies: reliability versus budget
- Correlated failures invalidate independence formula
👁 Full explanation
Assume independent device failures. With m_i parallel copies of stage i, each reliability r_i, stage reliability is φ_i(m_i)=1−(1−r_i)^m_i. Series stages multiply: total∏φ_i. Choose integers m_i≥1 with∑m_i c_i≤B; extra copies improve reliability but consume budget. Correlated failures invalidate the simple independence formula. - Reliability budget DP
- R[i,b]: first-i best within budget b
- Base: R[0,b]=1
- R[i,b]=max_m R[i−1,b−mcᵢ]φᵢ(m)
- Feasible m≥1
- Empty candidate set: 0
- Time O(stages×budget×maximum copies)
- Value storage: O(budget)
- Retain copy counts for reconstruction
👁 Full explanation
Let R[i, b] be best reliability for the first i stages within budget b. Base R[0, b]=1; maximize R[i−1, b−m c_i]φ_i(m) over feasible m≥1. Empty candidate sets give 0. Time is O(stages×budget×maximum copies), with O(budget) value storage; reconstruct retained copy counts. - Worked example Reliability allocation comparison
- Costs 30,15,20; reliabilities 0.9,0.8,0.5
- Budget 105
- Copies (1,2,2): cost 100
- Reliability: 0.9×0.96×0.75=0.648
- Copies (1,1,3): cost 105
- Reliability only 0.63
👁 Full explanation
Worked microexampleFor costs 30,15,20, reliabilities 0.9,0.8,0.5 and budget 105, copy counts(1,2,2) cost 100 and yield 0.9×0.96×0.75=0.648. Three copies of the weak last stage with the others single cost 105 but yield only 0.63.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Reliability redundancy model
DAA33
Exact TSP subset DP
[Exam Focus]- Exact TSP subset-state recurrence
- Minimum tour: every vertex once, return
- Shortest path needn't cover/return
- Fix start s
- F(S,j): minimum from s through S
- Exactly S; ending j∈S
- Base: F({s},s)=0
- F(S,j)=min_{i∈S−{j}}[F(S−{j},i)+w(i,j)]
- Finish: min_{j≠s}[F(V,j)+w(j,s)]
- Missing edges: ∞
👁 Full explanation
TSP asks for a minimum-cost tour visiting every vertex once and returning to its start; a shortest path need not visit all vertices or return. Fix start s. Let F(S, j) be minimum cost from s through exactly S, ending at j∈S. Base F({s}, s)=0. Transition F(S, j)=min_i∈S−{j}[F(S−{j}, i)+w(i, j)]. Finish with min_j≠s[F(V, j)+w(j, s)]. Missing edges cost∞. - Held–Karp costs and alternatives
- Store predecessors for tour reconstruction
- Time: O(V²2^V)
- Space: O(V 2^V)
- Improves factorial enumeration
- Still exponential
- Nearest-neighbour: heuristic, no general exactness
- Backtracking/branch-and-bound: exact TSP alternatives
- Generic method selection needs details
👁 Full explanation
Store predecessor choices to reconstruct a tour. Held–Karp uses O(V²2^V) time and O(V 2^V) space, improving factorial enumeration but remaining exponential. Greedy nearest-neighbor is a heuristic without a general exactness guarantee; backtracking and branch and bound can also solve exact TSP. Specify the problem variant and algorithm before choosing a solution method. - Held–Karp boundary conditions
- S must contain start s
- Initialize F({s},s)=0
- Impossible states: ∞
- Larger sets: endpoints j≠s
- Avoid nonexistent predecessor states
👁 Full explanation
For Held–Karp, S contains the start s. Initialize F({s},s)=0 and impossible states to infinity; for larger sets, evaluate endpoints j other than s. These boundary cases prevent using a nonexistent predecessor state.
1 related practice question
Blueprint: DAA2, DAA3 · Note references: DAA-M, DAA-N, DAA-S
- Exact TSP subset-state recurrence
DAA34
BFS, DFS, graph representations
- BFS versus DFS discovery
- BFS: mark on enqueue
- FIFO neighbour exploration
- Record predecessor and level
- Levels: minimum edge counts
- Unweighted/equal-weight shortest paths
- DFS: mark on entry
- Recursive or iterative branch completion
- Unvisited neighbour before parent resumption
- Resume parent after branch
👁 Full explanation
BFS marks a vertex when enqueued, explores neighbors with a FIFO queue and records predecessor/level. Levels give shortest paths by edge count in unweighted/equal-weight graphs. DFS marks on entry, recursively or iteratively explores an unvisited neighbor to completion, then resumes the parent. - Graph traversal conditions and costs
- Disconnected: restart each unvisited vertex
- Adjacency-list time: O(V+E)
- Auxiliary visited/queue/stack: O(V)
- Matrix scanning: O(V²)
- Exact order requires neighbour order
- Reverse DFS finish order: DAG-only topological
- Printed under DP ≠ DP optimization
👁 Full explanation
Run from each unvisited vertex for a full disconnected traversal. Adjacency lists give O(V+E) traversal time and O(V) auxiliary visited/queue/stack space; adjacency matrices give O(V²) scanning. State neighbor order before requesting one exact traversal sequence. Reverse DFS finish order gives a topological order only for DAGs. BFS/DFS being printed under a DP unit does not make ordinary traversal a DP optimization algorithm.
2 related practice questions
Note references: DAA-M, DAA-N, DAA-S
- BFS versus DFS discovery
DAA35
Articulation, bridges, biconnected components
- Articulation discovery and low values
- Removal increases connected-component count
- Undirected DFS
- disc[u]: discovery time
- low[u]: smallest reachable discovery number
- Reachability from u's subtree
- Downward tree edges; at most one back-edge
- Update from children/nonparent back edges
- Root articulation: ≥2 DFS children
- Nonroot articulation: some low[v]≥disc[u]
👁 Full explanation
An articulation vertex increases the number of connected components when removed. In an undirected DFS, disc[u] is discovery time and low[u] is the smallest discovery number reachable from u’s subtree using downward tree edges and at most one back edge. Update low from children and nonparent back edges. A root is articulation if it has at least two DFS children; a nonroot u is articulation if some child v has low[v]≥disc[u]. - Articulation, bridges, biconnected blocks
- Child cannot bypass u to ancestor
- Bridge: low[v]>disc[u]
- Block trigger: low[v]≥disc[u]
- Edge stack: pop through (u,v)
- Adjacency-list time: O(V+E)
- Vertex-biconnectivity ≠ directed strong connectivity
👁 Full explanation
Such a child cannot reach an ancestor of u without u. A bridge has the stricter condition low[v]>disc[u]. An edge stack can output a vertex-biconnected block when low[v]≥disc[u], popping through edge(u, v). With adjacency lists these checks cost O(V+E). Distinguish vertex-biconnectivity from strong connectivity in directed graphs. - Biconnected-component DFS procedure
- Simple undirected graph
- On entry: disc[u]=low[u]=++time
- Unvisited v: push (u,v), DFS(v)
- Then low[u]=min(low[u],low[v])
- Visited nonparent ancestor: disc[v]<disc[u]
- Push back edge once
- Back-edge update: low[u]=min(low[u],disc[v])
- low[v]≥disc[u]: pop through (u,v)
- Separate root-child articulation rule
- Bridge test: low[v]>disc[u]
- Restart each unvisited vertex
- Multigraph: skip parent edge by identity
- Do not skip every parent-directed edge
👁 Full explanation
For a simple undirected graph initialize disc[u]=low[u]=++time on entry. For an unvisited neighbor v, push tree edge(u,v), DFS(v), then low[u]=min(low[u],low[v]). For a visited nonparent ancestor v, push the back edge once when disc[v]<disc[u] and use low[u]=min(low[u],disc[v]). After a child returns with low[v]>=disc[u], pop through(u,v) to output one block. Keep the separate root-child articulation rule and bridge test low[v]>disc[u]. Restart DFS at each unvisited vertex. For multigraphs skip the parent edge by identity rather than skipping every edge to the parent. - Worked example Two-triangle low-link check
- Triangles A-B-C-A and C-D-E-C
- DFS order: A,B,C,D,E
- disc=(1,2,3,4,5)
- low=(1,1,1,3,3)
- Only articulation: C
- No bridges
- Blocks: {A-B,B-C,C-A}; {C-D,D-E,E-C}
- low[D]=disc[C]
- Articulation ≥ versus bridge >
👁 Full explanation
A small procedure checkTwo triangles A-B-C-A and C-D-E-C, DFS order A,B,C,D,E: disc=(1,2,3,4,5), low=(1,1,1,3,3). Only C is articulation; no edge is a bridge; stack yields blocks{A-B,B-C,C-A} and{C-D,D-E,E-C}. low[D]=disc[C] shows why articulation uses>= but bridge uses>.
Note references: DAA-M, DAA-LOW, CMU-LOWLINK
- Articulation discovery and low values
DAA36
Backtracking and safe pruning
[Exam Focus]- Backtracking candidate template
- Partial assignment x[1..k]
- For each allowed choice: assign
- Test possible extension
- Promising: recurse
- Return: undo assignment
- Report complete feasible candidates
- Stop after one: existence/single-answer request
- Explicit constraints: variable domains
- Implicit constraints: relations among choices
👁 Full explanation
Represent a partial assignment x[1.. k]. For each allowed next choice: assign it, test whether an extension remains possible, recurse if promising, and undo the assignment on return. Report complete feasible candidates; stop after one only if the task requests existence/a single answer. Explicit constraints restrict each variable’s domain; implicit constraints relate choices. - Backtracking completeness and pruning
- Consider every feasible extension
- Prune only impossible branches
- Disliked partial objective insufficient
- DFS space proportional to depth
- Total search may remain exponential
- Equivalent-state memoization reduces work
- Stronger constraints reduce work
- Branch count: actual choices/tests
👁 Full explanation
Correctness requires exhaustive consideration of every feasible extension and pruning only impossible branches. Merely disliking a partial objective is not enough. DFS recursion uses space proportional to search depth, while total search can remain exponential. Memoizing equivalent states or stronger constraints can reduce work, but branch count depends on actual choices/tests.
6 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Backtracking candidate template
DAA37
N-queens
[Exam Focus]- N-queens representation and conflict tests
- x[r]=column; one queen per row
- Earlier row i: conflict comparison
- Reject column conflict: x[r]=x[i]
- Reject diagonal: |x[r]−x[i]|=|r−i|
- Distinct rows built into representation
- Legal placement: recurse, then remove
- Column and r−column/r+column sets
- Set-based conflict tests: constant time
👁 Full explanation
Use x[r]=column for one queen per row. Reject against earlier row i when x[r]=x[i] or |x[r]−x[i]|=|r−i|; distinct rows are built into the representation. Recurse after legal placement and remove it on return. Column and r−column/r+column sets permit constant-time conflict tests. - N-queens bounds and conventions
- Distinct columns: at most n! permutations
- Additional partial-node work
- Pruning ≠ polynomial-time guarantee
- Placement/conflict storage: O(n)
- n=2,3: no solutions
- State empty-board convention
👁 Full explanation
Distinct columns leave at most n! complete permutations plus partial-node work; pruning does not guarantee polynomial time. Placement/conflict storage is O(n). Boards 2 and 3 have no solutions; state empty-board conventions. - Worked example N-queens placement examples
- n=4: (2,4,1,3) valid
- Rows 1,2; columns 2,3
- Row difference=column difference=1
- Diagonal conflict: reject partial branch
👁 Full explanation
Worked microexampleFor n=4, column vector(2,4,1,3) is valid. Rows 1 and 2 with columns 2 and 3 would share a diagonal because both differences are 1, so that partial branch is rejected.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- N-queens representation and conflict tests
DAA38
Subset sum
[Exam Focus]- Subset-sum include/exclude pruning
- Track current sum s
- Track remaining sum R
- Nonnegative weights assumption
- Prune s>target
- Prune s+R<target
- Equality: report subset
- All subsets: consider zero-weight extensions
- Sorted positives strengthen tests
- Sorting cannot force next-item inclusion
👁 Full explanation
Include/exclude each item while tracking current sum s and remaining sum R. For nonnegative weights prune s>target or s+R<target. On equality report the subset, considering zero-weight extensions if all subsets are needed. Sorting positive weights can strengthen tests but cannot force inclusion of the next item. - Subset-sum boundary assumptions and bounds
- Negative values: overshoot may recover
- Use valid attainable-range bounds
- At most 2^n subsets
- Recursion depth: O(n)
- Duplicate values: define index-distinct counting
👁 Full explanation
With negative values, s>target may recover later; use valid attainable-range bounds. There are up to 2^n subsets and O(n) recursion depth. Define whether duplicate-valued items count by index. - Worked example Subset-sum feasibility bounds example
- {3,4,5,6}; target 13
- Solution: {3,4,6}
- s=9,R=3: 12<13, failure
- s=9,R=4: equality still possible
👁 Full explanation
Worked microexampleFor{3,4,5,6}, target 13, subset{3,4,6} succeeds. At s=9 with remaining total 3, s+R=12<13 proves failure. At s=9 with remaining 4, equality can still be reached.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Subset-sum include/exclude pruning
DAA39
Graph coloring
[Exam Focus]- Fixed-m graph coloring search
- Assign colours 1…m
- Reject already-coloured neighbour's colour
- All colours fail: backtrack
- At most m^V complete assignments
- Additional conflict-checking cost
- Simple test: O(V)
- Exponential bound
- Module polynomial-looking expression: garbled
- Self-loop: proper coloring impossible
👁 Full explanation
For a fixed m, assign colors 1…m to vertices, rejecting a color used by an already colored neighbor. Backtrack when all colors fail. At most m^V complete assignments exist, with additional checking cost; a simple O(V)-per-test implementation gives an exponential bound. A self-loop makes proper coloring impossible. - Coloring decision versus optimization
- Decision: do m colours suffice?
- Chromatic number: minimum colours
- Increasing m with complete decision search
- Greedy: vertex-order-dependent colour choice
- Greedy may use too many
- No general greedy optimum proof
- Odd cycle: 3 colours
- Edge-containing bipartite graph: 2 colours
- Edgeless nonempty graph: 1 colour
👁 Full explanation
The decision question asks whether m colors suffice; optimization asks for the chromatic number. Trying increasing m with a complete decision search finds the minimum. Greedy coloring chooses a color by vertex order and may use too many; it is not a general optimum proof. An odd cycle needs 3 colors; an edge-containing bipartite graph needs 2, and an edgeless nonempty graph needs 1.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Fixed-m graph coloring search
DAA40
Hamiltonian cycles
[Exam Focus]- Hamiltonian cycle backtracking
- Fix start: eliminate rotational duplicates
- Extend to unused adjacent vertex
- At V vertices: require return edge
- Missing return edge: backtrack
- Hamiltonian: visit vertices once
- Euler: visit edges
- Fixed-start candidates: up to (V−1)!
- Polynomial checking overhead
👁 Full explanation
Fix a start vertex to avoid rotational duplicates. Extend a path with an unused vertex adjacent to its current end. At V vertices require an edge back to the start; otherwise backtrack. A Hamiltonian cycle visits vertices once, while an Euler cycle concerns visiting edges. Fixing the start leaves up to(V−1)! candidate permutations, with polynomial checking overhead. - Hamiltonian necessary conditions and TSP
- Simple undirected graph; V≥3
- Degree 1 rules out Hamiltonian cycle
- Articulation point rules out Hamiltonian cycle
- Absence of obstructions insufficient
- TSP: optimize weighted Hamiltonian tour
- Existence search alone doesn't minimize cost
- Undirected reversal equivalence for unique enumeration
👁 Full explanation
For a simple undirected graph with at least 3 vertices, a degree 1 vertex or articulation point rules out a Hamiltonian cycle, but their absence does not prove one exists. TSP optimizes a weighted Hamiltonian tour; the decision existence search alone does not minimize its cost. Reversed undirected tours may be equivalent if enumerating unique cycles.
1 related practice question
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Hamiltonian cycle backtracking
DAA41
Branch-and-bound states and bounds
[Exam Focus]- Branch-and-bound node lifecycle and selection
- Live: generated, eligible for expansion
- E-node: currently expanded
- Dead: finished or pruned
- FIFO: queue order
- LIFO: stack order
- Least-cost/best-bound: priority queue
- Selection affects work/storage
- Valid bounds preserve exactness
👁 Full explanation
A live node is generated and still eligible for expansion; the E-node is currently expanded; a dead node is finished or pruned. FIFO selects live nodes by queue order, LIFO by stack order, and least-cost/best-bound uses a priority queue. Selection changes work/storage; valid bounds preserve exactness. - Branch-and-bound bound directions
- Minimization incumbent: feasible upper bound U
- Partial lower bound L: every completion
- One optimum/value: prune L≥U
- Maximization incumbent: feasible lower bound
- Optimistic completion: upper bound
- Maximization prune: upper≤incumbent
- All optima: retain equality branches
👁 Full explanation
For minimization, an incumbent feasible solution supplies an upper bound U; a partial node supplies a lower bound L on every completion. Prune if L≥U when only one optimum/value is needed. For maximization, feasible profit is a lower bound and an optimistic completion estimate is an upper bound; prune if upper≤incumbent. Keep equality branches when all optimal solutions must be enumerated.
2 related practice questions
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Branch-and-bound node lifecycle and selection
DAA42
Knapsack branch and bound
[Exam Focus]- Knapsack fractional-relaxation bound
- Positive weights/values
- Sort decreasing density
- Branch include/exclude
- Reject overweight nodes
- Fill remaining capacity fractionally
- Fractional fill: remaining items only
- Relaxed profit: upper bound
- Whole-item completion updates incumbent
- Fractional result ≠ legal 0/1 answer
👁 Full explanation
Sort positive-weight/value items by decreasing density and branch include/exclude. Reject overweight nodes. To bound a node’s possible profit, fill its remaining capacity fractionally from remaining items; this relaxation can only improve on 0/1 feasibility, so its value is an upper bound. A whole-item feasible completion updates the incumbent; the fractional result itself is not a legal 0/1 answer. - Knapsack branch-and-bound certificate
- Capacity 10; (6,12),(5,8),(5,8)
- Root bound: 12+(4/5)8=18.4
- First included: whole-item value 12
- First excluded: other two value 16
- All live upper bounds≤16: optimality
- Avoid downward floating-point bound rounding
- Worst-case search: exponential
👁 Full explanation
With capacity 10 and items(6,12),(5,8),(5,8), the root fractional bound is 18.4: take the first and 4/5 of the second. The first-item-in branch has whole-item value 12; excluding it permits the two other items, value 16. Continue until every live upper bound is≤16 to certify optimality. Avoid downward floating-point rounding that could invalidate the bound; worst-case search remains exponential.
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S
- Knapsack fractional-relaxation bound
DAA43
TSP matrix-reduction branch and bound
[Exam Focus]- Directed-TSP matrix-reduction bound
- Diagonal/forbidden entries: ∞
- Subtract finite row minima
- Then subtract finite column minima
- Accumulate reductions
- Tour: one entry per row/column
- Reduction sum: lower bound
- Relaxed assignment may contain disjoint subtours
👁 Full explanation
For directed TSP, set diagonal/forbidden entries to∞. Subtract each finite row minimum, then each finite column minimum, accumulating reductions. Every tour uses one entry per row/column, so their sum is a lower bound; the relaxed assignment may contain disjoint subtours. - TSP include-edge reduction and search
- Include i→j: remove row i/column j
- Prevent premature subtours
- Reduce residual matrix
- Child bound=parent+selected reduced cost+new reductions
- Compare with best complete tour
- Expand promising live node
- Matrix zeros ≠ valid complete tour
👁 Full explanation
When including edge i→j, remove its used row/column, prevent premature subtours, reduce again and add the selected reduced-edge cost and new reductions to the parent bound. Compare bounds with the best complete tour and expand a promising live node. Never treat a reduced matrix’s zeros as proof of a complete valid tour. - TSP branching and subtour prevention
- Branch on undecided i→j
- Include: delete row i/column j
- Include bound: parent+reduced edge+new reductions
- Exclude: set entry ∞
- Exclude bound: parent+new reductions
- Forced in/out-degree at most one
- Track forced path head h, tail t
- Forbid t→h before all vertices included
- Residual required row/column without choice: infeasible
- Prune infeasible child
- Accept one complete all-vertex cycle
- Reject disjoint cycles
👁 Full explanation
Branch on an undecided edge i->j. The include child deletes row i/column j and adds its selected reduced cost plus new reductions to the parent bound. The exclude child sets that entry to infinity and adds only new reductions. Keep forced in/out-degree at most one. Track each forced path from head h to tail t and forbid t->h until the path contains every vertex; this blocks premature cycles. A required residual row/column with no finite choice is infeasible and pruned. Accept only one complete cycle through every vertex, not a set of disjoint cycles. - Worked example TSP subtour procedure check
- Forced 1→2→1 and 3→4→3
- One incoming/outgoing each: insufficient
- Two disjoint 2-cycles ≠ tour
- Forced 1→2: forbid 2→1
- Retain prohibition while path size<4
- Existing three-city bound=25
- Tour cost=25
👁 Full explanation
A small procedure checkFor four cities, cheap forced edges1->2,2->1 and3->4,4->3 satisfy one incoming/outgoing edge per city but are two disjoint2-cycles, not a tour. Once forced path1->2 is formed, forbid2->1 while fewer than4 vertices are in the path. Preserve the existing3-city reduction example: bound25 equals tour cost25.
1 related practice question
Blueprint: DAA2 · Note references: DAA-M, DAA-N, DAA-S, BYU-TSP
- Directed-TSP matrix-reduction bound
DAA44
P, NP, reductions, encoding
[Exam Focus]- P and NP definitions
- Decision problems
- P: deterministic polynomial input-bit time
- NP: polynomial-length certificates
- Polynomial-time verification
- Equivalent nondeterministic polynomial-time machine
- NP ≠ non-polynomial
- P⊆NP
- P=NP remains open
👁 Full explanation
P contains decision problems solvable deterministically in polynomial input-bit time. NP contains decision problems with polynomial-length certificates verifiable in polynomial time, equivalently solvable by a nondeterministic polynomial-time machine. NP does not mean non-polynomial; P⊆NP. Whether P=NP remains open. - Reductions, hardness, encoding size
- A≤ₚB: polynomial many-one instance transformation
- Preserve yes/no answers
- Prove B hard: known-hard A→B
- Reverse direction insufficient
- NP-complete: NP-hard and in NP
- Optimization TSP: NP-hard
- Bounded-tour decision TSP: NP-complete
- Tour/cost verification versus global-optimality certification
- O(nW): pseudo-polynomial knapsack
- Not polynomial in W's bit length
👁 Full explanation
A polynomial many-one reduction A≤p B transforms each A-instance into a B-instance preserving yes/no. To prove B NP-hard, reduce a known hard A to B, not the reverse. NP-complete means NP-hard and in NP; optimization TSP is normally called NP-hard, while its bounded-tour decision form is NP-complete. A valid proposed tour and its cost are easy to check, but certifying global optimality is another task. Pseudo-polynomial O(nW) knapsack is not polynomial in the bit length of W.
2 related practice questions
Blueprint: DAA3 · Note references: DAA-S, DAA-COMPLEXITY, DAA-REDUCTION
- P and NP definitions
DAA45
Damaged items and required clarifications
- Conditional-output damaged item
- p=10,n=5
- if(n>p) false: output skipped
- Execution terminates
- No implied feasibility/finiteness/control-flow violation
- Efficiency needs specification
- Required output needs specification
👁 Full explanation
For p=10,n=5, if(n>p) cout<<(n+p) skips output and terminates. Skipping this output does not by itself violate feasibility, finiteness or control flow. Efficiency or a missing required output needs a specification. - Missing notation and syntax clarifications
- 3n?+7n+12: missing exponent
- Precise degree undetermined
- Fixed nonnegative integer exponents: polynomial
- Stray ini/inl: repair syntax
- Redeclared n: repair syntax
- Exact counts need primitive-cost model
- Marked key cannot replace missing clarification
👁 Full explanation
A precise degree for 3n?+7n+12 requires the missing exponent; fixed nonnegative integer exponents still give polynomials. Use valid declarations rather than ini/inl or a redeclared n; exact counts also need a primitive-cost model. Justify the result from the specification, valid code and cost assumptions.
6 related practice questions
Note references: DAA-M, DAA-N, DAA-S
- Conditional-output damaged item
No matching topics. Clear the search or change the filter.
Blueprint learning outcomes
- DAA1 · Perform algorithm analysis using the different techniques
DAA01, DAA02, DAA03, DAA04, DAA05, DAA06, DAA07, DAA08, DAA09, DAA10, DAA11, DAA13, DAA14, DAA29 - DAA2 · Demonstrate the use of algorithm design techniques
DAA12, DAA13, DAA14, DAA15, DAA17, DAA18, DAA19, DAA20, DAA21, DAA22, DAA23, DAA24, DAA25, DAA26, DAA27, DAA28, DAA29, DAA30, DAA31, DAA32, DAA33, DAA36, DAA37, DAA38, DAA39, DAA40, DAA41, DAA42, DAA43 - DAA3 · Describe the basics of computational complexity
DAA02, DAA03, DAA04, DAA05, DAA08, DAA11, DAA29, DAA33, DAA44