Starting from:
$30
COMP2000-Assignment 1 Solved
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
a. the recursive algorithm. The program name is mergeSortR.c.
b. the iterative algorithm. The program name is mergeSortI.c. In your programs, the given array a is sorted in ascending order.
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.
a. the partition algorithm proposed by Lomuto. The program name is quickSortL.c.
b. the partition algorithm proposed by Hoare. The program name is quickSortH.c. In your programs, the given array a is sorted in ascending order.
3. Given an unsorted array containing n distinct integers, denoted as a[0..n - 1]. Write a complete C program named heapSort.c to implement the heap sort algorithm. In your program, the given array a is sorted in ascending order.
4. Write a complete C program named merge.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).
5. Write a complete C program named kSmallest.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.
6. An n×n 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 lowerTri.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
1
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 n×n matrix, denoted as a[0..n - 1][0..n - 1] is symmetric if aij = aji, 0 ≤ i, j ≤ n - 1. Write a complete C program named symMat.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 zigzag.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 hilCur.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.
a. the recursive algorithm. The program name is mergeSortR.c.
b. the iterative algorithm. The program name is mergeSortI.c. In your programs, the given array a is sorted in ascending order.
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.
a. the partition algorithm proposed by Lomuto. The program name is quickSortL.c.
b. the partition algorithm proposed by Hoare. The program name is quickSortH.c. In your programs, the given array a is sorted in ascending order.
3. Given an unsorted array containing n distinct integers, denoted as a[0..n - 1]. Write a complete C program named heapSort.c to implement the heap sort algorithm. In your program, the given array a is sorted in ascending order.
4. Write a complete C program named merge.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).
5. Write a complete C program named kSmallest.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.
6. An n×n 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 lowerTri.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
1
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 n×n matrix, denoted as a[0..n - 1][0..n - 1] is symmetric if aij = aji, 0 ≤ i, j ≤ n - 1. Write a complete C program named symMat.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 zigzag.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 hilCur.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.
1 file (15.5KB)
