Brainscape's Knowledge GenomeTM

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


See full index

Des & Analysis of Algorithms (CS 617) > FINAL - short answer/equations > Flashcards

FINAL - short answer/equations Flashcards

Get an A+ on the final exam!!

1
Q

Greedy choice property

A

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

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

Optimal substructure property

A

A globally optimal solution contains globally optimal solutions to its subproblems

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

Cardinality

A

The number of elements in a set

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

7 steps to solve a DP problem

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

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

For Master Theorem, what is the level cost?

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

For Master Theorem, what is the # base cases?

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

For Master Theorem, what is the # levels?

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

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

A

Level cost is polynomially SMALLER than # base cases

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

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

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

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

A

Level cost is polynomially LARGER than # base cases

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

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

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

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

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

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

A

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

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

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

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

What summation is this equation true for?

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

A BFS Tree is also…

A

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

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

Tree edge (BFS)

A

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

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

BFS Applications

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Parenthesis Lemma

A
  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
22
Q

What is a topological sort (of a DAG)?

A

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)

23
Q

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

A

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

24
Q

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

A

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.

25
Q

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

A

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

26
Q

ith order statistic of n elements is…

A

the ith smallest element

27
Q

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

A

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

28
Q

For US coinage problem, what approach do we use?

A

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

29
Q

What problem does Huffman encoding solve?

A

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).

30
Q

How does Huffman encoding work?

A

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.

31
Q

For L, root, R, what is inorder?

A

L, root, R

32
Q

For L, root, R, what is preorder?

A

root, L, R

33
Q

For L, root, R, what is postorder?

A

L, R, root

34
Q

How do you implement topological sort?

A

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

35
Q

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?

A

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

36
Q

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

A

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] }

37
Q

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

A

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

38
Q

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

A
39
Q

What is P?

A

The set of problems solvable in polynomial time

40
Q

What is NP?

A

The set of problems verifiable in polynomial time

41
Q

What is NPC?

A

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

42
Q

What is NPH?

A

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

43
Q

How to prove that a problem Y is NPC?

A

Show that:

  1. It is in NP
  2. Another NPC problem Yn is no harder than Y (Yn <=p Y)
44
Q

What kind of problems are NPC?

A

Decision problems (Y/N answers)

45
Q

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

A

T(n) = Theta(n lg n)

46
Q

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

A

T(n) = Theta(n lg n)

47
Q

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

A

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

48
Q

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

A

T(n) = Theta(n)

49
Q

If the recursion coeffecients sum to 1, we get…

A

Theta(n lg n)

50
Q

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

A

something > n lg n

51
Q

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

A

Theta(n)

52
Q

What is the general approach for unbalanced recursion trees?

A

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

Des & Analysis of Algorithms (CS 617) (16 decks)

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