CS 6515 ALGORITHMS UPDATED ACTUAL EXAM QUESTIONS CORRECT ANSWERS GRADED
A PLUS
Question:
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.
Question:
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)]
Question:
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]
Question:
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) }
A PLUS
Question:
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.
Question:
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)]
Question:
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]
Question:
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) }
