[Solved] COMP 2000 Assignment 1

1. 1. Given an unsorted array containing n distinct integers, denoted as a[0..n 1]. Write complete C programs to implement the merge sort algorithms by using
2. the recursive algorithm. The program name is c.
3. the iterative algorithm. The program name is c. In your programs, the given array a is sorted in ascending order.
4. 2. Given an unsorted array containing n distinct integers, denoted as a[0..n 1]. Write complete C programs to implement the quick sort algorithms.
5. the partition algorithm proposed by Lomuto. The program name is c.
6. the partition algorithm proposed by Hoare. The program name is c. In your programs, the given array a is sorted in ascending order.
7. Given an unsorted array containing n distinct integers, denoted as a[0..n 1]. Write a complete C program named c to implement the heap sort algorithm. In your program, the given array a is sorted in ascending order.
8. Write a complete C program named c to merge two sorted arrays of integers. In your program, the merge() function merges two arrays of integers a and b that are sorted in ascending order into an array of integers c that is also sorted in ascending order. Assume that the numbers of elements of a and b are m and n, respectively. The merge() function is called in the main() function as follows: c = merge(a, m, b, n).
9. Write a complete C program named c to find the kth smallest element of an unsorted array containing n distinct integers, denoted as a[0..n 1]. In your program, the kSmallest() function returns the kth-smallest number a[k] (0 k n 1) of the given array without sorting the array.
10. An nn lower-triangular matrix, denoted as a[0..n 1][0..n 1], is one in which all elements above the main diagonal are zero and the non-zero elements are all found on or below the main diagonal. Write a complete C program named c to transfer the elements of the matrix a to a one-dimensional array b, denoted as b[0..n(n + 1)/2 1] and vice versa. In your

program, the tran2Dto1DTM() function stores the elements of a to b and the tran1Dto2DTM() function transfers the elements of b back to a.

7. An nn matrix, denoted as a[0..n 1][0..n 1] is symmetric if a_ij = a_ji, 0 i, j n 1. Write a complete C program named c to transfer the elements of the symmetric matrix a to a one-dimensional array b, denoted as b[0..n(n + 1)/2 1] and vice versa. In your program, the tran2Dto1DSM() function stores the elements of a to b and the tran1Dto2DSM() function transfers the elements of b back to a.
8. Write a complete C program named c to display the elements of a 2D array a[0..H 1][0..W 1] by using the zigzag scan order as shown below.
9. Write a complete C program named c to display the elements of a 2D array a[0..H 1][0..W 1] by using the Hilbert-curve scan order as shown below.