COMP225 TUTORIAL EXERCISES WEEK 6

COMP225 Tutorial Exercises for Week 7

(*) Recall the lecture concerning merging two trees for assignment 2. Sketch the trees corresponding to the serialised output from two saved games. Call the first t1 and the second t2.
t1 is:
```
T: does it eat catfood?
  T: Is it a cat?
    N:
    N:
  T: Is it a dog?
    N:
    N:
```
t2 is:
```
T: does it have a blue tongue?
  T: Is it a giraffe?
    N:
    N:
  T: Is it an octopus?
    N:
    N:
```
1. Sketch the two binary trees t1 and t2.
2. Consider merging the two trees as discussed in lectures. Using the case analysis from lectures, sketch the merged tree.
3. Call the merged tree t3. Let t3= merge(t1, t2), where the specification of the merging function is given by
```
QuestionNode *merge(QuestionNode *qN1, QuestionNode *qN2);
// Returns the merge of qN1 and qN2
```
  Write down expressions involving t1, t2 and merge for the subtrees t3->yes t3->no.
Consider the following problem for finding the longest strictly increasing subsequence. Given an array A of length n having integer values, determine the maximum length of a subsequence (not necessarily contiguous) in which the values in the subsequence form a strictly increasing sequence. (Recall that a subsequence of an array is obtained by ``crossing out" elements.) (How many subsequences are there, and what does this tell you about the complexity of the brute-force method for computing this?)
For example if the array is [2, 4, 3, 5, 3, 7] then the longest strictly increasing subsequence has length 4 (and it is [2, 4, 5,7]).
Now define the array L[] such that L[i] is the length of the longest strictly increasing subsequence A[0..i] which includes the item A[i].
1. Complete the following table.
```
i	L[i]	Example subsequence

0	1		[2]
1	2		[2,4]
2	1		[3]
3
4
5
```
2. Write a program to compute L[]
```
void seq(int A[], int n, int L[]);
//PRE: A and L are arrays of length n
//POST: For all j with 0 <= j < n, L[j] is the length of the longest increasing subsequence in A[0..j]
//      which includes item A[j]
```
3. Now show how you would use L[i] to solve the original problem. What is the overall complexity? State your reasons.
Trace the radix sort algorithn for the following list of letters.
```
 BCA, ABC, CAB, ACB, BAC, CBA
```
Suppose that during one pass of the radix sort algorithm to sort the elements for attribute k, it is found that the items were already sorted with respect to that attribute. Explain how that situation can be identified by inspecting the counters. Now adjust the implementation given in lectures for radix sort to take advantage of this observation to improve efficiency.
Answers to all of the above starred questions should be handed in to your tutor at your scheduled tutorial in Week 7.
All enquiries to Annabelle McIver