deepayan.sarkar@gmail.com>$ gcc -o insertion_sort insertion_sort.c
Assignment 1 (due January 31): Modify the insertion sort code presented in class to implement the bubble sort algorithm:
BUBBLESORT(A)
for (i = 1, 2, ..., A.length) {
for (j = A.length, A.length-1, ..., i+1) {
if (A[j] < A[j-1]) {
exchange A[j] and A[j-1]
}
}
}
Your program should count and report the number of comparisons performed for random input data, as done in class for insertion sort.
Your solution should consist of a single file named according
to the pattern FirstnameLastname.c, which should be
emailed to me.
Assignment 2 (due February 7)
1. Prove that the algorithm PERMUTE-BY-SORTING
presented in class generates a uniform random permutation.
2. Prove or disprove: The following algorithm generates a uniform random permutation of its input.
RANDOMIZE-IN-PLACE(A)
n = A.length
for (i = 1, ..., n) {
Swap A[i] with A[ RANDOM(1, n) ]
}
Assignment 3 (due February 21)
Write a C program that takes as input an integer
n, and prints all permutations of {1, 2, ...,
n}. The value of n should preferably be
specified as a command-line argument, or as a
#define-d constant within the program.
Assignment 4 (due March 7)
Write a C program that takes an integer n as a
command-line input argument, and prints the number of comparisons
needed to perform insertion sort, merge sort, heapsort and
quicksort on one randomly generated array of size n
(the arrays may be different for the different sorting
algorithms).
Assignment 5 (due 14 March): The Towers of Hanoi puzzle consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in order of size on one rod, the smallest at the top. The objective of the puzzle is to move the entire stack to another rod using a sequence of moves. Each move consists of shifting the topmost disk on one rod to the top of another rod, with the restriction that no disk may be placed on top of a smaller disk.
The assignment is to write a C program that takes a single command-line argument that gives the number of disks, and outputs a sequence of moves that solve the puzzle. The output should consist of one line per move, and each line should have the number of the source and destination towers separated by a space (towers should be numbered 1, 2, 3).
Here is a possible solution to the puzzle, along with corresponding desired output, when there are five disks.
Submit by email a single C file named
hanoi.c.
Assignment 6 (due 11 April): Write a program that takes a
single integer n as argument, forms a binary search
tree with n random numbers as input, and prints the
depth of the tree thus created.
Hint: Use a variable to keep track of current height. When inserting a new element, compute the height of the node where it is to be stored, and update the current height variable if needed.