Stipek: Stop and Think

Question 1

For a graph with all unique edge weights, both Kruskal’s and Prim’s Algorithm will always return the same exact MST. Why might this be the case?

Answer 1

If a graph have unique edge weights that means every path between any two nodes must be unique.????

Question 2

Can a graph have more than one spanning tree that fulfills the four spanning tree properties mentioned above?

Answer 2

Yes.

If edge weighs are not all entirely unique multiple paths using edges of the same weights can generate the same minimum value with different edge sets

Question 3

Which of the following are valid ways to modify an unweighted graph to have Dijkstra’s Algorithm be able to accurately produce the shortest paths from one vertex to all other vertices?

Answer 3

We can assign a cost of 1 to each edge.

We can assign a cost of ¹/₂ to each edge.

Question 4

STOP and Think: It is important to note that there does not exist such a simple recursive pseudocode for Breadth First Search; why might this be the case?

Answer 4

????

Is it because of the vague base case?

Question 5

STOP and Think: If our database string D has length n, what is the space complexity of storing all of its n suffixes?

Answer 5

You need to store n, then n-1, then n-2, then …… until 1

So its (n) + (n-1) + (n-2) + … (2) + (1) = n(n+1)/2 ~ n^2

Question 6

STOP and Think: How can we reformulate our algorithm to find the correct first and last suffixes?

Answer 6

Instead of doing a single binary search to determine whether or not we have any matches, do two binary searches with slightly different “success” criteria:

Find the i-th suffix that begins with w such that the (i-1)-th suffix does not start with w. This is the start of the range of matches
Find the j-th suffix that begins with w such that the (j+1)-th suffix does not start with w. This is the end of the range of matches

Question 7

STOP and Think: (end of Suffix array) Can we think of an even more clever preprocessing of our database sequence to enable even faster query searches?

Answer 7

Burrows Wheeler Transform

Question 8

STOP and Think: Is there any way for us to reconstruct our original string using only the first and last columns of our Burrows-Wheeler Matrix?

Answer 8

For each letter __ m, the i-th occurence of x in the first column happens to correspond to the exact same lette in the original string as the i-th occurence in the last column.

Question 9

STOP and Think: Given only the BWT, do we actually need the original string (or any information about the original string) to construct any parts of this table?

Answer 9

Not really

Question 10

STOP and Think: How could you transform an undirected graph into a directed graph?

Answer 10

Yes, just give it a direction

Question 11

STOP and Think: Can the Hash Table above ever get full (using seperate chaining?

Answer 11

depends on what is meant by “full”