Question 1.  (10 marks)

 

Question 1A.   (7 marks)

Write a recursive function gcd(a,b) in C that finds the Great Common Divisor oftwo integers A and B using Euclid’s algorithm. Euclid’s algorithm is defined as follows:

 

Question 1B.   (3 marks)

Show the calls (indicating the values of the function parameters) and return values from those calls when the following code is executed:

x = gcd (54, 24);

 

 

Question 2. Sort Comparison  (10 marks)

 

This question compares Selection Sort and Bubble Sort. The sorts will be used to arrange data in ascending order - meaning that when a sort has finished, the smallest data item will be in the       lowest index - position 0, the next lowest in position 1, etcetera.

Suppose you start with an array with the following data:

50  36  42  19  27  33  4  48  12  6  2

Answer the following questions based on this data.

1.   For both sorts, the 50 will be in position 10 after the first pass ofthe sort. (True/False)

2.   After the first pass of Bubble Sort, the 42 will be at index:

3.   After the second pass of Bubble Sort, the 42 will be at index:

4.   After the first pass of Selection Sort, the 42 will be at position:

5.   After the second pass of Selection Sort, the 42 will be at position:

6.   During the first pass of Selection Sort, how many swaps will occur?

7.   In the first pass ofBubble Sort, how many swaps will occur?

8.   If we compare the total number of swaps required by Bubble Sort to sort the whole array to the total number of swaps required by Selection Sort to sort the whole array, we find   that Bubble Sort requires, in the worst case, twice as many swaps as Selection Sort.         (True/False)

9.   Both Selection Sort and Bubble Sort require 11 passes to sort the given data. (True/False)

 

Question 3. Stack/Queue Question (10 marks)

 

In this question, you are asked to write C-language code. For the purposes ofthe exam,  you do not need to comment your code unless you feel the need to explain what you are doing. Also, you can earn part marks by using a C-like pseudo code that illustrates how your solution would work.

Suppose you have been supplied software that implements a single integer queue. You do not have access to the code that implements the queue but you are told the interface to the queue  implementation is as follows:

int Qisnotempty (void)

Returns 0 ifthe queue is empty, 1 if it is not empty.

int Qstore (int val)

Inserts the integer val at the end ofthe queue. Returns 1 ifthe insert worked, 0 if it did not.

int Qfetch (int *pval)

Fetches an integer value from the front ofthe queue and stores the value in the integer pointed to by pval. Returns 1 ifthe fetch          worked, 0 if it did not.

You are told to assume, for the purposes ofthis problem, that the queue will not run out of memory.

You are told to implement code for a stack and that your implementation MUST use the queue for the actual data storage. In other words, you have a single FIFO (first-in, first out) data         structure and you want to use it to implement a LIFO (last-in, first-out) data structure.

Your code shall have the following interface - meaning, these are the variable and routines that you must write code for.

int  StackCount;

Variable keeps track of how many items are on the stack.

void StackInit (void)

Function to initialize all necessary data related to the stack.

 

void Stackisnotempty (void)

Returns 0 ifthe stack is empty, 1 if it is not empty

int  StackPush (int val)

Push the integer val onto the stack. Returns 1 if push worked and 0 if it did not

int  StackPop (int *pval)

Pop the top value from the stack and store the value in the integer pointed to by pval. Returns 1 if pop worked, 0 if it did not.

Your code need not contain any elaborate comments unless you need to explain what you have  done. You can earn some part marks by explaining how your code will work without writing all the required code.

 

Question 4. (6 marks)

 

Suppose you are given an array A containing K integers. The integer values are all in the range   [0..M- 1] where M > K.  Write an O(N) function in C that determines which ofthe values in A     have duplicate values in A. For example, if A contained { 0, 1, 2, 1, 3, 2, 4, 5}, your code would report that two values (the 1 and the 2) are duplicated.

The prototype for your function shall be:

 

int find_duplicates (int *pa, int k, int m);

 

Parameter pa shall be a pointer to the array to be checked, parameter k shall be the size ofthe array,  and parameter m shall be the maximum value that can be in the data.

 

 

Question 5. Binary Search Tree  (10 marks)

Recall the notation used to represent a binary tree using only text - no diagram.  For a binary tree holding just an item of integer data, we show a pair of curly brackets {} to  enclose the whole      tree, and then we describe the tree within the brackets by first showing the data value, then           showing the left subtree and then showing the right subtree.  So, a binary tree with only a root      node containing 9 would look like  { 9 {} {} } - the tree has a 9 in the root node and the root node has two empty subtrees. A binary tree with 9 in the root position, 4 in root's left child and 20 in    root's right child would be { 9 { 4 {}{}} {20 {}{}} }.

This notation can be a bit unreadable, especially with a larger binary tree, and so for display purposes, the following notation can be used:

{ 9

{ 4 {}{} }

{20 {}{} }

}

 

That is, for every leaf - a node with no children - it can be shown on one line. Otherwise, for a node with at least one child, we show an opening curly bracket and a node value, then move    down one line and show the left subtree, then move down one more line and show the right     subtree, then move down one more line and show the closing curly bracket for the node.

The following questions will use this notation.

 

Question 5A  (3 marks)

Suppose you want to store integer data in a binary search tree (BST), where the ordering is lower values on the left and higher values on the right.

If you insert the following values into the tree:

60  70  50  55  68  80  75  76  77  90  40  45  30  74  73

what would a diagram ofthe resulting tree look like? Use the text-only method to describe the tree.

 

Question 5B (1 mark)

If the tree were to be printed using a post-order traversal, what would be printed?  (Please use two spaces between each number.)

 

Question 5C (1 mark)

If the tree were to be printed using a breadth-first traversal, what would be printed?  (Please use two spaces between each number.)

Question 5D (2 marks)

Suppose the 75 is  removed from the BST. Use the text-only method to show what the tree looks like after the 75 is removed.

 

Question 5E (3 marks)

Suppose the definition of a node in this tree is as follows:

struct node {   struct node struct node

int

};

 

*pleft;

*pright;

data;

Write a recursive routine to print the tree using the text-only format that was described at the top ofthe question. The header for the function shall be:

void print_tree (struct node *proot)

 

where proot points to the root ofthe tree to be printed.

Question 6C.  (16 marks)

 

The diagram shows a weighted digraph with six vertices {A, B, C, D, E, F}.

Use Dijkstra’s algorithm to find the shortest cost (weight) path from starting vertex A to other      vertices in the graph. You will show the progress of the algorithm with each pass on its own row. This is slightly different from the presentation used in class, where each pass was shown in a        new column.  This change has been done to make it easier to enter your answer.  In class the         rows were labelled with the vertex names - here the columns will be labelled by vertex name.

For your answer, you will be recording a k, d, and p value for each vertex.

•    The k values are + ifthe vertex is known or - if it is not.

•    The d value is the cost from this vertex to the starting vertex. Use 99999 to indicate unknown.

•    The p value indicates the predecessor node on which the weighted distance is based. It

will be a ? ifno distance is known yet.

The data at the start ofthe algorithm is as follows:

	A	B	C	D	E	F
Start	-0A	-99999?	-99999?	-99999?	-99999?	-99999?
Pass 1

 

 

After the first pass, the data for A will change to +0A, and data will be updated for the vertices directly connected by an edge from A.

Show the rest of the table - as many passes as you need using the format as shown -  as Dijkstra's algorithm determines more information.

 

Question 7. (10 marks)

 

Suppose you have an array, A, containing the following 20 integers:

49  11  93  50  67  18  13  48   6  20  38  27  22  12  33  41  63  58   2   47

You are going to run Quicksort on this array and describe the progress.

 

In the partition step when you are looking at a portion ofthe array from index left to index right, the pivot element shall be chosen as the value in A[left].

 

Question 7A (1 mark)

For the first partition step, what is the pivot value?

 

Question 7B (2 marks)

After the first partition step completes, at what index in the array is the pivot value placed?

 

Question 7C (1 mark)

For the second partition step, what is the pivot value?

 

Question 7D (2 marks)

After the second partition step completes, at what index in the array is the pivot value placed?

 

Question 7E (1 mark)

For the third partition step, what is the pivot value?

 

Question 7F (1 mark)

After the third partition step completes, at what index in the array is the pivot value placed?

 

Question 7G (1 mark)

For the fourth partition step, what is the pivot value?

 

Question 7H (1 mark)

After the fourth partition step completes, at what index in the array is the pivot value placed?

Question 8.  Heaps   ( 6  marks)

 

Suppose you have the following 16 values in an array of integers:

 

40, 30, 75, 65, 22, 30, 16, 10, 90, 15, 6, 72, 4, 80, 5, 71, 35

 

Heapify this array to create a maximum heap. Show the contents ofthe array after heapifying. Write the numbers all on one line, with either two blanks or a comma and a blank between the numbers.

 

Question 9. AVL Tree  (20 marks)

An AVL tree is created and the following 5 numbers are inserted:

30  25   35  20   40

 

For all the following questions, indicate which answer is true. In the questions that describe        adding a value to the tree, the additions are cumulative – that is, the additions in questions 9D to 9J are done in order. Note: An incorrect tree structure at any step may result in a loss ofmarks    for subsequent steps.

 

Question 9A    (1 mark)

The balance factor for the root node is

a)   left heavy (BF > 0)

b)  right heavy  (BF < 0)

c)  balanced     (BF == 0)

 

Question 9B     (1 mark)

The balance factor for the node with value 25 is

a)   left heavy (BF > 0)

b)  right heavy  (BF < 0)

c)  balanced     (BF == 0)

 

Question 9C     (1 mark)

The balance factor for the node with value 40 is

a)   left heavy (BF > 0)

b)  right heavy  (BF < 0)

c)  balanced     (BF == 0)

Question 9D     ( 5 marks)

Ifthe value 21 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 9E     ( 4 marks)

If the value 39 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 9F     ( 3 marks)

If the value 50 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 9G      ( 2 marks)

Ifthe value 55 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 9H      ( 1 mark)

If the value 22 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

Question 9I      ( 1 mark)

Ifthe value 23 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 9J      ( 1 mark)

If the value 54 is added to the tree,

a)  A single left rotation is required

b)  A single right rotation is required

c)  A left-then-right rotation is required

d)  A right-then-left rotation is required

e)  No rotation is required.

 

Question 10. Algorithm Analysis (7 marks)

 

These questions all relate to algorithm analysis - the "BigOh" topic that was covered in class.

 

Question 10A  (1 mark)

Suppose you were to sort an array of N integers by first inserting its elements into a BST and

then performing an in-order traversal on the BST, writing the values back into the original array. Which of the following best describes this algorithm's complexity?

a)  Worst case running time O(N*N)  additional memory required O(N)

b)  Worst case running time O(N log N) additional memory required O(N)

c)  Worst case running time O(N*N)  additional memory required O(1)

d)  Worst case running time O(N log N) additional memory required O(1)

 

Question 10B  (1 mark)

We wish to sort an array of N integers by first inserting its elements into an AVL Tree and then performing an in-order traversal on the resulting tree, copying the values back into the original  array.

Which of the following best describes this algorithm's complexity?

 

a)  Worst case running time O(N*N) additional memory required O(N)

b)  Worst case running time O(N log N) additional memory required O(N)

c)  Worst case running time O(N*N) additional memory required O(1)

d)  Worst case running time O(N log N) additional memory required O(1)

Question 10C (1 mark)

 

Consider the following piece of C code:

 

void divide(int n, int k)

{

for (int i = n; i >= 1; i /= k)

printf("I love algorithms!\n");

}

 

Which of the following best describes how many times the print statement is performed when the divide function is called with n > 1 and k > 1?

a)   O(log n) times

b)  O(log k) times

c)   O(n/k) times

d)  O(k/n) times

 

Question 10D (1 mark)

 

Consider the following piece of C code:

 

void tricky(int n)

{

if (n <= 1000000000)

for (int i = 0; i < n; i++)

printf("I love algorithms!\n");

else

printf("I hate algorithms!\n");

}

 

Which of the following  best describes how many times the print statement containing the word “love” is executed when the tricky function is called?

a)   O(1) times

b)  O(N) times

c)   exactly 1000000000 times

d)  none ofthe other answers is correct