Prim’s Algorithm

All work must be your own. Turn in electronic format (PDF or MS Word) and any supporting programs (source code and test cases). Show your work in all the details for maximum score.

NOTE: No extensions or late submissions for anything.

(Q1) [15 pts.] What is the order of the following algorithm:

procedure Func1(m,n)

{

while (m > 0)

{

t = n mod k;

n = k;

k = t;

}

}

(Select the answer from the following options and prove your choice):

1. n^k
2. theta (ln k)
3. k^n
4. k^2

(Q2) [5 pts.] A graph with n nodes is connected, undirected, and acyclic. How many edges must it have? (Select the answer from the following options and prove your choice):

1. n/2 – 1
2. n – 1
3. n*(n-1)
4. n

(Q3) [40 pts.] Given these methods:

METHOD math1:

public int math1( int n ) {

if (n <= 1) {

return 1;

} // if

else {

return ( 2 * n ) + math1( n-1 );

} // else

} // math1

METHOD math2:

public int math2( int n ) {

if (n <= 1) {

return 1;

} // if

else {

return n + math1( n ) * math2( n/2 );

} // else

} // math2

(a) Set up a recurrence relation for the running time of the method math1 as a function of n. Solve your recurrence relation to specify THETA bound of math1.

(b) Now set up a recurrence relation for the running time of the method math2 as a function of n. Solve your recurrence relation to specify the Big-O bound of math2.
HINT: When doing this, the call to math1 can be replaced by the equation that you found when solving the recurrence relation for math1 in part a) [see above].

(Q4) [10 pts.] Which Design Technique was used to produce Kruskal’s Algorithm? (Select the answer from the following options of Design Techniques and prove your choice):

1. Linear Programming
2. Dynamic Programming
3. Greedy
4. Divide and Conquer

(Q5) [30 pts.] Given a six vertex graph (see below):

• Based on this graph, compute a minimal cost spanning tree using Kruskal’s Algorithm. Show (plot) the tree and cite its total cost.

• Using the same graph (above), apply Prim’s Algorithm and compute a minimal cost spanning tree starting at the VERTEX marked as “C”. Show (plot) the spanning tree and cite its cost.

NOTE: DO THIS BY HAND (using any simple drawing tool)! No need to write code.

ATTN: Submit your Final Exam Report in electronic format (PDF or MS Word) as an attachment to your email