Starting from:
$29
Homework #1 – Algorithm Efficiency and Sorting
Homework #1 – Algorithm Efficiency and Sorting
Question 1 – 30 points (a) [11 points] Sort the functions below in the increasing order of their asymptotic complexity (Use < and = signs during ordering. For example, if the asymptotic complexity of fx(n)=o(fy(n)), i.e., fx(n) is “less than” fy(n), use fx(n) < fy(n); if they are equal, i.e., fx(n)= (fy(n)), use fx(n) = fy(n)): f1(n) = nlog(logn), f2(n) = n, f3(n) = n3, f4(n) = n1/logn, f5(n) = n logn, f6(n) = (logn)logn, f7(n) = en, f8(n) = log2n, f9(n) = log n, f10(n) = 2logn , f11(n) = n! (b) [9 points] Find the asymptotic running times (in notation, tight bound) of the following recurrence equations by using the repeated substitution method. Show your steps in detail. T(n) = 9 T(n/3) + n2, T(1) = 1 where n is an exact power of 3 T(n) = T(n/2) + 2, T(1) = 1 where n is an exact power of 2 (c) [10 points] Trace the following sorting algorithms to sort the array [ 4, 9, 7, 3, 5, 2, 1, 6 ] in ascending order. Use the array implementation of the algorithms as described in the textbook and show all major steps (after each sort pass for instance). Insertion sort Bubble sort
Question 2 – 50 points You are asked to implement the selection sort (10 points), merge sort (10 points), and quick sort (10 points) algorithms for an array of integers and then perform the measurements as detailed below. For each algorithm, implement the functions that take an array of integers and the size of the array and then sort it in non-ascending (descending) order. Add two counters to count and return the number of key comparisons and the number of data moves during sorting. For key comparisons, you should count each comparison like “k1 < k2” as one comparison, where k1 and k2 correspond to the value of an array entry (that is, they are either an array entry like arr[i] or a local variable that temporarily keeps the value of an array entry). For data moves, you should count each assignment as one move, where either the right-hand side of this assignment or its left-hand side or both of its sides correspond to the value of an array entry. For example, the following swap function has three such assignments (and thus three data moves): void swap(DataType &x, DataType &y) { DataType temp = x; x = y; y = temp; } For the quick sort algorithm, you are supposed to take the first element of the array as the pivot. After implementing the sorting algorithms, implement a function named performanceAnalysis (20 points) which does the followings: 1. Create three identical arrays with random 1000 integers using the random number generator function rand. Use one of the arrays for the selection sort, another one for the merge sort, and the last one for the quick sort algorithm. Output the elapsed time in milliseconds, the number of key comparisons, the number of data moves (use clock from ctime for calculating elapsed time). 2. Now, instead of creating arrays of random integers, create arrays with elements in ascending order and repeat the steps in part 1. 3. Now, instead of creating arrays of random integers, create arrays with elements in descending order and repeat the steps in part 1. 4. Lastly, instead of creating arrays of random integers, create arrays with elements in ascending order up to its half size and in descending order in the rest, and repeat the steps in part 1. 5. Repeat the experiment (parts 1-4) for the following array sizes: {6000, 12000, 18000}, given as input to performanceAnalysis (total of four different sizes).
When the performanceAnalysis function is called, it needs to produce an output similar to the following one:
Performance analysis for arrays of size 1000 ------------------------------------------------------------------------------------------- Random integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort ------------------------------------------------------------------------------------------- Ascending integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort …
Performance analysis for arrays of size 6000 ------------------------------------------------------------------------------------------- Random integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort ... Put the implementations of these functions in a file named sorting.cpp, and their interfaces in a file named sorting.h. Also write a main function separately inside a file named main.cpp that calls only the performanceAnalysis function inside. Although you will write your own main function to get the experimental results, we will also write our own main function to test whether or not your algorithms work correctly. In our main function, we will call your sorting algorithms with the following prototypes: void selectionSort( int *arr, int size, int &compCount, int &moveCount ); void mergeSort( int *arr, int size, int &compCount, int &moveCount ); void quickSort( int *arr, int size, int &compCount, int &moveCount ); void performanceAnalysis( int size ); In all of these prototypes, arr is the array that the algorithm will sort, size is the array size, compCount is the number of key comparisons in sorting, and moveCount is the number of data moves in sorting. After returning from this function, arr should become sorted.
IMPORTANT: At the end, write a basic Makefile which compiles all your code and creates an executable file named hw1. Check out these tutorials for writing a simple make file: http://mrbook.org/blog/tutorials/make/, http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/.
Question 3 – 20 points After running your programs, you are expected to prepare a 2-3 page report about the experimental results that you obtained in Question-2. First, prepare tables for presenting the results for the number of key comparisons, the number of data moves, and the elapsed time. You should prepare a separate table for each required number. For each table, each row should include the type of the input (e.g., R1K - array with 1000 random integers, A1K - array with 1000 ascending integers, D1K - array with 1000 descending integers, M1K - array with 500 ascending and 500 descending integers, etc.) and the values obtained by selection sort, merge sort and quick sort in four separate columns. Then, with the help of a spreadsheet program (Microsoft Excel, Matlab or other tools), present your experimental results graphically. Interpret and compare your empirical results with the theoretical ones for each sorting algorithm. Explain any differences between the empirical and theoretical results, if any.
Question 1 – 30 points (a) [11 points] Sort the functions below in the increasing order of their asymptotic complexity (Use < and = signs during ordering. For example, if the asymptotic complexity of fx(n)=o(fy(n)), i.e., fx(n) is “less than” fy(n), use fx(n) < fy(n); if they are equal, i.e., fx(n)= (fy(n)), use fx(n) = fy(n)): f1(n) = nlog(logn), f2(n) = n, f3(n) = n3, f4(n) = n1/logn, f5(n) = n logn, f6(n) = (logn)logn, f7(n) = en, f8(n) = log2n, f9(n) = log n, f10(n) = 2logn , f11(n) = n! (b) [9 points] Find the asymptotic running times (in notation, tight bound) of the following recurrence equations by using the repeated substitution method. Show your steps in detail. T(n) = 9 T(n/3) + n2, T(1) = 1 where n is an exact power of 3 T(n) = T(n/2) + 2, T(1) = 1 where n is an exact power of 2 (c) [10 points] Trace the following sorting algorithms to sort the array [ 4, 9, 7, 3, 5, 2, 1, 6 ] in ascending order. Use the array implementation of the algorithms as described in the textbook and show all major steps (after each sort pass for instance). Insertion sort Bubble sort
Question 2 – 50 points You are asked to implement the selection sort (10 points), merge sort (10 points), and quick sort (10 points) algorithms for an array of integers and then perform the measurements as detailed below. For each algorithm, implement the functions that take an array of integers and the size of the array and then sort it in non-ascending (descending) order. Add two counters to count and return the number of key comparisons and the number of data moves during sorting. For key comparisons, you should count each comparison like “k1 < k2” as one comparison, where k1 and k2 correspond to the value of an array entry (that is, they are either an array entry like arr[i] or a local variable that temporarily keeps the value of an array entry). For data moves, you should count each assignment as one move, where either the right-hand side of this assignment or its left-hand side or both of its sides correspond to the value of an array entry. For example, the following swap function has three such assignments (and thus three data moves): void swap(DataType &x, DataType &y) { DataType temp = x; x = y; y = temp; } For the quick sort algorithm, you are supposed to take the first element of the array as the pivot. After implementing the sorting algorithms, implement a function named performanceAnalysis (20 points) which does the followings: 1. Create three identical arrays with random 1000 integers using the random number generator function rand. Use one of the arrays for the selection sort, another one for the merge sort, and the last one for the quick sort algorithm. Output the elapsed time in milliseconds, the number of key comparisons, the number of data moves (use clock from ctime for calculating elapsed time). 2. Now, instead of creating arrays of random integers, create arrays with elements in ascending order and repeat the steps in part 1. 3. Now, instead of creating arrays of random integers, create arrays with elements in descending order and repeat the steps in part 1. 4. Lastly, instead of creating arrays of random integers, create arrays with elements in ascending order up to its half size and in descending order in the rest, and repeat the steps in part 1. 5. Repeat the experiment (parts 1-4) for the following array sizes: {6000, 12000, 18000}, given as input to performanceAnalysis (total of four different sizes).
When the performanceAnalysis function is called, it needs to produce an output similar to the following one:
Performance analysis for arrays of size 1000 ------------------------------------------------------------------------------------------- Random integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort ------------------------------------------------------------------------------------------- Ascending integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort …
Performance analysis for arrays of size 6000 ------------------------------------------------------------------------------------------- Random integers Elapsed time compCount moveCount Selection sort Merge sort Quick sort ... Put the implementations of these functions in a file named sorting.cpp, and their interfaces in a file named sorting.h. Also write a main function separately inside a file named main.cpp that calls only the performanceAnalysis function inside. Although you will write your own main function to get the experimental results, we will also write our own main function to test whether or not your algorithms work correctly. In our main function, we will call your sorting algorithms with the following prototypes: void selectionSort( int *arr, int size, int &compCount, int &moveCount ); void mergeSort( int *arr, int size, int &compCount, int &moveCount ); void quickSort( int *arr, int size, int &compCount, int &moveCount ); void performanceAnalysis( int size ); In all of these prototypes, arr is the array that the algorithm will sort, size is the array size, compCount is the number of key comparisons in sorting, and moveCount is the number of data moves in sorting. After returning from this function, arr should become sorted.
IMPORTANT: At the end, write a basic Makefile which compiles all your code and creates an executable file named hw1. Check out these tutorials for writing a simple make file: http://mrbook.org/blog/tutorials/make/, http://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/.
Question 3 – 20 points After running your programs, you are expected to prepare a 2-3 page report about the experimental results that you obtained in Question-2. First, prepare tables for presenting the results for the number of key comparisons, the number of data moves, and the elapsed time. You should prepare a separate table for each required number. For each table, each row should include the type of the input (e.g., R1K - array with 1000 random integers, A1K - array with 1000 ascending integers, D1K - array with 1000 descending integers, M1K - array with 500 ascending and 500 descending integers, etc.) and the values obtained by selection sort, merge sort and quick sort in four separate columns. Then, with the help of a spreadsheet program (Microsoft Excel, Matlab or other tools), present your experimental results graphically. Interpret and compare your empirical results with the theoretical ones for each sorting algorithm. Explain any differences between the empirical and theoretical results, if any.
1 file (309.7KB)
