FINAL - algorithms/proofs

Question 1

Integer multiplication solution

Answer 1

(see notebook) Should be XY = a function of I1, I2, I3…

Question 2

Integer multiplication running time

Answer 2

n^(lg 3)

Question 3

Draw the logic for maximum subarray (non-DP)

Answer 3

(see notebook…arrows coming out from middle element on combine step)

Question 4

Write the recurrence for the MCM problem

Answer 4

(see notebook…m[i, k] + …)

Question 5

MCM Pseudocode

Answer 5

(see notebook: MCM(p) )

Question 6

BFS pseudocode

Answer 6

(see notebook: BFS(G, s) )

Question 7

DFS pseudocode

Answer 7

(see notebook: DFS(G) and DFS-VISIT(u) )

Question 8

How do you implement topological sort?

Answer 8

Run DFS on the graph. As each vertex is finished, insert it at the FRONT of a linked list. Return this list when done, which contains the topological sorted nodes

Question 9

Strongly-Connected Components pseudocode

Answer 9

(see notebook: SCC(G) )

Question 10

Prim’s algorithm pseudocode

Answer 10

(see notebook: Prim(G, w, r) )

Question 11

Dijkstra’s algorithm pseudocode

Answer 11

(see notebook: Dijkstra(G, s) )

Question 12

Interval coverage proof

Answer 12

(see notebook)

Question 13

CLIQUE NPC proof

Answer 13

(see notebook)

Question 14

LCS recurrence

Answer 14

(see notebook: c[i, j] = ….)

Question 15

LCS pseudocode

Answer 15

(see notebook: LCSLength(X, Y) )

Question 16

PrintLCS pseudocode

Answer 16

(see notebook: PrintLCS(b, X, i, j) )

Question 17

ASP proof

Answer 17

(see notebook)

Question 18

INDEPENDENT SET NPC proof

Answer 18

(see notebook: TODO)

Question 19

Making Change pseudocode

Answer 19

(see notebook: MC(n) )

Question 20

Max subarray (DP) pseudocode

Answer 20

(see notebook: MaxSubarray(A) )

Question 21

Rod-cutting recurrence

Answer 21

(see notebook: mv[n] = …)

Question 22

Knapsack recurrence

Answer 22

(see notebook: V[i, j] = …)