FINAL - short answer/equations

Question 1

Greedy choice property

Answer 1

The (a) greedy choice is contained in a globally optimal solution

Question 2

Optimal substructure property

Answer 2

A globally optimal solution contains globally optimal solutions to its subproblems

Question 3

Cardinality

Answer 3

The number of elements in a set

Question 4

7 steps to solve a DP problem

Answer 4

1. Define variables, 2. Express final numeric answer using variables, 3. Recurrence relation between the variables, 4. Dependency graph, 5. Figure out the order to solve the subproblems, 6. Pseudocode, 7. Reconstruct an actual optimal solution

Question 5

Answer 5

Question 6

What form does the recurrence have to take to use Master Theorem?

Answer 6

Question 7

For Master Theorem, what is the level cost?

Answer 7

Question 8

For Master Theorem, what is the # base cases?

Answer 8

Question 9

For Master Theorem, what is the # levels?

Answer 9

Question 10

For Master Theorem Case 1, what condition must be met?

Answer 10

Level cost is polynomially SMALLER than # base cases

Question 11

What is the running time T(n) for Master Theorem Case 1 (level cost is poly SMALLER than # base cases)?

Answer 11

Question 12

For Master Theorem Case 3, what condition must be met?

Answer 12

Level cost is polynomially LARGER than # base cases

Question 13

For Master Theorem Case 3, what extra condition must be met?

Answer 13

Question 14

What is the running time T(n) for Master Theorem Case 3 (Level cost is polynomially LARGER than # base cases)?

Answer 14

Question 15

For Master Theorem Case 2, what condition must be met?

Answer 15

Level cost is in Big-Theta(# base cases)

Question 16

For Master Theorem Case 2, what is the runtime T(n)?

Answer 16

Question 17

What summation is this equation true for?

Answer 17

Question 18

A BFS Tree is also…

Answer 18

The single source shortest path tree (where the weight of each edge is 1)

Question 19

Tree edge (BFS)

Answer 19

An edge from a gray to a white node, where the white node is first being discovered (also called discovery edges)

Question 20

BFS Applications

Answer 20

1. Test if G is connected
2. Compute a spanning tree of G
3. Compute the connected components of G
4. Compute the shortest path/distance between s and each vertex v in G

Question 21

Parenthesis Lemma

Answer 21

1. u is an ancestor of v iff [d[u], f[u]] SUPERSET OF [d[v], f[v]]
2. u is a descendant of v iff [d[u], f[u]] SUBSET OF [d[v], f[v]]
3. u and v are not related iff [d[u], f[u]] and [d[v], f[v]] are disjoint

Question 22

What is a topological sort (of a DAG)?

Answer 22

A LINEAR ORDERING of all vertices in G such that vertex u comes before vertex v if (u, v) is in G. Topological sort creates a PARTIAL ordering (since multiple valid orders may exist)

Question 23

For Prim’s algorithm, what is the key data structure?

Answer 23

A priority queue (min-heap) that is used to determine which node/edge to add to the tree next

Question 24

For Dijkstra’s algorithm, what is the key difference from Prim and Kruskal?

Answer 24

Dijkstra’s algorithm uses a priority queue (like Prim) but uses the shortest distance to the root node as the key value for the PQ.

Question 25

To compare (lg n)^100 vs. (lg n)^(lg n), what is a technique you can use?

Answer 25

Let m = lg n. Then you can easily compare m^100 vs m^m

Question 26

ith order statistic of n elements is...

Answer 26

the ith smallest element

Question 27

How do you reconstruct the LCS solution (qualitatively looking at the table)?

Answer 27

Take the letter listed on the side(s) when the arrow goes diagonally out of that letter's box!

Question 28

For US coinage problem, what approach do we use?

Answer 28

It can be solved with a greedy algorithm (unlike the general making change problem), and the greedy choice is to select the largest coin possible without exceeding the remaining amount

Question 29

What problem does Huffman encoding solve?

Answer 29

If we know the frequencies of characters in our alphabet, Huffman encoding can generate the optimal binary prefix-free encoding (such that the most frequently used characters have the shortest encoding).

Question 30

How does Huffman encoding work?

Answer 30

Sort all characters from lowest to highest frequency. Take the lowest two and combine them under a new node that contains the sum of their frequencies. Insert this composite node back into the list, resort, and repeat. You end up with a binary tree, and the encoding for any character can be found by assigning 0 to left branches and 1 to right branches as you traverse the path from the root node to that character.

Question 31

For L, root, R, what is inorder?

Answer 31

L, root, R

Question 32

For L, root, R, what is preorder?

Answer 32

root, L, R

Question 33

For L, root, R, what is postorder?

Answer 33

L, R, root

Question 34

How do you implement topological sort?

Answer 34

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 35

To find the maximum element of a strictly concave array (array strictly goes up then strictly goes down), what is the essence of the algorithm we discussed?

Answer 35

Compare the middle two (adjacent) elements. Since they are ADJACENT, you can properly determine if you are going up or down (since the strict ordering actually applies for adjacent elements!). Based on that, search either the left or right halves of the array

Question 36

For the Max subarray problem (DP), what is the definition of the main variable/answer?

Answer 36

maxSumEndAt[i] is the maximum sum of a contiguous subarray ENDING at index i (it can start anywhere!). The answer is: max (from i=1 to n) { maxSumEndAt[i] }

Question 37

For knapsack problem, what is the definition (not recurrence) of V[i, j]? What does it mean?

Answer 37

V[i, j] is the optimal solution considering only the first i items and capacity j knapsack

Question 38

What is the current view of P, NP, and NPC? (venn diagram)

Answer 38

Question 39

What is P?

Answer 39

The set of problems solvable in polynomial time

Question 40

What is NP?

Answer 40

The set of problems verifiable in polynomial time

Question 41

What is NPC?

Answer 41

The set of problems in NP and as hard as any other problem in NP

Question 42

What is NPH?

Answer 42

Problems that are as hard as any other problem in NP (hasn't necessarily been shown that these problems are in NP themselves)

Question 43

How to prove that a problem Y is NPC?

Answer 43

Show that: 1. It is in NP 2. Another NPC problem Yn is no harder than Y (Yn \<=p Y)

Question 44

What kind of problems are NPC?

Answer 44

Decision problems (Y/N answers)

Question 45

T(n) = 2T(n/2) + Theta(n)

Answer 45

T(n) = Theta(n lg n)

Question 46

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

Answer 46

T(n) = Theta(n lg n)

Question 47

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

Answer 47

T(n) = Theta(n^lg 3)

Question 48

T(n) = T(n/5) + T(7n/10) + Theta(n)

Answer 48

T(n) = Theta(n)

Question 49

If the recursion coeffecients sum to 1, we get...

Answer 49

Theta(n lg n)

Question 50

If the recursion coefficients sum to \> 1, we end up with...

Answer 50

something \> n lg n

Question 51

If our recursion coefficients sum to \< 1, we end up with...

Answer 51

Theta(n)

Question 52

What is the general approach for unbalanced recursion trees?

Answer 52

Find T(n) \>= something based on shorter side, find T(n) \<= something based on longer side, then make a bound from that