Home 
In your assignment please be brief, clear and precise. When you are describing an algorithm, avoid unnecessary details such as declaring that i is an integer. Be sure however to explain the nonobvious steps in your algorithm and of course any data structures used. Any assumptions must also be stated clearly. All diagrams must be clear and neat. You may use a dark pencil or ink for this assignment . The assignment consists of 6 questions. Attempt all questions. Total 100 marks 1. Given two sorted lists L1 and L2 and using only the basic operations defined for linked lists (insert, find, remove, next) write procedures in pseudocode to compute the following. (a) The intersection of L1 and L2 (b) The union of L1 and L2 Comment on the running times of your procedures. Illustrate your procedures using the following list values. L1 = {1,5,8,23,34,46,72} L2 = {3,9,17,23,31,42,46,75} [10 marks] 2. (a) Write routines in pseudocode to implement 2 stacks using 1 array. The routines should not declare a stack overflow unless every slot in the array is used. (b) Describe how you would implement 3 stacks using 1 array. (Note: This is only a description, no pseudocode is necessary). [15 Marks] 3. Devise an algorithm in pseudocode that takes two values, a and b, such that a £ b, and which prints all the keys x in a binary search tree such that a£ x £ b. The running time of your algorithm should be O(N+log n) , where N is the number of keys visited and n is the number of keys in the tree. Justify the running time of your algorithm. [15 marks]
4. (i) For each of the following key sequences draw the resulting binary search tree obtained when the keys are inserted one by one in the order given into an initially empty tree. (note you only need to show the final tree) a. 1,2,3,4,5,6,7 b. 4,2,1,3,6,5,7 c. 1,6,7,2,4,3,5 (ii) For each of the binary trees obtained, determine the resulting tree when the root is removed. (iii) Repeat parts i and ii for AVL trees. [25 marks]
5. Consider two sets of integers, S= {s1, s2,…, sm} and T= {t1, t2,…, tn}. (a) Devise an algorithm in pseudocode that uses a hash table to test whether or not S is a subset of T (S Í T). What is the average running time of your algorithm? (b) Two sets are equivalent if and only if both S Í T and T Í S. Show that we can test if two sets of integers are equivalent in O(m+n) time (on average). [15 marks]
6. Exercise 6.17 page 247 from Text. Parts a,b and c. Note that no pseudocode is necessary. Just an explanation of the algorithm would suffice. Show clearly why your algorithm will run in the specified time bound. [20 marks]
We use the fact that the lists are sorted to create a q(n) algorithm. (a) Intersection The algorithm is based on assigning pointers to the start of both lists. If the elements pointed to by the pointers are equal then print the element and increment both pointers. Otherwise increment the pointer whose value is lower. Pseudocode is as follows: We use ptr1.element to refer to the value stored at the node in list L1 We use ptr2.element to refer to the value stored at the node in list L2
While ptr1 ¹ NULL AND ptr2 ¹ NULL If ptr1.element = ptr2.element Print ptr1.element ptr1 < ptr1.next ptr2 < ptr2.next else if ptr1.element < ptr2.element ptr1 = ptr1.next else if ptr1.element > ptr2.element ptr2 = ptr2.next endif enddo The running time is actually bounded by the length of the shorter list. Hence let m be the number of elements in list L1 and m be the number of elements in list L2. The running time is O(min(m,n)) if m ¹ n and O(m) if m = n. (b) Union The idea is to maintain the order of the elements Again we assign pointers to the start of both lists. This algorithm is very similar to a merge algorithm. Print the value of the lesser element and increment its corresponding pointer. If the element is the same for both pointers, print one and increment both pointers. At the end of any list, print the remaining nodes for the longer list. While ptr1 ¹ NULL AND ptr2 ¹ NULL If ptr1.element < ptr2.element Print ptr1.element ptr1 < ptr1.next else if ptr1.element > ptr2.element Print ptr2.element ptr2 = ptr2.next else if ptr1.element = ptr2.element Print ptr1.element ptr1 = ptr1.next ptr2 = ptr2.next endif enddo while ptr1 ¹ NULL Print ptr1.element ptr1 < ptr1.next enddo
while ptr2 ¹ NULL Print ptr2.element ptr1 < ptr2.next enddo The running time is actually bounded by the length of both lists. Hence let m be the number of elements in list L1 and m be the number of elements in list L2. In the worst case where no elements are the same, the running time is O(m+n). In the best case where all elements are the same, the running time is O(m).
(a) Two stacks can be implemented in an array [0..n] by having one grow from the low end of the array [0] up and the other grow from the high end of the array [n] down. (b) Three stacks can be implemented by having one grow from the bottom [0] up, another from the top [n] down and a third somewhere in the middle growing is some arbitrary direction. If the third stack collides with either of the other two, it needs to be moved. A reasonable strategy is to move its so that its center (at the time of the move) is halfway between the tops of the other two stacks. Any reasonable design should be considered.
The algorithm is actually easiest as a recursive algorithm: T refers to the root of the tree. Printrange(a,b,*T) If (a <= T.element) Printrange(a,b,T.leftchild) If (a <= T.element AND T.element <= b) Print T.element If (T.element <= a) Printrange(a,b,T.rightchild) The running time is essentially a combination of the time taken to traverse the tree (in order traversal) if a significant number of nodes are within the range and the time taken to get to the leaves if for example no nodes are found. This is the time taken to look up the next node in the range. Hence since the average depth of the tree is O(log n) this gives O(N + log n).
Given two sequences S and T, (a) If S Í T then every element S must be in T. Therefore, the simplest way of doing this is as follows: Use a simple hash function to hash the elements in T. Separate chaining will suffice for this situation, Although one could apply an open addressing scheme such as linear probing etc. Next, we have to hash the elements of S, into the same table. Now, each element in S is hashed in sequence. In order to hash the elements we must first perform a find. So, if the find returns false for any element in S then we know that SË T. If the find returns TRUE (collision) for all elements of S, then S Í T. The entire algorithm would take nl/2 operations to hash set T and then ml/2 operations to hash set S. Hence the average case running time is O(l/2 (m+n)). If we make the table large enough such that l =1 we get O(m+n) in the average case. (b) If S Í T and T Í S then S and T are identical. We can perform the above algorithm to test S Í T. If all finds return TRUE, then we hash S in an empty hash table and then hash into the same table. This tests that T Í S. The running time is obviously twice that as testing only one subset. Hence we have 2(m+n) operations wish yields O(m+n).
The students need only provide answers for parts a and b for full marks. Part c was awarded for bonus marks. (a) If l = r, then place µ (negative infinity or some extremely small number) as the root with the two heaps as subtrees and do a deleteMin. (b) If l – r = 1, place µ (negative infinity or some extremely small number) as the root with the two heaps as subtrees. However, you have to put the larger heap on the left and the smaller heap on the right. This preserves the heap structural property (filling left to right) . Then do a deleteMin. (c) (Bonus only) The answer supplied by the author for this question is quite confusing so I will supply the answer provided by the author and also my own solution. The answer supplied by the author: Split the larger heap into smaller heaps as follows: on the leftmost path remove two subheaps of height r1, then one of height r, r+1 and so on until l2. Then merge the trees going smaller to higher using the results of parts (a) and (b) with the extra nodes on the left path substituting for the insertion of infinity and subsequent deleting. My Solution: Assume r > l Since both heaps are full complete trees, subdivide the larger heap R by starting at the rightmost leaf and moving up the rightmost path to towards the root. When we get to a node that is of height l1, then merge the subtree rooted at this node with the smaller tree L using the solution to part a. Remove the subtree from R, the larger tree and continue to merge the subtrees rooted at subsequent nodes along the rightmost path of R along the path to the root, to tree L using the answer to part b.

