Question 1

Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps.

Question 2

Write the outputs for the following Matlab codes
f1=0;
f2=1;
for i = 1 : 10
f3=f2+f1;
disp(f3)
f1=f2;
f2=f3;
end

Question 3

(a) List and describe the operations that can be performed on a stack.

(b) For each operation given in (a), write the implementation using Matlab codes.

Question 4

(a) Construct a tree for the following list of alphabets assuming that a number smaller than the node goes to the left else it goes to the right.

16, 8, 4, 24, 9, 5, 23, 13, 22, 28, 6, 3, 7, 2, 15, 10, 12, 14, 19, 27, 29, 26, 31, 25, 30, 1, 11, 18, 21, 17, 20

(b) Perform inorder, postorder and preorder traversal with the following tree.

Question 5

Use Prim's algorithm (matrix form) to find a minimum spanning tree and calculate the minimum cost for the graph given below.

Question 6

Using Big-O estimate the execution time for the Matlab codes given below. Show clearly all your workings.

1. for i = 1:n-1
2. for j = 1:n-i
3. if a(j) > a(j+1)
4. c=a(j);
5. a(j)=a(j+1);
6. a(j+1)=c;
7. end
8. end
9. end

Question 7

Given the set of items S = {4, 8, 5, 1, 7, 6, 1, 4, 2, 2} and bins of size 10, pack the items into as few bins as possible using Best Fit and Worst Fit. Show all the intermediate steps.