Assignment 1
a. Sort the sequence 3, 7, 4, 1, 5, 2, 8, 6, 9 using Insertion sort (show the steps on your
paper)
b. Please write C program for Insertion sort, using sequence of question a as input.
Assignment 2
a. Sort the following array using Merge Sort (show the steps on your paper)
b. Please write C program for Merge sort, using sequence of question a as input.
c. Please write C program for Merge sort without using recursion
d. Please modify the program of question b as following:
– In practical, if the sub-lists are less than some threshold length (cutoff), use an algorithm
like insertion sort to sort the lists
– Otherwise, use Merge sort, again
– Modify your program with cutoff = 5
Assignment 3
a. Sort the following array using Quick Sort (show the steps on your paper)
b. Please write C program for Quick sort with random pivot, using sequence of question a as
input. Please show the running time of this program.
c. Please modify program of question b with median-of-three pivot.
d. Please modify the program of question b as following:
– In practical, if the sub-lists are less than some threshold length (for example 10), use an
algorithm like insertion sort to sort the lists
– Otherwise, use Quick sort, again
Assignment 4 Sort 3, 1,4, 1,5,9,2, 6,5,3,5 using quicksort with median-of-three partitioning
and a cutoff of 3.
Assignment 5
a. Sort an array of 0’s, 1’s and 2’s: Given an array A[] consisting of 0’s, 1’s and 2’s, give an
algorithm for sorting A[]. The algorithm should put all 0’s first, then all 1’s and all 2’s last.
Example: Input = {0,1,1,0,1,2,1,2,0,0,0,1}, Output = {0,0,0,0,0,1,1,1,1,1,2,2}
b. Is there any other way of solving question a with the same time complexity.
Assignment 6
Determine the running time of merge sort and quicksort for
a. sorted input
b. reverse-ordered input
c. random input
Assignment 7 (Searching)
Given an array A[0...n– 1] of n numbers containing the repetition of some number. Give an
algorithm for checking whether there are repeated elements or not. Assume that we are not
allowed to use additional space but we can use recursive algorithm. (We can use few temporary
variables and recursive function)
Hint: you should give an algorithm with O(nlogn)