CS 6515 EXAM QUESTIONS AND ANSWERS

Steps to solve a Dynamic Programming Problem - 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) - 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 - Given r = common ratio and a = first term in series CS 6515 Exam CS 6515 Exam = a + ar + ar^2 + ar^3 + ... + ar^(n-1) = a * [(1 - r^n) / (1-r)] DC: Arithmetic Series - 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 - If T(n) = aT([n/b]) + O(n^d) for constants a0, b1, d=0: