- Right click on the blue screen to bring up a menu.
- Start an Xterm.
- Type `ls` to find the files for the exam.
- Follow the instructions contained in the files below:

Question 1 - partition.c

Question 2 - treeEq.c

Question 3 - inDegree.c

To get the all the relevant files change into an appropriate directory and type the following command

cp ~cs2521/public_html/18x1/exams/prac2/* .

Which of the following statements are true for a complete graph with 3 or more vertices?

.[A] The least hops path between 2 different vertices always has exactly one edge .[B] The shortest weighted path between 2 different vertices always has exactly one edge .[C] There can not be a hamilton tour .[D] All of the above .[E] None of the above

After running tests and determining that an unknown sorting algorithm has a time complexity of O(n) for descending ordered data, we would assume the algorithm could be

.[A] Quicksort with Median of Three Partitioning .[B] A non-comparison based sorting method .[C] unstable .[D] In-place .[E] None of the above

15 / \ 3 16 / \ \ 1 8 17 \ 9A pre-order traversal would give the output in which order:

.[A] 1 3 8 9 15 16 17 .[B] 1 9 8 3 17 16 15 .[C] 15 3 16 1 8 17 9 .[D] 15 3 1 8 9 16 17 .[E] None of the above

The following alternatives list expressions for the worst-case time complexity T(n) of various algorithms. Which alternative has an asymptotic worst-case complexity of O(n^2^)?

.[A] n^2^ .[B] 0.3n^2^ + n + 1000 .[C] 1.3n(n+1) + 10logn .[D] 2n^2^ - 10 .[E] All of the above

We can change a depth first search to a breadth first search by using

.[A] A queue instead of a stack .[B] A stack instead of a queue .[C] Using recursion instead of iteration .[D] None of the above

Assume we have the following minHeap 5 / \ / \ 10 29 / \ / \ 11 12 30 31

.(a) Give an example of a key that would result in a worst case scenario for heap insertion. Show the resulting heap and state how many comparisons were made.

You may show the resulting heaps in either a tree or array format.

.(b)

Give an example of a key that would result in a best case scenario for heap insertion. Show the resulting heap and state how many comparisons were made.

You may show the resulting heaps in either a tree or array format.

After running a djikstra's algorithm from the starting vertex with id 3, we get the following st and dist arrays.

0 1 2 3 4 5 6 st: 3 6 3 3 3 -1 4 dist: 5 7 1 0 2 inf 5

.(a)

What is the shortest path from 3 to 1? What is the cost of this path?

.(b)

Is the graph fully connected? Explain why.