CS 6515 Final Review Questions and Correct Answers the Latest Update

D&C Steps 1. Figure out your Black Box if needed. ○ Sorted = Binary Search (usually) ○ Unsorted = Merge sort (usually) ○ Polynomials, convolution, multiplication = FFT(usually) 2. State the Modification if needed. You may use the blackbox as is. ○ Which part of the black box you are changing. ○ What are your inputs and outputs to the black box. 3. State the steps of your algorithm. ○ NO PSEUDOCODE - use words ○ Must include base case(s) if needed. ○ Always return what the problem asks for. 4. Prove Correctness ○ Proof in words of why this algorithm solves the problem. ○ Prove the base case ○ The decision to select left or right in a Binary Search. ○ Prove that the problem gets smaller. 5. Analyze the runtime. ○ Can explain in words. ○ Can use black box runtime. Must include modifications' run time. ○ Can use Master Theorem. DP Steps Steps: 1. Find the subproblem. ○ State your ranges (not required) ■ For 1 ≤ i ≤ n Examify | OnlineExams | TestPrep | StudyResources | AcademicSuccess | ExamPreparation | QuizTime | LearningTools | Education | StudentSupport Smart Grades Latest update 1 ○ Define the subproblem in words. ○ Define the problem on ith item. ■ T(i) or T(i, j) is ... ○ Possibly add a constraint such as include last element ■ T(i) is ... that includes x[i]. ○ Might be different than what the overall question asks. ○ For example, a True/False final answer can usually be set up with Min/Max first and then checked at the end. ■ T(i) or T(i, j) is the maximum ... 2. Find the recurrence. ○ Must include base case(s) if needed ■ T(0) = ... ○ State your ranges ■ For 1 ≤ i ≤ n ○ Define the current problem as a relationship of smaller subproblems. ■ T(i) in terms of T(i-1) ■ T(i, j) in terms T(i-1, j), T(i, j-1), and/orT(i-1, j-1) 3. Pseudocode for algorithm. ○ No real code allowed. ○ Must include base case(s) if needed. ○ Always return what the problem asks for. ○ May be a different return from the subproblem definition. 4. Analyze the runtime. ○ Can annotate code with each runtime and compute at the end. ○ Can explain in words. ○ Include all non trivial (arithmetic) lines Master Theorem T(n) = aT(n/b) + O(n^d) -T(n) is O(n^d) if d logb(a) Examify | OnlineExams | TestPrep | StudyResources | AcademicSuccess | ExamPreparation | QuizTime | LearningTools | Education | StudentSupport Smart Grades Latest update 1 -T(n) is O(n^d * log (n)) if d = logb(a) -T(n) is O(n^(logb (a))) if d logb(a) a = number of recursive calls b = size of partition in each recursive call n^d = effort at each recusion DP & D&C Blackboxes Binary Search - O(log n) - Cuts in half each time Merge Sort - O(n log n) FFT - O(n log n) Merge Sort function mergesort(a[1 . . . n]) Input: An array of numbers a[1 . . . n] Output: A sorted version of this array if n 1: return merge(mergesort(a[1 . . . n/2]),mergesort(a[n/2 + 1 . . . n])) else: return a function merge(x[1 . . . k], y[1 . . .l]) if k = 0: return y[1 . . .l] if l = 0: return x[1 . . . k] if x[1] ≤ y[1]