Finals

Question 1

Dynamic Programming Longest Palindrome

What are the base and recursive cases?

Answer 1

Base Case:

• i == j
  
  • return {i}
• i == j-1 && A[i] == A[j]
  
  • return {i,j}

Recursive Cases:

• A[i] == A[j]
  
  • recursively search S = A[i+1…j-l]
  • return {i} U S {j}
• A[i] != A[j]
  
  • recursively search s₁ = A[i…j-l]
  • recurisvely search s₂ = A[j+1…j]
  • returns max of s₂, s₁

Question 2

Dynamic Programming Longest Palindrome

What does i and j refer to?

What does subProbSols[i][j] refer to?

What location returns the optimal solution?

Answer 2

i refers to the start of the section we are reviewing, j refers to the end

in our two dimensional table, the first index refers to i value, second index refers to j value

subprobSols[i][j] refers to optimal solution to subproblem A[i…j]

subprobSols[0][n-1] refers to the optimal sol for A[0…n-1]

Question 3

Dynamic Programming Longest Palindrome

In the bottom up first what are the first cases filled out?

Answer 3

subprobSols[0][0] = {0}

all the way through to:

subprobSols[n-1][n-1] = {n-1}

then look

0-1

1-2

…

0-2

1-3

…

Question 4

What is the run speed of longest palin buttom up

Answer 4

Theta of n²

Question 5

Dynamic Programming Longest Palindrome

What is the overlappin subproblems property

Answer 5

Question 6

Dynamic Programming 0-1 knapsack

What is the speed?

Answer 6

O(nk)

n = num of items

k = capacity

Fast, as long as k into too large

if k is O(n²) then nk is O of (n³)

Question 7

Dynamic Programming 0-1 knapsack

What are the base and recursive cases?

Answer 7

Base Cases:

• n == 1
  
  • If n fits, put it in
  • if n doesn’t fit return 0

recursive cases:

• if I[n][0] is > K then the answer is recursive(I,k,n-1)
• otherwise
  
  • bestWithoutItemN = recursive(I,k,n-1);
  • bestWithItemN = I[n][1] + recursive(i,k-I[n][0],n-1);
  • return the max

Question 8

Dynamic Programming 0-1 knapsack

How is the table set up?

What does i keep track of of?

What does j keep track of?

Answer 8

first index i keeps track of which item we are considering (starting at n down to 1)

second index j keeps track of the remaining capacity (starts at k, down to 0)

Question 9

Dynamic Programming 0-1 knapsack

How do we decide what value to put in table entry?

Where is the answer located?

Answer 9

w(i,j) is exactly the value that we want to store in entry [i][j] of the table

The answer is in w(n,k)

we use the same formula:

w(i,j):

• if i =1
  
  • it either fits (v_i) or it doesn’t, 0
• i > 1
  
  • s_i>j so the answer must be in w(i-1,j)
  • s_i<=j so the answer is
    
    • the bigger of the two w(i-1,j) or v_i+w(i-1,j-s_i)

Question 10

Dynamic Programming 0-1 knapsack

What is the table filling order, what are the base cases to fill in?

Answer 10

Fill the table in order

sol[0][0] is item 0 with cap 0

sol[0][1] is item 0 with cap 1

sol[1][0] best of so far with cap 0, etc

Question 11

Dynamic Programming 0-1 knapsack

What is the speed of bottom up

Answer 11

Theta of (nk)

Question 12

Dynamic Programming 0-1 knapsack

How would the solutions table be implemented (code)

Answer 12

capacity = k

we need a decision table that represents if that item is in the opt sol (true, false)

We use that table to build the rest.

for(int i = n-1; i>=0; i–){

if(decision[i][capacity] == true){

solution[i] = true;

capacity = capacity - I[i][0];

}else{

solution[i] = false;

}

Question 13

What is the definition of Expectation of T?

Answer 13

Expectation of T is the sum of each probabiltiy mult by it’s lines of code.

Question 14

What is a randomiszed algo?

Answer 14

An algorithm whose execution is determined in part by a source of random bits

Question 15

In general what is the Las Vegas algo

Answer 15

It outputs an answer that is always correct

It’s run time depends on a randomness, but they most often run fast

Question 16

What is the Monte Carlo algo?

Answer 16

Is an algo that always runs fast (it’s speed isn’t dependant on a random variable)

But the answer may not be correct, or may be close to correct.

Question 17

What is Freivalds random algo for verifying matrix multiplications

Answer 17

1. repeate M times
   
   1. choose an n x 1 binary matrix r uniformly at random:
      
      1. Each entry r_i is 0 with probability 1/2 and 1 with prob 1/2
      2. Comput A*B*r, compute C*r, then check if they are equal
         
         1. If not equal immediately output C != AB and stop
   2. After m’th iteration output “yes, C=AB”

Question 18

Verifying Matrix mults

what is the run speed?

Answer 18

Question 19

Divide and Conquer

What is merge sort’s divide, conquer and combine?

What is it’s formula and run speed?

Answer 19

Divide:

Partition A into two subarrays: A[0…n/2] and A[n/2+1…n-1]

Conquer:

Recursively sort each subarray using MergeSort

Combine:

Merge the two sorted subarrays into one sorted array, by repeatedly comparing the smalles from each subarray

Question 20

Graphs:

What is the cost to brute force?

How fast is Prim’s?

How fast is Kruskals?

Answer 20

Brute : n^n-2

Prim and Kruskal = O(ElogV)

Question 21

Matrix Multiplication

What is the divide, conquer and combine for naive and Stressen’s?

What is the speed of naive, divide and conquer and Strassens?

Answer 21

Divide: Part A&B in 4 n/2-by-n/2 matrices

Conquer: recursively computer 8 matrix mults of size n/2-by-n/2

Combine: Use 4 matrix additions to computer the n/2-by-n/2 matries c11, c12,c21,c22

Base case: when A and B are 1-by-1 matrices, return A11B11

Question 22

Matrix Mult

How are they multiplied?

Answer 22

Question 23

Half-Plane Intersection

Given a convex polygon P and a half-plane h, the intersection is either:

Answer 23

Question 24

What is the cost of half-plane brute force?

Answer 24

Question 25

What is the divide, conquer and combine of half-plane?

Answer 25

Divide: Partition the set H into two sets H₁ and H₂ with equal size n/2

Conquer: Recursively compute the intersection of each set H1 and H2. This will return two convex polygons P1 and P2

Combine: Computer the intersection of P1 and P2

Base:cse single-half-plane, just return it

Question 26

Whats the general idea of the half-plan intersection algo?

Answer 26

Question 27

Advance P or Q?

Answer 27

Question 28

What is the speed and formula for Half-Plane?

Answer 28

Question 29

What is proof for greedy choice property with the coins?

Answer 29

Question 30

What is needed for Dynamic Programming to be a good candidate for a solution?

Answer 30