Circuits (a) Express the following Boolean Statement as a circuit: [3 marks] \[ A(B+\bar{C})+\overline{A+B C} \]

3. Consider the following list of values: $15,21,7,19,22,11$. (a) Demonstrate how the selection algorithm would sort this list efficiently and count how many comparisons are made. [3 marks] (b) Demonstrate how the bubble algorithm would sort this list efficiently and count how many comparisons are made. [3 marks] (c) Demonstrate how the merge algorithm would sort this list efficiently and count how many comparisons are made. [3 marks]

2. You are given an ordered list of $n$ objects, $a_{1}, a_{2}, \ldots, a_{n}$ (in no particular order, though). Describe an algorithm that reverses the order of these $n$ objects while introducing at most one new variable. Keep in mind, that if you set $a_{n}=a_{1}$, then we forget what $a_{n}$ used to be unless we assign a place-holder variable. [5 marks]

1. Minimal Spanning Trees (a) Construct a connected graph that has two distinct minimal spanning trees (that is, if its minimal spanning tree has total weight $\mathrm{W}$, then there are two different spanning trees with this weight). [2 marks] (b) If a connected graph has four vertices and all edges have different lengths (refer to the last assignment for all the ways you could draw this), show that you cannot have two distinct minimal spanning trees. [6 marks]

4. Travelling Salesman Problem (a) For the following graph with 8 vertices and indicated edge lengths, find the shortest 8-cycle (a cycle that contains all 10 vertices). [3 marks] \[ \begin{array}{l} A B(5), A C(9), A D(6), A F(2), A H(5), B C(3), \\ B D(3), B E(8), B F(2), B G(9), C E(2), C F(6), \\ D E(7), D F(3), D G(5), E G(2), F H(7), G H(3) \end{array} \] (b) One method to find the shortest cycle in a graph with $n$ vertices is to find the length of all possible $n$-cycles and choose the shortest $n$-cycle from that set. So that this can be programmable, we can write that the distance between two vertices that don't contain an incidental edge is $\infty$; that is, the length of any $n$-cycle containing a missing edge is $\infty$. This requires us to compare the lengths of all $n$-cycles, even if edges are missing. i. Use this method to find the shortest cycle for the following graph. [3 marks] \[ A B(7), A C(3), A D(4), B C(5), B D(8), C D(9) \] ii. Use this method to find the shortest cycle for the following graph. [4 marks] \[ A B(3), A C(8), A E(4), B C(5), B D(11), C D(7), C E(6), D E(9) \] iii. How many $n$-cycles of this type are there between three vertices? Four vertices? Five vertices? Six vertices? Twenty vertices? [2 marks] (c) Consider the following algorithm for decreasing cycle length: Choose an arbitrary cycle $v_{1} \rightarrow$ $v_{2} \rightarrow \ldots \rightarrow v_{n} \rightarrow v_{1}$. Go through $i=1$ to $i=n-1$ and check if swapping any $v_{i}$ and $v_{i+1}$ will yield a shorter cycle; swapping them if so. After $i=n-1$, check if swapping $v_{n}$ and $v_{1}$ will yield a shorter cycle, swapping them if so. Start again at $i=1$ and stop when you've checked $n$ times consecutively without a swap occurring. i. Each check requires calculating the new total cycle length, where each mathematical operation requires a tiny amount of time. What is the fastest way we could do this check at each stage? [1 mark] ii. Demonstrate an implementation of this algorithm on the following graph, beginning with the cycle $A->B->C->D->A$. [3 marks] \[ A B(9), A D(10), B C(11), B D(6), C D(13) \] iii. Construct a graph where this algorithm does not work. That is, it does not give the shortest $n$-cycle. [2 marks]