CS6515 ALGORITHMS EXAMINATION TEST 1
2026 COMPLETE QUESTIONS AND CORRECT
SOLUTIONS
◉ Why is all pairs Dist(y,z) n^2? Answer: Because it builds a two
dim table!
◉ what is the run time of bellman ford algoirthm?
How about if you had to do it for all edges? Answer: O(nm)
O(n^2m)
◉ FLoyd-Warshall run time? Answer: O(n^3)
◉ what is the base case for the bellman ford algorithm? Answer:
D(0,s,t)
◉ how does bellman ford and floyd differ when it comes to detecting
negative weight cycles? Answer: bellman == can only find it if it can
be access from the "s" or start vertex
,◉ Steps to solve a Dynamic Programming Problem Answer: 1. Define
the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a subproblem to the
main problem. (hint: use a prefix of the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time Function notation
here => T(n) = T(n/2) + 1...
◉ DP: Types of Subproblems (4) Answer: Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
Input = x1, x2, ..., xn; y1, y2, ..., ym
1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the Input.
, ◉ DC: Geometric Series Answer: Given r = common ratio and a =
first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
=> a * [(1 - r^n) / (1-r)]
◉ DC: Arithmetic Series Answer: Given d = common difference and a
= first term in series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
Sum = n/2 * [2*a + (n-1)d]
◉ DC: Solving Recurrences - Master Theorem Answer: If T(n) =
aT([n/b]) + O(n^d) for constants a>0, b>1, d>=0:
T(n) = {
O(n^d) if d > logb(a)
O((n^d)logn) if d = logb(a)
O(n^(logb(a))) if d < logb(a)
}
◉ Nth roots of Unity Answer: (1, 2*PI*j/n) for j = 0, 1, ..., n-1
2026 COMPLETE QUESTIONS AND CORRECT
SOLUTIONS
◉ Why is all pairs Dist(y,z) n^2? Answer: Because it builds a two
dim table!
◉ what is the run time of bellman ford algoirthm?
How about if you had to do it for all edges? Answer: O(nm)
O(n^2m)
◉ FLoyd-Warshall run time? Answer: O(n^3)
◉ what is the base case for the bellman ford algorithm? Answer:
D(0,s,t)
◉ how does bellman ford and floyd differ when it comes to detecting
negative weight cycles? Answer: bellman == can only find it if it can
be access from the "s" or start vertex
,◉ Steps to solve a Dynamic Programming Problem Answer: 1. Define
the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a subproblem to the
main problem. (hint: use a prefix of the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time Function notation
here => T(n) = T(n/2) + 1...
◉ DP: Types of Subproblems (4) Answer: Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
Input = x1, x2, ..., xn; y1, y2, ..., ym
1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the Input.
, ◉ DC: Geometric Series Answer: Given r = common ratio and a =
first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
=> a * [(1 - r^n) / (1-r)]
◉ DC: Arithmetic Series Answer: Given d = common difference and a
= first term in series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
Sum = n/2 * [2*a + (n-1)d]
◉ DC: Solving Recurrences - Master Theorem Answer: If T(n) =
aT([n/b]) + O(n^d) for constants a>0, b>1, d>=0:
T(n) = {
O(n^d) if d > logb(a)
O((n^d)logn) if d = logb(a)
O(n^(logb(a))) if d < logb(a)
}
◉ Nth roots of Unity Answer: (1, 2*PI*j/n) for j = 0, 1, ..., n-1
