part 2

Question 1

What does Prim’s algorithm do?

Answer 1

Finds the minimum spanning tree of a graph

Question 2

What does Kruskal’s algorithm do?

Answer 2

Finds the minimum spanning tree of a graph

Question 3

What’s the difference between how Prims and Kruskal’s algorithm operate?

Answer 3

Both Prim’s and Kruskal’s algorithm start with the lowest cost edge (which obviously includes the two vertices that are attached by said edge). Prim’s algorithm goes on to select the lowest cost edge that is connected to the original vertices chosen in the first step, while Kruskal’s goes on to select the next lowest cost edge in the entire graph (irrespective of whether its connected to the original vertices or not)

Question 4

How do we avoid resolving a subproblem for DP?

Answer 4

Memoization

Question 5

Strongly Connected Component

Answer 5

every vertex is reachable from every other vertex

Question 6

Transpose of a graph

Answer 6

A directed graph that has flipped the directions of all of its edges

Question 7

Topological Sort

Answer 7

a linear ordering of nodes of a directed acyclic graph, such that a node follows all of its graph predecessors in the ordering.

Question 8

What does the runtime for dynamic programming tell us?

Answer 8

When there are two variables/constants it will be much easier to use a lookup table than to try a top down approach

Question 9

Whats the runtime of the Huffman coding algorithm?

Answer 9

O(nlogn)

Question 10

Exchange Argument for Greedy Algorithms

Answer 10

1)Let Sg be items (or whatever) chosen by greedy
2)Let So be items chosen by another potentially optimal algorithm
3)Order (doesn’t have to be order, problem dependent) items in So the same way as greedy, let e be the first thing in So not in greedy
4)show towards contradiction that the greedy algorithm is correct, or show in a mathematical sense or otherwise explain in English that item e in So is equal or worse to item f in greedy
5)conclude we can exchange e for f
6) Repeat over and over until So is the same as greedy

Question 11

What is the runtime of Kruskals algorithm?

Answer 11

O(ElogV)

Question 12

What’s the runtime of Prim’s algorithm?

Answer 12

O(ElogV)

Question 13

What does the shortest path by matrix multiplication do?

Answer 13

-You start with matrix A, which is a matrix of how to get from nodes i to nodes j in one step
-It tells you the shortest possible way to get from one node to another node in n-1 steps
-It does this by adding the row of i plus the column of j (one at a time) and takes the minimum of these sums
-Worth noting th

Question 14

How long does matrix multiplication take?

Answer 14

O(n^3 logn)

Question 15

What is the shortest path between two vertices that are on a negative length cycle?

Answer 15

negative infinity

Question 16

What do we initialize all the values of bellman ford at?

Answer 16

All at infinity

Question 17

What is a shortest path tree?

Answer 17

a shortest path tree rooted at vertex v is a spanning tree such that the distance from v to any root u is the shortest path from vertex v in the original graph

Question 18

Proof By Contrapositive

Answer 18

Let S be a statement of the form that implies “if P then Q”. The Contrapositive of S is “if (not Q) then (not P)”

Question 19

Proof by Contradiction

Answer 19

An indirect proof in which one assumes that the statement to be proved is false. One then uses logical reasoning to deduce a statement that contradicts a postulate, theorem, or one of the assumptions. Once a contradiction is obtained, one concludes that the statement assumed false must in fact be true.

Question 20

Whats the runtime of DFS and BFS?

Answer 20

O( V + E)

Question 21

An interesting tool that could be useful for graph algorithms

Answer 21

Add a new node to the graph and connect to every every node that has some specified thing we are trying to identify. Then run BFS from the new node in order to identify every node on the graph that has some specified thing

Question 22

Minimum spanning tree

Answer 22

a tree that connects all nodes by edges such that the sum of the edges is as small as possible

Question 23

Connected graph

Answer 23

it’s possible to get to any node from any node in the graph. But it is NOT a complete graph !

Question 24

Cut Edge

Answer 24

The removal of this edge would disconnect a graph

Question 25

What’s the recurrence relation for the optimal static BST in English?

Answer 25

T(i,j) = average access time of an optimal BST over the keys {k_{i}, k_{i+1},…k_{j}}

more specifically/explicitly

T(i,j) = min possible left subtree + sum of probabilities of the left subtree + min possible right subtree + sum of probabilities of the right subtree + probability of the root node !

Question 26

What is a O(logn) search algorithm that can only be used on a sorted array/list?

Answer 26

Binary Search

Question 27

in terms of data structures utiilized how does DFS differ from BFS?

Answer 27

DFS uses a stack while BFS uses a queue

Question 28

What is a tree edge of a graph?

Answer 28

Edge on which a new vertices are found

Question 29

What is the back edge of a graph?

Answer 29

All other edges besides tree edges
keep in mind with their retarded notation that n = nodes, m = edges

Question 30

What is the shortest path of a negative weighted cycle?

Answer 30

It will result in negative infinity, because the relaxing algorithm will just keep knocking the values lower and lower till it gets to negative infinity

Question 31

What’s the runtime of the optimal static BST?

Answer 31

O(n^3)

Question 32

Proof By Contradiction

Answer 32

1) To prove P we can prove if (not P) then C
a) C stands for contradiction

Question 33

Heap Tree

Answer 33

• value of a parent is always less than value of a child
• the root is always the min
• as close to a complete binary tree as possible
  -all heap operations take O(logn)

Question 34

If we wanted to create a heap out of an array, what would be the runtime of heapify vs successively inserting each element into the heap?

Answer 34

Heapify takes O(n) time while sucessively inserting each element takes O(nlogn) time

Question 35

Proof By Converse

Answer 35

Let S be a statement of the form that implies P -> Q. Then the Converse of this statement is Q -> P

Question 36

Proof By Contrapositive

Answer 36

Let S be a statement of the form that implies “if P then Q”. The Contrapositive of S is “if (not Q) then (not P)”

Question 37

In a balanced BST how would you store the size of the subtree rooted at d?

Answer 37

a) Anytime we add or delete a new node, we recursively add or subtract one from each of its parents
b) When rotating a tree, we can recalculate the size of the two changed nodes by summing the size of their unmodified children and adding one

Question 38

Given an array, how do you know what the left and right child of a given index is in a heap?

Answer 38

left child is 2i, right child is 2i + 1