Comp 352  Data Structure and Algorithms Assignment 3  Solved

 

                                                                                                           

  

Heads-Up
 

•        The programming questions can be done individually or in a team of two members max. However, the written questions must be completed and submitted individually.

•        For the written questions, you must submit the answers to all the questions. However, only a couple of questions chosen at random, will be corrected and will be evaluated to the full 50 marks.

•        For the programming questions you are not allowed to use any java build-in classes/methods/algorithm unless indicated.

 

 

1. Written Questions 

   

Question 1
 

Assume a hash table utilizes an array of 13 elements and that collisions are handled by separate chaining. Considering the hash function is defined as: h(k) = k mod (13).

 

a)     Draw the contents of the table after inserting elements with the following keys:

{245, 28, 10, 49, 70, 225, 122, 12, 180, 140, 177, 65, 223, 85, 111, 256, 18, 69, 59, 185, 105, 120, 44}.  

 

b)     What is the total number of collisions caused by the above insertions?

 

Question 2
 

 

Assume an open addressing hash table implementation, where the size of the array N = 19, and the double hashing is performed for collision handling. The second hash function is defined as:  

d(k) = q - k mod q, where k is the key being inserted in the table and the prime number q = 11. Use simple modular operation (k mod N) for the first hash function.

a)     Show the content of the table after performing the following operations, in order:

put(37), put(17), put(24), put(36), put(62), put(28), put(58),put(47), put(19).

b)     What is the size of the longest cluster caused by the above insertions?

c)     What is the number of occurred collisions as a result of the above operations?

d)     What is the current value of the table’s load factor?

 

 

Question 3
 

Assume the utilization of linear probing instead of double hashing for the implementation given in Question 2.

Still, the size of the array N = 19, and that simple modular operation (k mod N) is used for the hash function.  

a)     Show the contents of the table after performing the following operations, in order: put(37), put(17), put(24), put(36), remove(62), remove(28), put(58), put(47), remove(19). 

b)     What is the size of the longest cluster caused by the above insertions? Using Big-O notation, indicate the complexity of the above operations.

c)     What is the number of occurred collisions as a result of the above operations? 

 

 

Question 4
 

Note: Part (a) and (b) are independent in this question.

Consider the following AVL tree:

 

 

  

 

a)       Draw the AVL tree resulting from the insertion of an entry with key 56 in the AVL tree shown above.

 

b)      Draw the AVL tree resulting from the removal of the entry with key 28 in the AVL tree shown above.

 

 

Question 5
 

Consider the following elements:

12, 47, 74,19, 89, 4, 63, 26, 53, 8, 93, 71, 15, 87, 50, 17, 82

 

Trace the steps when sorting these values into ascending order using:

a)     Merge Sort

b)     Quick Sort (using (middle +1) element as pivot point)

c)     Bucket Sort – We know that the numbers are less than 99 and there are 10 buckets. d) Radix Sort

 

    

Question 6
 

Consider the graph shown below:

  

 

1.              Give the adjacency matrix representing this graph.

2.              Give the adjacency lists representing this graph.

3.              Show the breadth-first search trees for the graph starting at node 0.

4.              Show the depth-first search trees for the graph starting at node 0.  

Question 7
 

Use Dijkstra’s Algorithm to find the shortest path of the following graph from node H to each of the other nodes.

 

  

 

 

Programming Questions 
 

In these programming questions you will experimenting writing  your own Binary Search Tree with a couple  of methods.

 

A Binary Search Tree (BST) is a tree-based data structure in which each node has at most two children, which are referred to as the left child and the right child, and the topmost node in the tree is called the root. It additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree.