Midterm 2 Flashcards

Question

The Karatsuba algorithm to multiply 2 integers is asymptotically optimal. True or False?

Answer 1

False It is better than the traditional method going from O(n^2) → O(n^1.585) But not the optimal solution, there exists faster algorithms

Answer 2

C) log_5(n) Describes a divide-and-conquer process where a problem of size n is recursively broken into two smaller subproblems, each of size n/5. The additional term n^3 represents the work done outside of the recursive calls at each level.

Answer 3

Dynamic programming (trees) 1. Original problem: LIS(r) = size of the largest independent set in the tree with root at r 2. Sub-problems: LIS(v) denotes the size of the largest independent set in the subtree rooted at v 3. Decision to make: Include node → exclude its children OR exclude node → can include children or not MIS(v) = max { Sum the children MIS(w), 1+ Sum all the grandchildren MIS(x)) } - w is a child or v - x is grandchildren of v - Sum of grandchildren is double sum → of children of children 4. Store the memory into a tree - Post-order traversal (visit every node before its parent?) Can make this algorithm even simpler by setting 2 functions MISyes and MISno which includes or not the node Time complexity = O(n) Brute force would be O(2^n)

Answer 4

*DP problem MISyes(v) = 1 + Sum MISno(children) MISno(v) = Sum max {MISyes(w), MISno(w)}

Answer 5

Choose non-conflicting activities with the earliest finishing time

Answer 6

Solve TOP-DOWN You may have to preprocess input to put it into greedy order (ex: sorting activities by finishing time) *Greedy requires and optimal substructure + Greedy-choice property!! Greedy-choice property = can build a globally optimal solution by making a locally optimal (greedy) choice.

Answer 7

- At the start of each iteration of the for loop, subarray A[p..k – 1] contains the k – p smallest elements of L and R in sorted order. - L[i] and R[j] are the smallest elements of L and R that have not been copied back into A. (Sentinels) Initialization: Before the first iteration: - A[p..k – 1] is empty, k = p => k – p = 0. - i = j = 1. - L[1] and R[1] are the smallest elements of L and R not copied to A. Maintenance: Case 1: L[i] <= R[j]: - By LI, A contains k – p smallest elements of L and R in sorted order. - By LI, L[i] and R[j] are the smallest elements of L and R not yet copied into A. - Line 13 results in A containing k – p + 1 smallest elements (again in sorted order). Incrementing i and k reestablishes the LI for the next iteration. Case 2: Similar arguments with L[i] > R[j] Termination: - On termination, k = r + 1. By LI, A[p..k-1], which is A[p..r], contains k-p=r–p+1 smallest elements of L and R in sorted order. - LandRtogethercontainn1 +n2 +2=r–p+3 elements including the two sentinels. All but the two largest (i.e., sentinels) have been copied in A.

Answer 8

Divide and Conquer → O(log n) Recurrence = T(n) = T(n/2) + 1

Answer 9

Base case → T(n) = O(1) for n = 1 Otherwise → T(n) = 2T(n/2) + O(n) + O(1) T(n) = O(n long n) *O(1) = time to divide O(n) = time to merge n elements 2T(n/2) = conquer the 2 subproblems

Answer 10

log n + 1 levels - height of log base 2 of n because counts the edges - Every level requires cn work cn * (log 2 n + 1) → T(n) = cn*log n + cn → O(n log n) *This assumes n is a power of 2

Answer 11

a = # subproblems (bad as it increases with each recursive call) n/b = size of each subproblem (good because shrinks with each recursive call) n^d = work done outside of recursive calls Tree has a^(log base b of n) leaves Height = log base b of n

Answer 12

We can calculate power using divide and conquer in O(log n) time

Answer 13

It can process elements in pairs, comparing them with each other first and then comparing the smaller one with the current minimum and the larger one with the current maximum. This reduces the total number of comparisons to about 3/2 (n-1) in the worst case - 1 comparison/pair for which is largest and which is smallest - 2 comparions/pair with the min or max respectively - n/2 pairs - If n is odd, the last element is compared with the max and min adding 2 comparisons

Answer 14

Let n = 2^m T(2^m) = 2* T( 2 ^ m/2 ) + 1 Let S(m) = T(2^m) S(m) = S(m/2) + 1 Ex2: T(2^m) = 2* T( 2 ^ m/2 ) + m S(m) = S(m/2) + m DON'T FORGET TO SWITCH BACK TO N (log n)

Answer 15

The fractional knapsack problem is solved using a greedy algorithm

Answer 16

FALSE It always finds the locally optimal solution, but this does not mean it is the globally optimal solution

Answer 17

Knapsack problem → DP Generate permutations → Complete search Huffman coding → Greedy Quicksort → Divide & Conquer

Answer 18

Recursive backtracking: iterating through each element in the set, adding it to a current permutation, then recursively calling the function to generate permutations with the remaining elements, and finally "backtracking" by removing the element and trying the next option at the current position before moving on to the next position in the permutation Base Case = all elements have been added to the current permutation, store the permutation as a solution and return Recursive step: For each element in the remaining set: Add the element to the current permutation. Recursively call the function with the updated permutation and the remaining set excluding the chosen element. Backtrack by removing the element from the current permutation to explore other possibilities.

Answer 19

Complete Search: 1. Start with an empty subset. 2. At each step, decide whether to include the current element. 3. Recursively explore both choices (include or exclude the element). 4. Backtrack by removing the last added element to explore new possibilities. Time complexity: - Each element can be included or not → 2^n subsets - Copying a subset takes O(n) Total = O(n*2^n) DP approach: For every subset of already existing in dp, create a new additional subset in which you just add the next element and store it in dp. Time Complexity: - 2^N subsets in total - For each element, we iterate of all existing subsets → O(n* 2^n) Space complexity → O(2^n)

Answer 20

Complete Search: base case → row == n → all the queens have been placed → add it to the solutions You are going row by row and trying the different columns for every row If valid solution → SolveQueen (row + 1, board, solutions) Backtrack (remove queen from the current board) O(n!)

Answer 21

Non-exponential reduction of problem size: The problem decreases very slowly in size, at rate n - Sum from i = 0 to k (sqrt(n^i)/4 ) About sqrt(n) level in that tree (LOTS)

Answer 22

f(n) = f(n - 1) + f(n - 2) Base cases → f(1) = 1 // f(2) = 2 Code: 1. Check base case 2. if memo.containsKey(n) → return memo.get(n) 3. result = f(n - 1) + f(n - 2) 4. memo.put(n, result) 5. return result Time complexity = O(n) (each subproblem computed once) Space complexity = O(n) (memoization table) Iterative solution: Set an array dp at which every index stores the number of ways to go up to the n level for (i = 3; i < dp.length; i++) { dp[i] = dp[i-1] + dp[i-2] } return dp[n] If we were not using DP, every step makes 2 recursive calls and recursion deapth ~ n → O(2^n)

Answer 23

T(n) = Sum from i = 0 to n [ T(i-1)xT(n-i) ] - Every number can be the root - All possibilities of right AND left subtrees with that root Base Case T(0) = 1

Answer 24

A) O(1) B) O(n) → the full array

Answer 25

A brute force approach would involve checking every single possible subsequence and returning the maximum length subsequence. 2 choices: - Include the number in the subsequence (if maintains the increasing order) → add and move to next index - Exclude the number → just move to next index Return maximum of both choices Time complexity → O(2^n) because choose for each index *Not most efficient!!

Answer 26

O (8^N) - 8 possible moves for each position - Explore up to N^2 positions as the board is NxN - Usually runs faster due to pruning (backtracking when valid move available) Check base case → return true For each position, for (i = 0; i < 8; i++) → try all 8 possible moves Call recursively → if it returns true, it leads to a solution Backtrack the current board Return false if not valid move is found O(8 ^ N^2) is better than O(N^2 !) which is the case if you take all possible paths and check that they are possible knight paths

Answer 27

- N elements are visited exaclty once (n/2 leaves) - In the worst case, each element must concat with all log(N) elements before it O (n log n) *For an unbalanced tree → O(n^2) the total work done is O(n) * O(log n) = O(n log n) if we were explicitly storing each path as a string, but counting the numbers of root-to-leaf paths is O(n) Brute force = start at the root and rcursively try all paths DP = NO OVERLAPPING SUBPROBLEMS

Answer 28

Divide each NxN matrix into 2 N/2 x N/2 matrices T(n) = 8 T(n/2) + O(n^2) - O(n^2) → work to combine the subproblems - Master's Theorem → O(n^3), not better than normal method Strassen's method: T(n) = 7T(n/2) + O(n^2) → avoid 1 multiplication

Answer 29

Recurrence relation: f(n) = max {cn + f(n-2), f(n-1)} base cases: f(1) = c1 // f(0) = 0 // f(2) = max{c1, c2} Time complexity: For every coin you have 2 choices → O(2^n) But DP avoids redundant computations, so it only traverses the array once and stores in memory → (n) (each computation takes O(1))

Answer 30

sqrt(n) > log n → Case 1 Worst case = leaves → O( n^log base b of a) → O( sqrt(n) )

Answer 31

T(n) = T(n − 1) + T(0) + O(n) Worst case: pivot is the largest/smallest element at every recursion T(n-1) → recrusviely sorting n-1 element as they were all sent to the same side of the pivot O(n) → Partition step takes linear time in this case **O(n^2) Average case: T(n) = 2T(n/2) + O(n) → O(n log n)

Answer 32

T(n) = T(n-2) + O(n-1) + O(n) ... T(n) = O(1) + O(2) + ... O(n) Sum from i=1 → n = n(n+1)/2 = O(n^2) T(n) = T(n-1) + 1: T(n) = T(n-2) + 1 + 1 ... T(n) = T(1) + (n-1)*1 = x + (n-1) T(n) = O(n)

Answer 33

12 unique solutions (generator) Naïve backtracking = O(N!) → doesn't consider symmetry of the board

Answer 34

False - Optimize the search space

Answer 35

False Ex: Fibonnacci → you replace the slots when not useful anymore F(n) = F(n-1) + F(n-2) Ex: Could rearrange 1D rolling array for knapsack/subsets instead of 2D array

Answer 36

False Base case = simplest input Termination condition = when the recursion stops