Data Structures and Algorithms Assignment 3

CS210a Data Structures and Algorithms
Assignment 3

Total of 20 Marks
Submit through OWL a pdf file with your answers to the following questions. Remember that no late concept
assignments will be accepted. Yu might find this fact useful:
nX−1
i=1
i =
n(n − 1)
2
1. (2 marks) Consider a hash table of size N = 7 where we are going to store integer values. The
hash function is h(k) = k mod 7. Draw the table that results after inserting, in the given order, the
following values: 19, 27, 12, 47, 15. Assume that collisions are handled by separate chaining.
2. (2 marks) Show the result of the previous exercise, assuming collisions are handled by linear probing.
3. (2 marks) Repeat exercise (1) assuming collisions are handled by double hashing, using a secondary
hash function h
′
(k) = 5 − (k mod 5).
4. (3.5 marks) Solve the following recurrence equation using repeated substitution and give the order
of f(n). You must show how you solved the equation.
f(1) = 3
f(n) = f(n − 1) + 2n + 1
5.(i) (7 marks) A tree is called symmetric if for every internal node u all the children of u store the same
value. For example the following tree with root a is symmetric, but the tree with root b is not symmetric as one child of node v stores value 2 while the other stores 3.
Write in pseudocode an algorithm isSymmetric(r) that receives as input the root r of a tree and it
outputs the value true if the tree is symmetric and false if it is not. For a node v let v.value denote the
value stored in v. To access the children of a node r use the following pseudocode
for each child c of r do
a b 3
7 7 7
4 4 4 1 1 1 6
5 5
3
7 7 7
4 4 4 1 1 1 6
2 3
v
5.(ii) (3.5 marks) Compute the worst case time complexity of your algorithm as a function of the total
number n of nodes in the tree. You must
• explain what the worst case for the algorithm is
• explain how you computed the time complexity
• give the order of the time complexity of the algorithm
1