Exam 1

Question 1

What is the approach for designing a dynamic programming problem?

Answer 1

1. Define the subproblem in words and try the same problem on a prefix of the input
2. Define e recursive relation which expresses k(i) - the solution to the ith subproblem - in terms of smaller subproblems ex) k(1) … k(i-1)

Question 2

What are some example algorithms for the divide and conquering technique?

Answer 2

merge sort and solving recurrences
Euclids GCD algorithm
Multiplying n-bit integers
FFT
Median

Question 3

What is Gause’s idea?

Answer 3

It’s based on the idea that:
- multiplication is expensive
- adding and subtracting is cheap
- the product of 2 complex numbers results in 4 terms where each is multiplied with itself
- thus we need 4 real number multiplications to solve
- We can reduce these term multiplications from 4 to 3

original) Ac - bd - (bc + ad)

new) ac, bd, (a +b)(c+d)

both give us the result (a +bi)(c + di)

Question 4

How does the D&C approach work for the multiplying 2 numbers for the naive approach?
input = x, y where both are n-bit integers
output = z where z = xy?

Answer 4

Runtime is based on the number of bits in x and y

Idea is the break each of the inputs into 2 halves
- Break the input into 2 halves and solve the problems on the 2 halves recursively

ex) x = 182 to binary 10110110

X_l = 1011 = 11

X_R = 0110 = 6

182 = 11 * 2^4 + 6

General:

x = XL * 2^(n / 2) + XR

Question 5

How does the D&C approach work for the multiplying 2 numbers for the recursive approach of easy multiply? What is the runtime?
input = x, y where both are n-bit integers
output = z where z = xy?

Answer 5

partition x: XL * 2^(n / 2) + XR

partition y: = YL * 2^(n / 2) + YR

So xy = (XL * 2^(n / 2) + XR) (YL * 2^(n / 2) + YR)

Simplify it to be:

(2^n * XL * YL) + (2^(n/2))(XLYR + XRYL) + XRYR

• This results in 3 terms (multiplied with each other) and then added together to give us xy

This is the pseudocode for easymultiply(x,y)

EasyMultiply PseudoCode:
A = easymultiply(xL,yL)
B = easymultiply(xR,yR)
C = easymultiply(xL,yR)
D = easymultiply(xR,yL)

z = (2^n) * A + (2^n/2)(C + D) + B

Runtime = 4 T(n/2) + O(n) = O(n^2)

Question 6

What is the equation for the improved approach or fast multiply? What change was made?

Answer 6

We simply from 4 to 3 multiplications

(2^n * XL * YL) + (2^(n/2))(XLYR + XRYL) + XRYR

We convert the above to the following:

xy = (2^n)A + (2^n/2)(C- A - B) + B

which is now 3 terms

The run time is now:
O(n ^ log2 3)

This is from:

T(n) = 3T(n/2) + O(n)

evaluates to O(n ^ log2 3)

Question 7

What are the general forms of recurrence?

Answer 7

For:

T(n) = aT(n / b ) + O(n)

O(n ^ log b a). if a > b

O(n log n). if a = b

O(n) if a < b

Question 8

What is the name of the shortest path algorithm that finds the single source shortest path from S to any vertex? What is the input, output, and runtime? How does this algorithm work (general steps)? What is it’s limitation?

Answer 8

Dijkstra’s

Input: graph, S E V

Output: distance of Z for all vertices in the graph (Z E V)

The way works:
- Explores the graph in BFS approach
- Take O (n + m) for the BFS exploration (linear time)
- Also takes O (log n) for the min heap or priority queue for the weights

Take total time: O (n + m) * log (n)

Requires positive weights in the graph

Question 9

What are negative weight cycles in the shortest path problem and how do they affect the result?

Answer 9

They disrupt the finding of the shortest path because a walk through the cycle ends up with negative distances / weights and potentially negative infinity for these values when walking

Question 10

What is the dynamic programming idea when it comes to finding the shortest path for a single source to the vertices? What is the base and recurrence cases?

Answer 10

• We use a prefix of the result path and condition on the number of edges in the path
• The DP idea => introduce variable i ranging from 0 to n - 1 which is the number of edges that we allow on the paths

For 0 <= i <= n - 1 Z E V

Let D(i, z) = length of the shortest path from S to Z using i <= edges

Base cases:
D(0,S) = 0 the distance of S to itself
For all Z E S, D (0, Z) = infinity if no edge to Z

Recurrence case:
For i >= 1 (when i is at least 1):
If using at most i - 1 edges then
Min { D(i-1, z) , miny { D(i-1, y) + w(y,z) } }
D(i-1, z) if solution uses i - 1 edges

Try all choices for penultimate vertex y and take shortest path from s to y using i-1 edgers + the length of the last edge ( miny { D(i-1, y) + w(y,z) } )

Question 11

What is the name of the algorithm that is similar to Dijkstra’s but handles negative weight edges and negative cycles? What is the overall time complexity? What are the steps and what does it ultimately return?

Answer 11

Bellman-Ford

Time complexity: O(nm)

Steps:
Init base cases where i = 0
D(0, S) = 0

D(0, Z) = infinity for all Z E V

Then for i = 1 to n - 1
For all Z E V
Set D(i, z) = D(i - 1, z)
For y -> z E edges:
Update to D(i, z) = D(i - 1, y) + w(y,z) if it’s smaller than D(i - 1, z)

Return D(n-1, . )

Question 12

How are negative cycles detected in Bellman Ford?

Answer 12

When there’s a negative length cycle, there’s going to be shorter distance for the same vertex in the next i value which keeping shrinking over time

When there’s a negative cycle, i = n is going to smaller than i = n - 1. This shouldn’t normally happen

So how do we determine if there’s a negative weight cycle:

We compare the 2 rows n and n - 1 to see if there different - specifically if n is smaller than n - 1

Question 13

What are 2 algorithm approaches to finding all pairs shortest path for a graph with edges?

Answer 13

A. All-pairs shortest path Bellman-Ford variant

how it works:
- input a graph with vertices/edges/weights for edges

For all edge pairs in the graph y -> z, we find the shortest path by running Bellman-Ford for all S E V

Run time is O(n^2 m)

B. Floyd Warshall

Run time: O(n^3)

How it works:

For every S from 1 to n
Check every t 1 to n
If there’s an edge between s and t then base case = w(s,t) the weight s and t
Else it’s an infinity

For 1 <= i <= n
For 1 <= s <= n
For 1 <= t <= n
D(i,s,t) = min { D(i-1, s, t), D(i - 1, s, i) + D(i - 1, i, t) }

Return D(n, . , . )

We return the case where i = n (return matrix D(n . .) for all possible pair paths

Question 14

What is the difference between the 2 different all shortest paths algorithms in how they handle negative cycles?

Answer 14

All paths Belman-Ford:
Single source shortest path
Won’t always find the negative cycle because cycles may not be reachable from the start vertex

Floyd-Warshall:
All pairs shortest path
Will find the negative cycles

Question 15

What is the base case and recurse case for the Fibonacci recursive problem? What is the run time? Is this the best solution? Why or why not?

Answer 15

The recursive formula for the fibonacci problem is

Fn = Fn-1 + Fn-2 (this is true for any nth Fib that is our input)

The base case for this problem is the first two fibonacci numbers which are 0 and 1
F(0) = 0
F(1) = 1

Runtime:
T(n) <= O(1) + T(n-1) + T(n-2)

O(1.618 ^ n ) or exponential run time

This is not the most optimal solution and therefore not the best solution

Why it’ s not optimal is because we calculate the same subproblems over and over again when recursing down the tree of subproblems. We need to store the previously solved subproblems

Question 16

Describe the dynamic programming solution for the Fib numbers problem. What is the pseudocode for this problem?

Answer 16

A better solution would involve the following:
- Starting with smaller fibonacci numbers and saving the computed values for later calculation of larger values
- Using an array or hash table to store

Question 17

Name the characteristics of a dynamic programming solution for this course:

Answer 17

• no recursion
• There is no recursion in dynamic programming
  Memoization is another approach where a hash table is used to store the solutions

Question 18

What is the pseudocode for the dynamic programming solution for the Fib problem?

Answer 18

Base case: input n is equal to 0 or 1
return 0 if n = 0
return 1 if n = 1

Otherwise set each in the solution array

for i = 2 -> n
F[i] = F[i-1] + F[-2]

Return F[n]

Runtime: O(n) based on the input n

Question 19

What is a difference between a substring and a subsequence?

Answer 19

Substring = set of consecutive elements

Subsequence = set of elements in order (where skips can happen)

Question 20

What is the subproblem and the recursive relation in the LIS problem?

Answer 20

Subproblem:
L(i) = LIS in a1 … ai which includes ai

Recursive relation:

L(i) = 1 + max { L(j) where 1 <= j <= i - 1 and aj < ai }

Question 21

What is the pseudocode for the LIS problem? What is the run time?

Answer 21

for 1 -> n:
L(i) = 1
for j -> i - 1:
if aj < ai and L(i) < L(j) + 1:
L(i) = L(j) + 1

max = 1
for 2 -> n:
if L(i) > max:
max = i

return L(max)

Runtime: O(n ^ 2)

Question 22

What is the psuedocode for the LCS problem? What is the subproblem? What is the runtime?

Answer 22

Subproblem:

The subproblem is the LCS of a prefix of the input of s1..si where i < n

We need two terms i, j

Base case:

for i = 0 -> n:
L(i, 0) = 0
for j = 0 -> n:
L(0, j) = 0

for i -> n:
for j -> n:
if xi = yj:
L(i, j) = 1 + L(i - 1, j - 1)

     else: 
         L(i, j) = max { L(i, j - 1), L(i - 1, j) 

return L(n,n)

(return the last value)

runtime: O(n ^ 2)

Question 23

What is the median problem and what is the easy solution? What is the run time and name of algorithm involved?

Answer 23

Given a unsorted list A [A1…An], find the median or the n/2 smallest

other version is find the k smallest

Easy algorithm: sort A and an then output the kth element or n/2 element

merge sort can be used O (n log n)

Question 24

What is an improved solution to the find median problem? What is its pseudocode?

Answer 24

BFPRT algorithm

It’s similar to the quicksort algorithm where a pivot p is chosen

then partition A into 3 groups:
A < p
A = p
A > p

We want the median or something close to it when choosing a pivot

The difference is that we don’t have to recursively consider both sublists. We only have to search in one of these 2 lists

Quick Select Pseudocode:
- choose a pivot p close to the median

• then partition A into 3 groups:
  A < p
  A = p
  A > p
• if k <= A <p then quickselect(A < p, k)

if k > |A < p | + |A = p | then quickselect(A > p, k - 1 - |A < p| - |A=p| )

if | A < p| < k <= | A < p| + |A = p | then return p

A good pivot is chosen by:
- we approximate a median because we don’t have the original median
- we can find a pivot that satisfies or falls in the range of n/4 to 3n/4
- the worst case in the above range is
T(3n/4) + O(n) which is O(n) runtime

In fact, this is the case if our band is from n/100 to 99/100 we still can achieve O(n)

There’s exactly n/2 good pivots with a P(1/2) of choosing a good pivot. We can choose again until we have a good pivot

It takes O(n) expected time to find a good pivot and then once you find one a good pivot leads to O(n) run time for an overall O(n)

Question 25

What is the process of choosing a good pivot for the median problem?

Answer 25

A good pivot is chosen by:
- we approximate a median because we don’t have the original median
- we can find a pivot that satisfies or falls in the range of n/4 to 3n/4
- the worst case in the above range is
T(3n/4) + O(n) which is O(n) runtime

In fact, this is the case if our band is from n/100 to 99/100 we still can achieve O(n)

There’s exactly n/2 good pivots with a P(1/2) of choosing a good pivot. We can choose again until we have a good pivot

It takes O(n) expected time to find a good pivot and then once you find one a good pivot leads to O(n) run time for an overall O(n)

Steps: for finding good pivot
- Break A in n/5 groups of 5 elements each
- For each group, we sort it (takes order of 1 time)
- Choose 1 representative of each group
- Choose in a way that at least 2 of the elements are at most <= x and two of the elements are at least >= x

Example group G

G = x1, x2, x3, x4, x5

Question 26

What is the pseudocode for fast select where a good pivot is chosen? What is the run time?

Answer 26

Steps:
Find good pivot - break A into n/5 groups -> G, G2, G3.. Gn/5
For i = 1 -> n / 5 (for loop over the n/5 groups)
For the ith group we want to find the median by first sorting this group and then we take the median of these five elements where mi becomes the group median of Gi
We want to look at n/5 medians we found in step 2. Let S denote this set of n over 5 medians
We next find the median of this set S. This will be a pivot P by recursive calling the FastSelect(S, n/10) -> median of the set of S = store as P
We then use P as pivot and partition into 3 groups -> less than P, equal to P, and greater than P

Recurse on the A<p or A>p or output p

Runtime:

Breaking A into 5 groups => O(n)

Sorting a group of 5 => O(1) / group => O(n)

Run FastSelect on subset S to get partition => T(n/5)

Partition A into 3 subgroups => O(n)

Recurse over 3 subproblems => because P is a good partition, then T(3/4n)

T(n) = T(3/4n) + T(n/5) + O(n) = O(n)

Question 27

What is the knapsack problem? What the two types of Knapsack problems?

Answer 27

Problem:

Inputs: integers weights and values (weights and values are corresponding), total capacity (of the sack)

Output: the subset where we maximize the values V while keeping the weights less than or equal to the total capacity

Two versions of the knapsack problem:
A. One copy of each object - without repetition (1 copy)

B. Unlimited supply of each object - with repetition (unlimited supply

Question 28

What is the subproblem in words and the recurrence of the knapsack problem?

Answer 28

Subproblem:

K(i, b) = The max value achievable in subset S where 0 <= i <= i and 0 <= b <= B

The recurrence:

for 0 <= i <= n and 0 <= b <= B

k(i, b) = max value achievable using subset from 1 up to i and and under total weight <= b

Question 29

What is the base case , recurrence case, and pseudocode for the knapsack problem no repeat?
What is the runtime? Is it efficient?

Answer 29

Base cases:
k(0,b) = 0

k(i, 0) = 0

Recurrence cases:

for 0 to b
K(0, b) = 0

for 1 to n:
K(i, 0 ) = 0

for 1 <= i <= n

for 1 <= b <= B

    if wi <= b: 
        k(i,b) = max { 
           vi + k(i-1, b - wi), k(i - 1, b) 
        }
    else: 
        k(i,b) = k(i - 1, b)

return K(n, b)
(last value in the 2D table or bottom right)

Runtime: O(nb)

No, it’s not polynomial because it’s not a polynomial in the input size. B is just a number where the space required for it is O(log B). Thus, the input size is n and log B size. it’s an NP complete problem

Question 30

What is the knapsack with repetition pseudocode, base case, recurrence, and run time?

Answer 30

This time we only need the term b where we focus on the weight

base case:
K(b) = 0

recurrence:
K(b) = max achievable using weight b <= B

try all possibilities of the last object to add

pseudocode:

for b = 0 to B:
K(b) = 0

   for i = 1 to n: 
       if wi <= b and 
       k(b) < vi + k(b - 
       wi) then k(b) = vi 
                   \+ k(b - wi) 

return K(b)

we return the last entry of our table

We make a separate array S
Init to S[b] = 0 to start
And then when we settle into the if-then statement, we update S[b] to be i
We can then use the S set to backtrack to produce a multiset which obtains the maximum value

Runtime: O(n B); same runtime as the other knapsack problem but just smaller space complexity

Question 31

What is the goal of the chain matrix multiply problem?

Answer 31

We have 4 matrices A, B, C, D

Think of these matrices as having integer values for the entries

Goal is to compute the product of these matrices most efficiently

General problem:
given matrices A1, A2, ..An

where Ai is mi-1 * mi

What is the min cost for multiplying these matrices

input: m0, m1, … mn

output: find min cost for multiplying these matrices

All we need to determine the costs for computing is the size of these matrices

Question 32

What is the subproblem in words and the recurrence for matrix multiply?

Answer 32

Subproblem:

Defining the subproblem in words:
C(i) = min cost for computing A1…Ai (first i matrices in the input)

There are 2 params i and j where i is the start of the substring and j is the end of the substring

Recurrence for C(i, j) Base Case

Base case is when i = j and thus just computing Ai
C(i, i) = 0
These are the diagonal entries C(i, i) see above

Recurrence general case:

The recurrence (general) case is the following:
- Corresponds to computing the matrices defined by the substring from i to j
- Root of the tree is from Ai…Aj
- We are trying to find the split L
- Left subtree -> Ai … AL
- Right subtree -> AL+1 … Aj
- We try all possibilities for the index L for the split and then we look up in our table the minimum cost for computing the left subtree (corresponding to a smaller substring) - we do the same for the right subtree

-We combine these together
- Left matrix mi-1 * mL
- Right matrix mL * mj

Total cost of the split of the split at index L is the following:
( Mi-1 * ML * Mj ) + C(i, L) + C(L+1, j)

root -> ( Mi-1 * ML * Mj )
left subtree -> C(i, L)
right subtree -> C(L+1, j)

Ps

Question 33

What is the pseudocode for matrix multiply?

Answer 33

for i -> n
C(i,i) = 0

for 1 <= s <= n - 1
for 1 <= i <= n - s
j = i + s
c(i, j) = infinity
for l = i -> j - 1
current = mi-1mlmj + C(i, l) + C(l+ 1, j)
if C(i,j) > curent:
C(i,j) = curent

return C(L,n)

Total run time is O(n ^ 3) given the 3 nested for loops

Question 34

You and a friend are going on a road trip to your new school across the country along a set route. Since you have hardly seen the world, you also want to make the most of this trip. Along your route you have a series of possible sites to visit, recorded in array D in order as di = distance the ith site is from home along the route, and the Coolness factor array C where ci = coolness of the ith site. However, because you are in a rush to get there before the start of school, you’ve agreed to only stop at a site once every 300 miles or more.

Design a DP solution to maximize the Coolness of your trip.

Input: Distance array D [d1, d2, … , dn], and Coolness array C [c1, c2, … , cn], both of positive integers.

Output: Maximum Coolness possible from the trip

Question: Define the entries of your table in words, E.g. T(i) or T(i,j) is..

Answer 34

Let T(i) = maximum coolness of a trip up to and including the ith site.