Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Q2.1

We used a PriorityQueue to help us efficiently find the "closest unknown vertex" in the perimeter. The extended PriorityQueue ADT with changePriority and contains is very important for being able to update node distances that are already in the perimeter.

Q2.2

$$ \Theta\left(|V|^2\log(|V|)\right) $$

We can get this by plugging in $|E| = \frac{1}{2}|V|^2$ into the runtime for Dijkstra's. We drop the lower order terms and multiplicative constants.

$$ \Theta\left(|V|\log\left(|V|\right) + |E|\log(|V|)\right) \\ = \Theta\left(|V|\log\left(|V|\right) + \frac{1}{2}|V|^2\log(|V|)\right) \\ = \Theta\left(|V|^2\log(|V|)\right) $$

Q2.3

$$ \Theta\left(|V|^2 + |E||V|\right) $$

This can be found by using the same type of analysis we used with Dijkstra's, but now we have a $|V|$ operation each time we work with the perimeter rathern than a $\log(|V|)$ operation.

Question 3

Many orderings exist, here is one that satisfies all of the dependencies shown below.

3,5,7,11,8,9,2,10

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/95611063-840d-4752-9beb-a7bdabd725ff/Untitled.png

Question 4

For this problem, we chose to reduce this ranking problem to topological sort since we have a bunch of games that have "dependencies" on who should be ranked above who and we are trying to find an ordering that preserves these placements.

Q4.1