Right or Wrong?

Question 1

(a) Indicate whether each of the following statements is true or false. There is one mark for each correct answer and zero marks for each

incorrect answer.

[10 marks]

[Total for Question 1:  10 marks]

Proofs and Sequences

Question 2

(a) Write down the pseudocode for Katratsuba multiplication. [4 marks]

(b) Given n integers (each integer is from 0 to 100), give an efficientalgo- rithm for sorting them. [5 marks]

(c) Draw the binary heap structure that is equivalent to the following list (the root is first element).

[5, 9, 8, 12, 15, 11, 19, 14, 20, 18, 17, 13]             [4 marks]

(d)  Show the resulting tree after the value 6 is added to the heap in the part (c). Note that the binary heap properties must be restored after insertion.  Show your working; you may show the data structure in tree or array form. [3 marks]

[Total for Question 2:  16 marks]

Hashing and Skiplists

Question 3

(a) A hash function, h(x), hashes a name, x (the hash key), onto a hash value (the index into an array) as listed in the following table.  The hash table has a size of 8 (indexed from 0 to 7).

The keys are inserted into a hash table in the order listed in the fol- lowing table. Use the following collision resolution approaches as de- scribed in the lectures/tutorials.

Show the hash table contents after insertion with:

i. chaining [2 marks]

ii. linear probing [2 marks]

iii. quadratic probing [2 marks]

iv. For a hash table based on linear probing with n elements, what is the worst-case complexity for deleting an element. [3 marks]

(b) Derive the expression for the expected height H of an element inserted into a skiplist. [3 marks]

(c) Given a specific list of keys, h1 (key) maps the keys uniformly to values from 0 to 13. h2 (key) maps the keys uniformly to values from 0 to 25. Now I want to build a hash table of size around 39 (still only dealing with the original set of keys).  Is using h(key) = h1 (key) + h2 (key) a good idea? Why or why not? [2 marks]

[Total for Question 3:  14 marks]

Trees

Question 4

(a) Draw a maximally balanced binary search tree that can be produced from the elements:  1, 2, 3, 4, 5, 6, 7, 8, 9.  Hint:  a maximally balanced binary search tree minimises the average depth of its elements. [3 marks]

(b) Draw a sequence of diagrams showing the insertion of the values:

[1,9,8,7,2,3,6,4,5]

into an empty AVL tree, in the order shown above.

You must:

● Show the resulting tree immediately after each insertion step (that is before any balancing has taken place).

● Show the resulting tree after balancing operation(s). [10 marks]

(c) What are the requirements for a tree to be a 5-way B-tree? [6 marks]

(d) What is the complexity for searching/adding/removing from an AVL

tree with nnodes. What is the complexity for searching/adding/removing from a 5-way B-tree with n nodes. [6 marks]

[Total for Question 4: 25 marks]

Graph Representations and Traversals

Question 5

(a) Write pseudo-code for an algorithm that performs depth-first search of a directed graph:  G  =  (V, E) and prints out all of the nodes as they are checked. Note: a node is checked when it is inspected by the algorithm for the first time. [9 marks]

(b)  State the storage requirements of a graph with n nodes and m edges using:

1.  an adjacency list, and

2. an adjacency matrix

briefly justify each answer. [4 marks]

(c) Given a directed graph G  =  (V, E).  We know that the edges have nonnegative costs. Also, there are a lot of edges with 0 costs. Given a source nodes, we need to find out which nodes have 0 distance from s. Propose an algorithm for this problem. [5 marks]

[Total for Question 5:  18 marks]

Shortest Path Algorithms

Question 6

(a) Breadth-first search (BFS) can be used to perform single source short- est paths on any graph where all edges have the same costs 1.  Write an algorithm using BFS to assign distances to all nodes in a graph. [7 marks]

(b) If we change the setting of part  (a) this way:  all edges have costs 1 except for a constant number of edges, which all have costs 2.  Can you still use BFS to assign distances? [3 marks]

(c) Consider the following graph:

Solve the single-source-shortest path problem for the start node v1 using Dijkstra’s algorithm. List for each iteration which nodes becomes scanned. [9 marks]

(d) Briefly explain, with the use of an example, why Dijkstra’s algorithm will not work on graphs with negative weight edges. [4 marks]

[Total for Question 6: 23 marks]