Home

Home

Products

 Assignment # 2 February 26 2001

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 non-obvious 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]

 Assignment 2 Solutions
 Question 1

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).

 Question 2

(a)    Two stacks can be implemented in an array [0..n] by having one grow from the low end of the array  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  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.

 Question 3

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).

 Question 4

1. (a) After removing the root Node (b) If the root is to be removed, we can exchange the root with the leftmost child of the right sub-tree, or the rightmost child of the left sub-tree. In this case, one exchange puts the root at a leaf node which we can easily delete. The following two trees are possible.

Using the rightmost child of the left sub-tree. The leftmost child of the right sub-tree 4(c) To remove the root node. This can actually be done in two ways., We can move the node down the tree until it becomes a leaf node. Hence we perform two swaps. Node 1 with node 2, then the new node 1 with node 3. Then delete node 1 which is now a leaf node. This gives the following: Or following the method in the text, we can delete the node if it has just one child by adjusting its parent pointers. This needs only one swap. 4(iii) Building the AVL trees. Since the trees are always balanced, all inputs result in the same tree for parts a,b,c. It follows that removing the root would result in the same tree also for parts a,b,c Question 5

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).

 Question 6

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 sub-trees  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 sub-trees. 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 sub-heaps of height r-1, then one of height r, r+1 and so on until l-2. 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 l-1, then merge the sub-tree rooted at this node with the smaller tree L using the solution to part a. Remove the sub-tree from R, the larger tree and continue to merge the sub-trees 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.