CS2040S Tutorial 2
Name: Ravichandran Gokul
Matriculation No.: A0309353E
Q1a) O(n)
b) O(n log n)
c) O(n^2)
d) O(n log n)
e) O(^n)
f) O(n log n)
g) O(n^2)
Q2a)
Recurrence relation:
T(n) = T(n – 1) + O(n)
Upon analysing this recurrence relation, we will find out that the order of
growth of this recursive implementation of insertion sort is O(n^2)
2b) We can use MergeSort to sort the array of pairs according to their
head value. Now, the array is sorted into subarrays of pairs with the same
element in the head. Now, we can use SelectionSort to sort these
subarrays according to the value in the tail of the pairs.
2c) Instead of splitting the problem into two halves during each function
call of MergeSort in the recursive method, we can sort the array from
bottom up, iteratively merging the subarrays as we progress. In this
method, we would only need to use the same space as that required for
another array of the same size as the argument array. Hence, the order of
growth in terms of space for this iterative version would only be O(n).
Q3a and b)
Stack
Queue
3c) We would probably need some sort of error handling to handle cases
where the array is full.
3d) Push in the first element into the stack. If the element is ),
immediately return that the sequence is imbalanced. If it is (, continue
pushing in elements into the stack. If the subsequent element is ), pop the
last two elements i.e., (). Once all elements have been passed through the
stack, if the stack still has elements, the sequence is imbalanced.
3e) I think the same method as for the previous question would apply for
this one as well.
Q4) Traverse through the array, pushing the elements into the stack up till
the hill we are standing on. Store the index of that hill. Pop the elements
in the stack if they have a smaller index then the hill we are standing on.
Once, we reach a hill that’s bigger than us, stop popping. The index of our
hill minus the index of the last hill in the stack is how far we can see.
