Assignment1

University of Moratuwa
Faculty of Information Technology

Algorithms & Data Structures
Assignment 1 – 10 Marks


Question 1)
Implement the following sorting algorithms (You can use any language)
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Bubble sort with Boolean flag to check swapping
e) Selection sort with Boolean flag to check swapping

Analyze above sorting methods and give the time complexities in best, average and worst cases.
Can we omit using Boolean flag for insertion sort to check whether it’s already sorted? Explain your answer.

Question 2)
Implement the following using recursive algorithms (You can use any language)
a) Calculating power of 2
b) Print numbers from n to 0.
c) Checking if a number n is prime. (You have to check whether n is divisible by any number below n)

Question 3) Consider two integer arrays t and p. For example: int[] t = {1,2,1,2,3,2,1,3,0,0,1,2,0,3,2,1,1,3,3}; int[] p = {2,1,1,3}; Write a method that takes two integer arrays (t and p) as input and outputs a boolean: true if there is a match between t and p somewhere along the array, false if there is no match. In the example above the output would be true, since there is a match at position 14-17 in t. Position in t: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 t: 1 2 1 2 3 2 1 3 0 0 1 2 0 3 2 1 1 3 3p: 2 1 1 3

Analyze the code you have written and give a good asymptotic upper bound for your program.



Question 4)
Write a brief description about following sorting methods, their code, time complexity and suitability of using as a sorting method

Shell Sort
Radix Sort



Note: Solutions should be submitted to it201_assignment@yahoo.com.
Attach all documents and sample programs in a zip file.
Sample programs should be able to execute and observe the results.
Due date: 30th October 2004.