The Problem

We will consider the problem of exponentiating an integer to another. In particular, for non-negative integers $a$ and $n$, define Power$(a,n)$ be the number $a^n$. (For this problem assume that you can multiply two integers in $O(1)$ time.) Here are the two parts of the problem:

• Part (a): Present a naive algorithm that given non-negative integers $a$ and $n$ computes Power$(a,n)$ in time $O(n)$.

  Note

  For this part, there is no need to prove correctness of the naive algorithm but you do need a runtime analysis.

• Part (b): Present a divide and conquer algorithm that given non-negative integers $a$ and $n$ computes Power$(a,n)$ in $O(\log{n})$ time.

  Important Note

  To get credit you must present a recursive divide and conquer algorithm and then analyze its running time by solving a recurrence relation. If you present an algorithm that is not a divide and conquer algorithm you will get a level 0 on this entire part.

  Hint

  The following mathematical identity could be useful-- for any real numbers $b,c$ and $d$: $b^{c+d}=b^c\cdot b^d$.

  Common Mistake

  Be careful and make sure that you use the correct recursive calls. Many students end up with an $\Omega(n)$ time algorithm for the second part by not using the correct set of recursive calls.

The Problem

In this problem you will explore what happens if in the integer multiplication algorithm we saw in class we do the splitting of the numbers differently. But before we get to the final problem, let's start off with this one:

• Part (a): Define the recurrence relation \[ T(n)\le \begin{cases} c &\text{ if }n<3\\ 5T\left(\frac{n}{3}\right)+cn&\text{ otherwise}. \end{cases} \] Argue that $T(n)$ is $O\left(n^{\log_3{5}}\right)$.

We now come to the actual algorithmic problem:

• Part (b): Either by modifying the algorithm we saw in class or otherwise, present an algorithm that can multiply two $n$ bit numbers $a=(a_{n-1},\dots,a_0)$ and $b=(b_{n-1},\dots,b_0)$ in time $O\left(n^{\log_3{5}}\right)$, which is $O(n^{1.47})$ (and is better than the runtime of the algorithm we saw in class).

  Hint

  It might be useful to divide up the numbers into three parts each with roughly $n/3$ bits and then argue that one only needs to perform $5$ smaller multiplications of $n/3$-bit numbers instead of the trivial $9$ such multiplications. Further this support page might also be useful in generalizing the $O(n^{\log_2{3}})$ algorithm to one with a better runtime as required by this problem.)

The Problem

In this problem, we will explore minimum spanning trees.

We are given an undirected, connected graph represented by its adjacency matrix representation. Our goal it to find a minimum spanning tree of that graph.

Input

The input file is given as an $n\times n$ matrix where each entry $(u,v)$ represents the weight of the edge between nodes $u\in \{0,1,\dots,n-1\}$ and $v\in\{0,1,\dots,n-1\}$. If there is no edge then the weight is -1. Edge weights will be 0 <= w <= 50.

            	w0,0 w0,1 w0,2 w0,3 ...  w0,n-1
            	w1,0 w1,1 w1,2 w1,3 ...  w1,n-1
		.
		.
		.
		wn-1,0 wn-1,1 wn-1,2 wn-1,3 ...  wn-1,n-1
	    

Output

The output is a list where every index corresponds to the node ID and the value in the index is the parent of the node. In other words, you need to output a rooted form of an MST (you can root the MST at any node).

            	[p0 p1 p2 .... pn-1]   	<- Where the subscript is the node ID and p is the parent node