Programming Assignment The goal of this programming assignment is two-fold. The

Question

Programming Assignment The goal of this programming assignment is two-fold. The first goal is to observe empirically the complexities of different algorithms solving the same problem. The second goal is to discover how accurate the theoretical estimates of complexity are when compared to real execution times. You can implement the code in C, C++, Java. For other programming languages, please consult with the instructor. In this assignment, you will implement three sorting algorithms: ALGI, ALG2, and ALG3. For the algorithms discusses in class, the implementation should follow exacty the algorithms (pseudocode) learned in class, which is the same as in the textbook. The final submission will consist of . The source code, submitted on Blackboard . A report consisting of 1. A graph showing a comparison of the running times of the three algorithms for various input sizes (see below for details) 2. Three tables, one for each algorithm, showing a comparison of the actual and theoretical running times. For each algorithm, compute an approximation of the hidden constant in the O-notation More details: Run experiments varying n (where n is the number of elements) from ns to n, with increment . For each n value, run each algorithm m times on different input arrays and take the average of the running times. Run the three algorithms on the same input arrays. · . To generate numbers, use a random number generator. Then for each array instance run the algorithms. You can use rand) which generates a random number between 0 and RAND MAX 32767. Include #include Determine the unit of time for your measurements, such as milliseconds (ms) or microseconds (Hs). For us, if you use unix you can use for example "gettimeofday" which gives the time in sec and microseconds. Use "man gettimeofday" to see the manual description. You need to plot the running time of the algorithms as a function of the number of elements n Approximate the value of the hidden constant in the O-notation by dividing the running times with the theoretical values and then taking the maximum value over all input sizes. . . . . Make sure you address the issue with the array indexes! In our classnotes/textbook, we assume arrays start from the index 1, e.g. A[.n], while in many programming languages arrays start from the index 0, e.g. A[0.n-1 .File format accepted: Microsoft Word (doc files), PDF files, ZIP files (continued next page) COT 4400: Design and Analysis of Algorithms For this programming assignment, use the following specifications: ALG I = INSERTION-SORT ALG2 HEAPSORT ALG3 = QUICKSORT ns= 1000 nr = 20000 =1000 m= 10

Explanation / Answer

main.cpp

#include <iostream>
#include <vector>
#include "Random2DMatrix.h"

using namespace std;

void ALG1(Random2DMatrix arr); // INSERTION-SORT
void ALG2(Random2DMatrix arr); // HEAPSORT
void ALG3(Random2DMatrix arr); // QUICKSORT

void PrintVector(vector<int> arr);

namespace constants {
const int ns = 1000, nf = 20000, d = 1000, m = 10;
}

int main() {

Random2DMatrix matrix = Random2DMatrix(constants::m, constants::nf);

ALG1(matrix);
ALG2(matrix);
ALG3(matrix);

return 0;
}

// INSERTION-SORT
void ALG1(Random2DMatrix arr) {
arr.PrintRuntimeToFile(constants::ns, constants::nf, constants::d, "insertion-sort.txt", "Insertion Sort");
}

// HEAPSORT
void ALG2(Random2DMatrix arr) {
arr.PrintRuntimeToFile(constants::ns, constants::nf, constants::d, "heapsort.txt", "Heapsort");
}

// QUICKSORT
void ALG3(Random2DMatrix arr) {
arr.PrintRuntimeToFile(constants::ns, constants::nf, constants::d, "quicksort.txt", "Quicksort");
}

void PrintVector(vector<int> arr) {
for(int & elements : arr) {
cout << elements << " ";
}
cout << endl;
}

================================================================================

//
//filename Random2DMatrix.cpp
//

#include "Random2DMatrix.h"

Random2DMatrix::Random2DMatrix(int rows, int columns) {
matrix.resize(rows, vector<int> (columns));

for(int run = 0; run < matrix.size(); run++) {
for(int n = 0; n < matrix[run].size(); n++) {
matrix[run][n] = rand();
}
}
}

Random2DMatrix::Random2DMatrix(const Random2DMatrix& other) {
matrix.resize(other.matrix.size(), vector<int> (other.matrix[0].size()));

for(int run = 0; run < matrix.size(); run++) {
for(int n = 0; n < matrix[run].size(); n++) {
matrix[run][n] = other.matrix[run][n];
}
}
}

Random2DMatrix::~Random2DMatrix() {
for(int i = 0; i < matrix.size(); i++) {
matrix[i].clear();
}
matrix.clear();
}

void Random2DMatrix::InsertionSort(vector<int> &arr) { // INSERTION-SORT
int key, i;

for(int j = 1; j <= arr.size() - 1; j++) {
key = arr[j];
i = j - 1;
while(i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i];
i = i - 1;
}
arr[ i + 1] = key;
}
}

void Random2DMatrix::Heapsort(vector<int> &arr) {// HEAPSORT
int heapSize = arr.size();
BuildMaxHeap(arr, heapSize);
for(int i = heapSize - 1; i >= 1; i--) {
SwapElementsInVector(arr, 0, i);
heapSize = heapSize - 1;
MaxHeapify(arr, 0, heapSize);
}
}

void Random2DMatrix::Quicksort(vector<int> &arr, int beg, int end) { // QUICKSORT
if(beg < end) {
int q = Partition(arr, beg, end);
Quicksort(arr, beg, q - 1);
Quicksort(arr, q + 1, end);
}
}

void Random2DMatrix::PrintRuntimeToFile(int ns, int nf, int d, string fileName, string sortName) {
ofstream opFile;
opFile.open (fileName);
opFile << "Runtimes for " + sortName << endl << endl;

if(sortName == "Insertion Sort" || sortName == "Heapsort" || sortName == "Quicksort") {
// Specifies the number of elements to run the algorithm with.
for (int n = ns; n <= nf; n += d) {
vector<long> runtimeArray;

cout << "Please wait, running " + sortName << " with " + to_string(n) + " elements..." << endl;

// Specifies which run the program is on.
for (int run = 0; run < matrix.size(); run++) {
// Creates temporary vector to run algorithms with.
vector<int> arr(matrix[run].begin(), matrix[run].begin() + n);
timeval startTime, endTime;

if (sortName == "Insertion Sort") {
gettimeofday(&startTime, 0);
InsertionSort(arr);

} else if (sortName == "Heapsort") {
gettimeofday(&startTime, 0);
Heapsort(arr);

} else if (sortName == "Quicksort") {
gettimeofday(&startTime, 0);
Quicksort(arr, 0, arr.size() - 1);
}

gettimeofday(&endTime, 0);

long microseconds =
(endTime.tv_sec * 1000000 + endTime.tv_usec) - (startTime.tv_sec * 1000000 + startTime.tv_usec);
runtimeArray.push_back(microseconds);

arr.clear();
}

double average = 0;
for (int i = 0; i < runtimeArray.size(); i++) {
average += runtimeArray[i];
}
average = average / runtimeArray.size();

//TODO: SELECT FILE OR STD OUTPUT
opFile << "Average runtime for " + to_string(n) + " elements: " + to_string(average) << endl;
//cout << "Average runtime for " + to_string(n) + " elements: " + to_string(average) << endl;

runtimeArray.clear();
}
}
else {
opFile << "Sort Name does not exist" << endl;
}

opFile.close();
}

void Random2DMatrix::MaxHeapify(vector<int> &arr, int root, int heapSize) {
int leftChild = LeftChild(root);
int rightChild = RightChild(root);
int largest;

if(leftChild <= heapSize - 1 && arr[leftChild] > arr[root]) {
largest = leftChild;
}
else {
largest = root;
}

if(rightChild <= heapSize - 1 && arr[rightChild] > arr[largest]) {
largest = rightChild;
}

if(largest != root) {
SwapElementsInVector(arr, root, largest);
MaxHeapify(arr, largest, heapSize);
}
}

void Random2DMatrix::BuildMaxHeap(vector<int> &arr, int heapSize) {
for(int i = (heapSize - 1) / 2; i >= 0; i--) {
MaxHeapify(arr, i, heapSize);
}
}

int Random2DMatrix::LeftChild(int index) {
return 2 * index;
}

int Random2DMatrix::RightChild(int index) {
return (2 * index) + 1;
}

int Random2DMatrix::Partition(vector<int> &arr, int beg, int end) {
int q = arr[end];
int i = beg - 1;
for(int j = beg; j < end; j++) {
if(arr[j] <= q) {
i = i + 1;
SwapElementsInVector(arr, i, j);
}
}
SwapElementsInVector(arr, i + 1, end);
return i + 1;
}

void Random2DMatrix::SwapElementsInVector(vector<int> &arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}

==========================================================

//
//filename Random2DMatrix.h
//

#ifndef SCALES_COT4400_ASSIGN_RANDOM2DMATRIX_H
#define SCALES_COT4400_ASSIGN_RANDOM2DMATRIX_H

#include <vector>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <sys/time.h>
#include <iostream>

using namespace std;

class Random2DMatrix {
public:
Random2DMatrix(int rows, int columns);
Random2DMatrix(const Random2DMatrix& other);
~Random2DMatrix();
void InsertionSort(vector<int> &arr);

void Heapsort(vector<int> &arr);

void Quicksort(vector<int> &arr, int beg, int end);

void PrintRuntimeToFile(int ns, int nf, int d, string fileName, string sortName);

private:
vector<vector<int>> matrix;

void MaxHeapify(vector<int> &arr, int root, int heapSize);

void BuildMaxHeap(vector<int> &arr, int heapSize);

int LeftChild(int index);

int RightChild(int index);

int Partition(vector<int> &arr, int beg, int end);

void SwapElementsInVector(vector<int> &arr, int index1, int index2);
};

#endif //SCALES_COT4400_ASSIGN_RANDOM2DMATRIX_H

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.