CS 6515 — FINAL EXAM TAKE-HOME |
PRACTICE QUESTIONS 1–100 AND
WORKED SOLUTIONS | 2026 UPDATED
Introduction
CS 6515, Graduate Algorithms, at the Georgia Institute of Technology focuses on
designing, analyzing, and proving the correctness and efficiency of algorithms. This
practice question bank is intended for students preparing for a take-home final or
comprehensive graduate-level algorithms assessment. It emphasizes mathematical
reasoning, algorithm selection, runtime analysis, correctness proofs, and the ability to
apply theoretical concepts to unfamiliar problems.
The questions cover major graduate algorithms topics, including divide-and-conquer,
graph algorithms, greedy methods, dynamic programming, network flows, linear
programming, computational complexity, reductions, and approximation algorithms.
Each problem includes four answer options and a worked rationale explaining the
underlying reasoning and common pitfalls.
Use this bank to practice identifying the right algorithmic technique, justifying why it
works, and deriving its time complexity. For proof-oriented problems, focus on the
structure of the argument rather than memorizing the result. For computational
problems, write out the recurrence, invariant, or reduction before selecting an answer.
These are original study questions aligned with common graduate algorithms topics,
not verified copies of Georgia Tech’s actual take-home final. Confirm the current
course syllabus and assessment instructions for the precise scope of your exam.
Core domains tested
1.
Divide-and-conquer: Recurrences, merge-based algorithms, and asymptotic
analysis.
2.
3.
Greedy algorithms: Exchange arguments, scheduling, spanning trees, and
optimal local choices.
4.
5.
, Dynamic programming: State design, recurrence formulation, optimal
substructure, and reconstruction.
6.
7.
Graph algorithms: BFS, DFS, shortest paths, topological ordering, and
strongly connected components.
8.
9.
Network flow and matching: Max-flow/min-cut, residual graphs, augmenting
paths, and bipartite matching.
10.
11.
Linear programming: Formulations, duality, feasibility, and optimization.
12.
13.
NP-completeness and reductions: P, NP, NP-hardness, NP-completeness, and
polynomial-time reductions.
14.
15.
Approximation algorithms: Approximation ratios, greedy approximations, and
performance guarantees.
16.
17.
Randomized algorithms: Expected running time, probability, and randomized
analysis.
18.
19.
Algorithm correctness and complexity: Induction, loop invariants, proof
techniques, and worst-case bounds.
20.
QUESTIONS 1–100
,Divide-and-conquer and asymptotic analysis
Q1: An algorithm satisfies \(T(n)=3T(n/2)+\Theta(n)\), with \(T(1)=\Theta(1)\). What
is its asymptotic running time?
A) \(\Theta(n)\)
B) \(\Theta(n\log n)\)
C) \(\Theta(n^{\log_2 3})\)
D) \(\Theta(n^2)\)
Rationale: The Master Theorem compares \(f(n)=\Theta(n)\) with \(n^{\log_b
a}=n^{\log_2 3}\). Since \(n\) grows polynomially slower than \(n^{\log_2 3}\), Case
1 gives \(\Theta(n^{\log_2 3})\). Option A ignores recursive work, B would apply to a
recurrence such as \(2T(n/2)+\Theta(n)\), and D overestimates the growth.
Q2: Consider \(T(n)=2T(n/2)+\Theta(n\log n)\). Assuming \(n\) is a power of two,
what is the tight asymptotic bound?
A) \(\Theta(n)\)
B) \(\Theta(n\log n)\)
C) \(\Theta(n\log^2 n)\)
D) \(\Theta(n^2)\)
Rationale: At each recursion level, the nonrecursive work totals
\(\Theta(n\log(n/2^i))\). There are \(\Theta(\log n)\) levels, and summing these
decreasing logarithmic costs gives \(\Theta(n\log^2 n)\). Options A and B omit the
accumulated work across levels, while D is too large.
Q3: A recurrence is \(T(n)=T(n-1)+\Theta(n)\), with constant base cost. What is its
tight running time?
A) \(\Theta(n)\)
B) \(\Theta(n^2)\)
C) \(\Theta(n\log n)\)
D) \(\Theta(2^n)\)
Rationale: Expanding gives a sum proportional to \(n+(n-1)+\cdots+1\), which is
\(\Theta(n^2)\). A would require constant work per level, C does not match the
arithmetic sum, and D would require exponential branching or comparable
exponential work.
, Q4: An algorithm divides an input into two subproblems of size \(n/2\), spends
\(\Theta(1)\) combining their results, and performs constant base work. What is its
running time?
A) \(\Theta(n)\)
B) \(\Theta(n)\)
C) \(\Theta(n\log n)\)
D) \(\Theta(n^2)\)
Rationale: The recurrence is \(T(n)=2T(n/2)+\Theta(1)\). Since \(n^{\log_2 2}=n\)
dominates the constant combine cost, the solution is \(\Theta(n)\). Option C would
require linear combine work at every level. A and B are intentionally equivalent here;
this question has duplicate correct options and is therefore flawed as a single-answer
assessment item. The intended answer is \(\Theta(n)\).
Q5: A divide-and-conquer algorithm has recurrence \(T(n)=4T(n/2)+\Theta(n^2)\).
What is the tight bound?
A) \(\Theta(n)\)
B) \(\Theta(n^2)\)
C) \(\Theta(n^2\log n)\)
D) \(\Theta(n^3)\)
Rationale: Here \(n^{\log_2 4}=n^2\), equal to the nonrecursive term. The balanced
Master Theorem case gives \(\Theta(n^2\log n)\). Option B omits the logarithmic
factor, while A and D do not match the recurrence’s growth.
Q6: Suppose \(f(n)=O(g(n))\) and \(g(n)=O(h(n))\). Which conclusion necessarily
follows?
A) \(h(n)=O(f(n))\)
B) \(f(n)=\Theta(h(n))\)
C) \(f(n)=O(h(n))\)
D) \(g(n)=\Omega(f(n))\) only if all functions are equal
Rationale: Big-O is transitive: constants bounding \(f\) by \(g\) and \(g\) by \(h\) can
be multiplied to bound \(f\) by \(h\). The reverse bound in A is not guaranteed, and B
requires a matching lower bound. D is false because \(f(n)=O(g(n))\) already implies
\(g(n)=\Omega(f(n))\) under the standard asymptotic definitions.
PRACTICE QUESTIONS 1–100 AND
WORKED SOLUTIONS | 2026 UPDATED
Introduction
CS 6515, Graduate Algorithms, at the Georgia Institute of Technology focuses on
designing, analyzing, and proving the correctness and efficiency of algorithms. This
practice question bank is intended for students preparing for a take-home final or
comprehensive graduate-level algorithms assessment. It emphasizes mathematical
reasoning, algorithm selection, runtime analysis, correctness proofs, and the ability to
apply theoretical concepts to unfamiliar problems.
The questions cover major graduate algorithms topics, including divide-and-conquer,
graph algorithms, greedy methods, dynamic programming, network flows, linear
programming, computational complexity, reductions, and approximation algorithms.
Each problem includes four answer options and a worked rationale explaining the
underlying reasoning and common pitfalls.
Use this bank to practice identifying the right algorithmic technique, justifying why it
works, and deriving its time complexity. For proof-oriented problems, focus on the
structure of the argument rather than memorizing the result. For computational
problems, write out the recurrence, invariant, or reduction before selecting an answer.
These are original study questions aligned with common graduate algorithms topics,
not verified copies of Georgia Tech’s actual take-home final. Confirm the current
course syllabus and assessment instructions for the precise scope of your exam.
Core domains tested
1.
Divide-and-conquer: Recurrences, merge-based algorithms, and asymptotic
analysis.
2.
3.
Greedy algorithms: Exchange arguments, scheduling, spanning trees, and
optimal local choices.
4.
5.
, Dynamic programming: State design, recurrence formulation, optimal
substructure, and reconstruction.
6.
7.
Graph algorithms: BFS, DFS, shortest paths, topological ordering, and
strongly connected components.
8.
9.
Network flow and matching: Max-flow/min-cut, residual graphs, augmenting
paths, and bipartite matching.
10.
11.
Linear programming: Formulations, duality, feasibility, and optimization.
12.
13.
NP-completeness and reductions: P, NP, NP-hardness, NP-completeness, and
polynomial-time reductions.
14.
15.
Approximation algorithms: Approximation ratios, greedy approximations, and
performance guarantees.
16.
17.
Randomized algorithms: Expected running time, probability, and randomized
analysis.
18.
19.
Algorithm correctness and complexity: Induction, loop invariants, proof
techniques, and worst-case bounds.
20.
QUESTIONS 1–100
,Divide-and-conquer and asymptotic analysis
Q1: An algorithm satisfies \(T(n)=3T(n/2)+\Theta(n)\), with \(T(1)=\Theta(1)\). What
is its asymptotic running time?
A) \(\Theta(n)\)
B) \(\Theta(n\log n)\)
C) \(\Theta(n^{\log_2 3})\)
D) \(\Theta(n^2)\)
Rationale: The Master Theorem compares \(f(n)=\Theta(n)\) with \(n^{\log_b
a}=n^{\log_2 3}\). Since \(n\) grows polynomially slower than \(n^{\log_2 3}\), Case
1 gives \(\Theta(n^{\log_2 3})\). Option A ignores recursive work, B would apply to a
recurrence such as \(2T(n/2)+\Theta(n)\), and D overestimates the growth.
Q2: Consider \(T(n)=2T(n/2)+\Theta(n\log n)\). Assuming \(n\) is a power of two,
what is the tight asymptotic bound?
A) \(\Theta(n)\)
B) \(\Theta(n\log n)\)
C) \(\Theta(n\log^2 n)\)
D) \(\Theta(n^2)\)
Rationale: At each recursion level, the nonrecursive work totals
\(\Theta(n\log(n/2^i))\). There are \(\Theta(\log n)\) levels, and summing these
decreasing logarithmic costs gives \(\Theta(n\log^2 n)\). Options A and B omit the
accumulated work across levels, while D is too large.
Q3: A recurrence is \(T(n)=T(n-1)+\Theta(n)\), with constant base cost. What is its
tight running time?
A) \(\Theta(n)\)
B) \(\Theta(n^2)\)
C) \(\Theta(n\log n)\)
D) \(\Theta(2^n)\)
Rationale: Expanding gives a sum proportional to \(n+(n-1)+\cdots+1\), which is
\(\Theta(n^2)\). A would require constant work per level, C does not match the
arithmetic sum, and D would require exponential branching or comparable
exponential work.
, Q4: An algorithm divides an input into two subproblems of size \(n/2\), spends
\(\Theta(1)\) combining their results, and performs constant base work. What is its
running time?
A) \(\Theta(n)\)
B) \(\Theta(n)\)
C) \(\Theta(n\log n)\)
D) \(\Theta(n^2)\)
Rationale: The recurrence is \(T(n)=2T(n/2)+\Theta(1)\). Since \(n^{\log_2 2}=n\)
dominates the constant combine cost, the solution is \(\Theta(n)\). Option C would
require linear combine work at every level. A and B are intentionally equivalent here;
this question has duplicate correct options and is therefore flawed as a single-answer
assessment item. The intended answer is \(\Theta(n)\).
Q5: A divide-and-conquer algorithm has recurrence \(T(n)=4T(n/2)+\Theta(n^2)\).
What is the tight bound?
A) \(\Theta(n)\)
B) \(\Theta(n^2)\)
C) \(\Theta(n^2\log n)\)
D) \(\Theta(n^3)\)
Rationale: Here \(n^{\log_2 4}=n^2\), equal to the nonrecursive term. The balanced
Master Theorem case gives \(\Theta(n^2\log n)\). Option B omits the logarithmic
factor, while A and D do not match the recurrence’s growth.
Q6: Suppose \(f(n)=O(g(n))\) and \(g(n)=O(h(n))\). Which conclusion necessarily
follows?
A) \(h(n)=O(f(n))\)
B) \(f(n)=\Theta(h(n))\)
C) \(f(n)=O(h(n))\)
D) \(g(n)=\Omega(f(n))\) only if all functions are equal
Rationale: Big-O is transitive: constants bounding \(f\) by \(g\) and \(g\) by \(h\) can
be multiplied to bound \(f\) by \(h\). The reverse bound in A is not guaranteed, and B
requires a matching lower bound. D is false because \(f(n)=O(g(n))\) already implies
\(g(n)=\Omega(f(n))\) under the standard asymptotic definitions.
