Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Graduate Algorithms > Exam 1 - Dynamic Programming > Flashcards

Exam 1 - Dynamic Programming Flashcards

1
Q

What’s the general strategy for finding a DP solution?

A

Define the subproblem in words
State the recursive relation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What’s the difference between a subsequence and a substring?

A

A substring is consecutive elements, a subsequence is just in increasing order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the LIS algorithm?

A

It takes an array a of n numbers and finds the length of the longest increasing subsequence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the subproblem of the LIS algorithm?

A

L(i) = length of LIS in a_1, … , a_i that includes a_i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Why does the subproblem of the LIS algorithm include the condition that the LIS for L(i) includes a_i?

A

it keeps the subproblem from getting stuck on a suboptimal solution for an earlier value of i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the recursive relation for LIS?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Given this recursive relation for LIS, what is the algorithm to find the LIS for a?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Given this algorithm for LIS, what is its runtime?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the LCS algorithm?

A

Given two input strings X and Y, it finds the longest string which is a subsequence of both X and Y

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the subproblem of the LCS algorithm?

A

For i and j where 0 <= i or j <= n, let L(i,j) = length of LCS in x_1, … , x_i and y_1, … , y_j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the base cases of the LCS algorithm recurrence?

A

L(i,0) = 0 for all i
and
L(0,j) = 0 for all j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

For LCS, in the case that x_i = y_j , what is the recurrence?

A

L(i,j) = 1 + L(i-1, j-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

For LCS, in the case that x_i != y_j, what is the recurrence?

A

L(i,j) = max { L(i-1,j) , L(i, j-1) }

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

For LCS, in the case that x_i != y_j, why doesn’t the max include a branch of L(i-1,j-1)?

A

Because L(i-1,j-1) can be reached by either L(i-1,j) or L(i,j-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Given this recurrence of LCS, what is an algorithm for it?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Given this algorithm for LCS, what is its runtime?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How can we extract the chars of the LCS from the L(i,j) table generated by the LCS algorithm?

A

Start at the max L(i,j), and find where i and j both decrement to a smaller L(i,j) value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the inputs to the knapsack algorithm?

A

n objects
with integer weights w_1, … , w_n
and integer values v_1, … , v_n

and total capacity B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the goal of the knapsack algorithm?

A

Find subset S of objects that:
fit in backpack – total weight <= B
maximizes total value

20
Q

What is the subproblem for nonrepeating knapsack?

A
21
Q

Given this subproblem for nonrepeating knapsack, what is the recurrence?

A
22
Q

What are the base cases for the nonrepeating knapsack recurrence?

A

k(0,b) = 0 for all b
k(i,0) = 0 for all objects i

23
Q

Given this recurrence for nonrepeating knapsack, what is the algorithm?

A
24
Q

Given this algorithm for nonrepeating knapsack, what is its runtime?

A
25
Q

Why is nonrepeating knapsack not efficient?

A

The running time is not polynomial on the input size.

Because as B is incremented, its size increments by logB, so an efficient algorithm would be O(n log(B)), whereas nonrepeating knapsack is O(nB)

26
Q

What is the subproblem for repeating knapsack?

A
27
Q

Given this subproblem for repeating knapsack, what is the algorithm?

A
28
Q

If I have two matrices,
W of size a x b
and Y of size b x c
How many multiplication operations are needed to calculate Z = W x Y?

A

Calculating each element in Z requires b multiplications, and Z is of size a * c, so calculating Z takes:

a * c * b multiplications

29
Q

What is the input for the Chain Matrix Multiplication algorithm?

A

m_0 , … , m_n

Because we’re finding the cost of multiplying A_1, …, A_n, and A_i is of size m_(i-1) x m_i

30
Q

What is the base case of the recurrence for Chain Matrix Multiplication?

A

c(i,j) where i = j is 0, because no computation is needed

31
Q

What is the general case of the recurrence for Chain Matrix Multiplication?

A
32
Q

Given this recurrence for Chain Matrix Multiplication, what is the algorithm?

A
33
Q

Given this algorithm for Chain Matrix Multiplication, what is the runtime?

A
34
Q

What’s the difference between the output of the Bellman-Ford algorithm and the Floyd-Warshall algorithm?

A

Bellman-Ford gives the shortest path distance for every vertex from a given source vertex, whereas Floyd-Warshall gives the shortest path distance for every vertex from every other vertex

35
Q

In a directed graph with no negative weight cycles, the shortest path from one vertex to another visits every vertex no more than ____

A

once

36
Q

What is the subproblem in the Bellman-Ford algorithm?

A
37
Q

What is the base case of the recurrence in the Bellman-Ford algorithm?

A
38
Q

What is the recurrence for the Bellman-Ford algorithm?

A
39
Q

Given the recurrence for the Bellman-Ford algorithm, what is the pseudocode?

A
40
Q

Given the pseudocode for the Bellman-Ford algorithm, what is the runtime?

A
41
Q

How do you find a negative weight cycle with the table generated by the Bellman-Ford algorithm?

A

If D(n,z) < D(n-1, z) for any z in V, there’s a negative weight cycle

42
Q

What is the subproblem for the Floyd-Warshall algorithm?

A
43
Q

What is the base case for the recurrence of the Floyd-Warshall algorithm?

A

D(0,s,t) = w(s,t) if there is an edge from s to t , infinity if not

44
Q

What is the general recurrence of the Floyd-Warshall algorithm?

A
45
Q

Given the recurrence of the Floyd-Warshall algorithm, what is the psuedocode?

A
46
Q

Given the pseudocode of the Floyd-Warshall algorithm, what is the runtime?

A
47
Q

How do you detect negative weight cycles in the Floyd-Warshall algorithm?

A

There is one if any D(n,y,y) < 0 for any y

Graduate Algorithms (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions