This is a computer program that needs to be done in C#. I need this done in 6 days. - 76211

Request Posted by
3141_student

3141_student

Rating : No Rating
Earned: $0
Request Detail
Price: $20
  • From: Computer Science, C Programming
  • Due on: Mon 02 Feb, 2015 (04:15pm)
  • Asked on: Tue 27 Jan, 2015
  • Due date has passed, but you can still Post Solution.
Description

CS47

1 Overview

This assignment

2 Background

The mathematical functions we use comparing algorithms are asymptotic functions that are depend upon problem size. Consider again the definition of the "Big-Oh" function:

  • \(f(n) = O(g(n))\) : \(c*g(n)\) is an upper bound on \(f(n)\). Thus, there is some constant \(c\) such that \(f(n) \leq c*g(n)\) for \(n \geq n_{0}\)
  • There is a practical implication with this definition that says the performance of the algorithm in question start to show the expected behavior until such time that the value of \(n\) exceeds \(n_{0}\).

3 Assignment

Test this situation by doing the following:

  • Refer back to the textbook for CS372 to review the algorithms for performing an insertion sort and quicksort (Chapter 13 of the CS372 textbook). You may also use the information on these algorithms that can be found on the Internet.
  • Implement both algorithms in your language of choice to sort an array of integers that has length defined in the parameters of the implementation. For C++, the functions should have the following prototypes:

void insertionSort(int arr[], int size); void quicksort(int arr[], int size);

  • Write a program that will accept a integer array size as input, and for at least 20 times will randomly fill an integer array of the requested size and computes the amount time it takes to sort the array using the functions from the previous step.
  • Run your program for array sizes of 5, 10, 50, 100, 500, 1000, 5000, and 10000 integers. You program should, for each sort algorithm, generate two data files: (1) a comma-separated values file containing the raw run times for each sort, and (2) a comma separated values file containing the average run time for each array.
  • Using your favorite graphing tool (such as a spreadsheet), generate the following four graphs:
    • For insertion sort,
      • a scatterplot that plots array size on the x-axis vs. raw run time on the y-axis. Also, for each array size, plot a mark on the plot that shows the value of \(f(x)=x^2\) for that array size.
      • a line graph that plots a graph of \(f(x)=x^2\) and, for each array size, places a mark on the graph for the average run time for each array size.
    • For quicksort,
      • a scatterplot that plots array size on the x-axis vs. raw run time on the y-axis. Also, for each array size, plot a mark on the plot that shows the value of \(f(x)=x*\log_{2}(x)\) for that array size.
      • a line graph that plots a graph of \(f(x)=x*\log_{2}(x)\) and, for each array size, places a mark on the graph for the average run time for each array size.
  • Write a summary and interpretation of your results

4 Hints and suggestions

4.1 Timing functions

You're going to need to time how long it takes to sort the array. Timing of functions has some issues so we suggest you use the following class for timing purposes:

#include <iostream> #include <chrono> class Timer { public: Timer() : beg_(clock_::now()) {} void reset() { beg_ = clock_::now(); } double elapsed() const { return std::chrono::duration_cast<second_> (clock_::now() - beg_).count(); } private: typedef std::chrono::high_resolution_clock clock_; typedef std::chrono::duration<double, std::ratio<1> > second_; std::chrono::time_point<clock_> beg_; };

You use the this class in the following manner:

int main() { // timing is started in the Timer constructor Timer tmr; // Do whatever you need to do doSomething(); double t = tmr.elapsed(); std::cout << t << std::endl; // You reuse the timer by calling the reset method tmr.reset(); doSomeMoreWork(); double t = tmr.elapsed(); std::cout << t << std::endl; return 0; }

4.2 A math note

Note that you need to work base-2 logarithms when working with quicksort. Here's where we use some the math we're taught in calculus. There is a quick and easy way to covert between logarithms with different bases: \(log_{a}(b) = log_{c}(b) / log_{c}(a)\)

Use this identity to convert from base-10 to base-2 logarithms in your graphing tool of choice (if it doesn't support base-2 logarithms directly).

1 Solution for This is a computer program that needs to be done in C#. I need this done in 6 days.
Title Price Category solution By purchased  
C++ Sort Program and chart
$20.00 Mathematics, Algebra lightsource 0 time(s)
Please Login or Register to Submit the Solution for the Request