CM2035 Algorithms and Data Structures II 2020
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CM2035
BSc EXAMINATION
COMPUTER SCIENCE
Algorithms and Data Structures II
Question 1
The following algorithms, A1 and A2, solve the same problem. To do so, they receive as input arguments:
root: the root of a binary search tree (BST) storing integer numbers
x: an integer number
ALGORITHM 1 function A1(root, x) Q = new Queue() ENQUEUE(Q,root) while !ISEMPTY(Q) do t = PEEK(Q) if (t==x) return TRUE else ENQUEUE(Q,left(t) ) ENQUEUE(Q,right(t )) DEQUEUE(Q) end while return FALSE end function Note: the function ENQUEUE only inserts a new element in the queue if this element is different from NULL |
ALGORITHM 2 function A2(root,x) if (root==NULL) return FALSE else if(x == root->data) return TRUE else if (x< root->data) return A2(root- >left,x) else return A2(root- >right,x) end function |
(a) For the following BST:
What is the content of the queue immediately before returning from the
execution of A1(root,21)? [4]
(b) For the following BST: [4]
What is the return value of A2(root, 20)?
(d) What is the worst-case time complexity of A1? Use Theta notation [1] and explain your reasoning [3] [4]
(e) Assuming a fully balanced BST (a BST with all its levels fully populated) of N
elements, what is the recurrence equation describing the running time of A2? [4]
(f) What is the worst-case time complexity of A2? Use Theta notation [1] and
(g) Which algorithm do you recommend implementing? Why? [6]
The data structure shown in Figure 1 can be thought as a list of two lists. In this case, the data structure is used to classify numbers in one of 2 groups: even numbers and odd numbers.
Figure 1. A list of two lists
The first node of the main list (the list drawn horizontally, made of shaded nodes) stores a number 0 to signal that the numbers stored in its secondary list (the list drawn vertically, ‘hanging’ from node storing number 0) are even (in the figure, the numbers 2 and 18). The second node of the main list stores a number 1, to signal that the numbers stored in its secondary list (in the figure, the numbers 9, 3 and 15) are odd.
(a) In a single linked list implemented in C++ this is the definition of a node: [6]
struct Node {
int data;
Node *next;
};
This definition is useful for the nodes belonging to the secondary lists, but not for the nodes belonging to the main list. Main list nodes need two pointers (one for the next node in the main list and one for the first node in the secondary list). Assuming that the above definition is kept for the nodes of the secondary lists, propose a new definition of node for the nodes of the main list. Call this type of node Node_main and use the names of pointers given in Figure 1.
(b) Write the pseudocode of the function INSERT(head,x) that inserts a new number in this data structure. If the number is even it must go to the first secondary list (the one ‘hanging’ from node 0 in the main list). Otherwise, it must go to the second secondary list. Assume the data structure already has the main list created
and numbers are inserted at the start of the secondary list. [8]
(c) Write the pseudocode of the function SEARCH(head,x) that returns TRUE if the number x is in the data structure (in any of the secondary lists) and FALSE otherwise. [8]
(d) Write the pseudocode of the function DELETE(head, b) that receives as input arguments the head of the last of two lists and a Boolean value. The function DELETE(head,b) deletes one of the main nodes. If b equals 0, then the node storing number 0 is deleted. Otherwise, the main node storing number 1 is deleted. Consider the following cases: the main list is empty and it has only one node (node
0 or 1). [8]
Question 3
A software developer needs to solve the following problem: given the adjacency matrix of an undirected weighted graph, find the value of the k-th minimum cost edge. Assume that all edge weights are different, that they are non-negative integer numbers, and that they are not greater than 999. The number 1000 (one thousand) signals the absence of an edge.
For example, for the graph represented by the following adjacency matrix M:
A B C D
1000 |
3 |
1 |
5 |
3 |
1000 |
7 |
4 |
1 |
7 |
1000 |
9 |
5 |
4 |
9 |
1000 |
The first minimum (that is, k=1) is 1, the second minimum (k=2) is 3, the third minimum (k=3) is 4, and so on.
The design of the algorithm must take as input arguments the adjacency matrix (M), its number of nodes (N) and the value of k. It must return the value of the k-th minimum cost edge.
The software developer came up with these two algorithms to solve the problem:
Algorithm 1:
1. Make a copy of the adjacency matrix. Call the copy M_copy.
2. Create a variable, called min, where the minimum value is recorded
3. Create a variable, called count. Initialise its value to 0
4. Visit every element of M_copy, from top to bottom, from left to right and record the minimum value in min
5. Once the minimum value is found, increase the variable count by one unit
6. If the condition count==k is true, return the value of min. Otherwise, delete the minimum value from M_copy (write number 1000 in the corresponding positions) and repeat steps 2-6
Algorithm 2:
. Create a min-heap storing the values of all edges
. Perform EXTRACT_MIN k times. The value last extracted is the k-th
minimum.
(a) Write the pseudocode of Algorithm 1. [8]
(b) Write the pseudocode of Algorithm 2. Assume you already have
implemented the following min-heap functions:
RTD_,(.ors(W)t-(o)ca(rst)s(-)et(T)
. EXTRACT_MIN(heap): return the minimum value stored in the min-heap.
Worst-case Theta(logN)
That is, you can use these functions with no need to write the pseudocode for them.
(c) What are the worst-case time complexities of A1 and A2? Use Theta-
notation. Justify your findings. [8]
(d) What algorithm do you recommend for implementation? Justify in terms of worst-case time complexity. [6]
2023-03-03