**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
```

# 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