CS2123 Data Structures - Fall 2019 Assignment 1: Function Runtimes Table Due 9/11/19 by 11:59pm Completing the Program (15 points) This program prints a table of runtimes (these are displayed in seconds) for given functions on arrays. The program tests different array sizes to establish a relationship between input size and runtime. It tests each array size multiple times and then takes an average of the times. Here are example calls to the timing functions: int sizes[] = { 1000, 2500, 5000, 7500, 10000}; char str1[] = "Insertion Sort"; char str2[] = "quicksort (uses insertion sort when sorting <30 numbers)"; fRT = timeAlgorithm(str1, 10, 5, sizes, insertionSortInitial ); printRuntimeTable(fRT); freeFunctionRuntimes(fRT); fRT = timeAlgorithm(str2, 10, 5, sizes, quickSortOptInitial ); printRuntimeTable(fRT); freeFunctionRuntimes(fRT); This results in following table: Note your runtimes may vary since the test data is randomly generated. The runtimes are stored in a functionRuntimes struct. You are completing a program to create and fill data in this struct, print the data of this struct, and free this struct. You are given a partial implementation in the fle “cs2123HW1-LastName.c”. Specifically you are tasked to complete the funtctions below the heading “Functions for finding and printing runtime”. No other functions should be changed. Using the Program (5 points) After you have the program completed, you should use it to help determine the asymptotic runtimes of the three mystery functions (i.e., mysteryRuntime1, mysteryRuntime2, mysteryRuntime3). Be sure to also examine the code of the mystery functions to confirm/improve your estimations. Fill in the following table in the provided file: /* TODO: Give your asymptotic estimates for the runtimes of the following 3 functions: mysteryRuntime1: O( ) mysteryRuntime2: O( ) mysteryRuntime3: O( ) */ Deliverables: Your solution should be submitted as “cs2123HW1-LastName.c” where “LastName” is replaced with your last name. Be sure to fill in the table of runtimes described above: Upload this file to Blackboard under Assignment 1. Do not zip your file. To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

const char DATA_FILE_NAME[] = "TestData.txt";

typedef struct functionRuntimes
{
    char *szName;             //name of the function being tested
    double **arrRuntimes;         //run times
    double *arrAvg;            //average runtime
    int iNumRepeats;       //number of times to repeat each test size
    int iNumTestCaseSizes;   //number of test case sizes
    int *arrTestSizes;     //array containing the test case sizes
} functionRuntimes;

//Functions used to test the runtimes
functionRuntimes timeAlgorithm( char*, int, int, int[], void (*f)(FILE *) );
FILE *generateTestInput( int, int, int );
void computeAvg( functionRuntimes fRT );
void printRuntimeTable( functionRuntimes fRT );
void freeFunctionRuntimes( functionRuntimes fRT );

//Functions whose runtime will be tested (and helper functions)
void insertionSortInitial( FILE* input );
void insertionSort( int* points, int low, int high );
void quickSortOptInitial( FILE* input );
void quickSortOpt( int* points, int low, int high );
int partition( int* points, int low, int high );

void mysteryRuntime1( FILE* input );
void mysteryRuntime2( FILE* input );
void mysteryRuntime3( FILE* input );

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 * (if you make alterations plan to revert them before submission)
 */
int main( int argc, char *argv[] )
{
    functionRuntimes fRT;

    int sizes1[] = { 2000, 4000, 8000, 16000, 32000, 64000, 128000};

    srand(time(0));

    fRT = timeAlgorithm("Insertion Sort", 10, 3, sizes1, insertionSortInitial );
    printRuntimeTable(fRT);
    freeFunctionRuntimes(fRT);

    fRT = timeAlgorithm("quicksort (uses insertion sort when sorting <30 numbers)", 10, 6, sizes1, quickSortOptInitial );
    printRuntimeTable(fRT);
    freeFunctionRuntimes(fRT);

    fRT = timeAlgorithm("Mystery 1", 5, 6, sizes1, mysteryRuntime1 );
    printRuntimeTable(fRT);
    freeFunctionRuntimes(fRT);

    fRT = timeAlgorithm("Mystery 2", 5, 4, sizes1, mysteryRuntime2 );
    printRuntimeTable(fRT);
    freeFunctionRuntimes(fRT);

    fRT = timeAlgorithm("Mystery 3", 5, 4, sizes1, mysteryRuntime3 );
    printRuntimeTable(fRT);
    freeFunctionRuntimes(fRT);

    return 0;
}

/*************************************** Functions to have their runtimes tested *********************************************/

/* provided code - DO NOT CHANGE
 */
void mysteryRuntime1( FILE* input )
{
    int temp;
    int size;
    int i=0;
    int *array;

    if( fscanf( input, "%d", &size ) != 1 )
    {
        exit(-1);
    }
    array = (int *) malloc( size*sizeof(int) );
    if( array == NULL )
    {
        exit(-1);
    }

    while( fscanf( input, "%d", &temp ) == 1 && i<size)
    {
        array[i] = temp;
        i++;
    }

    while( size>1 )
    {
        size = size/2;
        array[size/2] = array[size];
    }

    free(array);
}

/* provided code - DO NOT CHANGE
 */
void mysteryRuntime2( FILE* input )
{
    int temp;
    int size;
    int n;
    int i=0;
    int *array;

    if( fscanf( input, "%d", &size ) != 1 )
    {
        exit(-1);
    }
    array = (int *) malloc( size*sizeof(int) );
    if( array == NULL )
    {
        exit(-1);
    }

    while( fscanf( input, "%d", &temp ) == 1 && i<size)
    {
        array[i] = temp;
        i++;
    }

    for( i=0; i<size; i++ )
    {
        for( n=size-1; n>1; n/=1.01 )
        {
            array[n-1] = array[n];
        }
    }

    free(array);
}

/* provided code - DO NOT CHANGE
 */
void mysteryRuntime3( FILE* input )
{
    int temp;
    int size;
    int i=0, j=0;
    int *array;

    if( fscanf( input, "%d", &size ) != 1 )
    {
        exit(-1);
    }
    array = (int *) malloc( size*sizeof(int) );
    if( array == NULL )
    {
        exit(-1);
    }

    while( fscanf( input, "%d", &temp ) == 1 && i<size)
    {
        array[i] = temp;
        i++;
    }

    i=0;
    while( j<size )
    {
        array[j] = array[i];

        i++;
        if( i>=size )
        {
            j++;
            i=0;
        }
    }

    free(array);
}


/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
void insertionSortInitial( FILE* input )
{
    int i;
    int size;
    int *array;

    fscanf( input, "%d", &size );
    array = (int *) malloc( size*sizeof(int) );

    for( i=0; i<size; i++)
    {
        fscanf( input, "%d", &array[i] );
    }

    insertionSort( array, 0, size-1 );

    //Error check to verify the array is sorted
    /*for( i=1; i<size; i++)
    {
        if(array[i-1]>array[i])
        {
            printf("Not sorted!");
            exit(-1);
        }
    }*/

    free(array);
}

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
void insertionSort( int* points, int low, int high )
{
    int i, j;
    double temp;

    for( i = low+1; i <= high; i++)
    {
        for( j = i; j > low && points[j]<points[j-1]; j--)
        {
            temp = points[j];
            points[j] = points[j-1];
            points[j-1] = temp;
        }
    }
}

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
void quickSortOptInitial( FILE* input )
{
    int i;
    int size;
    int *array;

    fscanf( input, "%d", &size );
    array = (int *) malloc( size*sizeof(int) );

    for( i=0; i<size; i++)
    {
        fscanf( input, "%d", &array[i] );
    }

    quickSortOpt( array, 0, size-1 );

    //Error check to verify the array is sorted
    /*for( i=1; i<size; i++)
    {
        if(array[i-1]>array[i]){
            printf("Not sorted!");
            exit(-1);
        }
    }*/

    free(array);
}

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
void quickSortOpt( int* points, int low, int high )
{
    if( high < low+30 )
    {
        insertionSort( points, low, high );
    }
    else
    {
        int pivot = partition( points, low, high );

        quickSortOpt( points, low, pivot-1 );
        quickSortOpt( points, pivot+1, high );
    }
}

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
int partition( int* points, int low, int high )
{
    int pivot = rand() % (high - low + 1) + low;
    int pivotValue = points[pivot];
    int i = low+1;
    int j = high;
    int temp;

    points[pivot] = points[low];
    points[low] = pivotValue;

    while( i<j )
    {
        while( i<=high && points[i] <= pivotValue )
        {
            i++;
        }
        while( j>=low && points[j] > pivotValue )
        {
            j--;
        }
        if(i<j)  //swap out of order elements
        {
            temp = points[i];
            points[i] = points[j];
            points[j] = temp;
        }
    }
    if( i<=high && points[i] <= pivotValue )
    {
        i++;
    }

    points[low] = points[i-1];
    points[i-1] = pivotValue;

    return i-1;
}

/*************************************** Functions for finding and printing runtime *********************************************/

/*
TODO: Give your asymptotic estimates for the runtimes of the following 3 functions:

mysteryRuntime1:  O(   )
mysteryRuntime2:  O(   )
mysteryRuntime3:  O(   )
*/


/* TO BE COMPLETED BY YOU
 * Fill in the missing parts of the code (see TODOs below)
 */
functionRuntimes timeAlgorithm( char *szName, int iNumRepeats, int iNumTestCaseSizes, int arrTestSizes[], void (*f)(FILE *) )
{
    /* Call and calculate the runtime of the provided function f */
    clock_t start, end;
    int i, j;
    FILE *testData;

    //create functionRuntimes variable to return
    functionRuntimes fRT;

    //TODO: copy passed data into the fRT variable.  Specifically do the following:
    /* fill szName in fRT with the variable szName */
    /* fill iNumRepeats in fRT with the variable iNumRepeats */
    /* fill iNumTestCaseSizes in fRT with the variable iNumTestCaseSizes */
    /* malloc space for arrTestSizes in fRT to hold iNumTestCaseSizes number of ints */
    /* fill arrTestSizes in fRT with the variable arrTestSizes (hint: use a loop) */



    //TODO: malloc an array with iNumTestCaseSizes variables of type double* (on next line)
    fRT.arrRuntimes = NULL; /* replace NULL with your code */
    for( i=0; i<iNumTestCaseSizes; i++ )
    {
        //TODO: malloc an array with iNumRepeats variables of type double (on next line)
        //fRT.arrRuntimes[i] = NULL; /* replace NULL with your code and uncomment the line */

        for( j=0; j<iNumRepeats; j++ )
        {
            //Generate test data for the function f
            testData = generateTestInput( 0, arrTestSizes[i], arrTestSizes[i] );

            //Run f on the generated test data
            start = clock();
            f( testData );
            end = clock();
            fclose(testData);

            //Enter the elapsed number of seconds into the arrRuntimes array for fRT
            //TODO: uncomment the next line line after you've malloc-ed memory for fRT.arrRuntimes
            //fRT.arrRuntimes[i][j] = (double)(end - start) / CLOCKS_PER_SEC;
        }
    }

    //TODO: Calculate the average runtimes (malloc space for fRT.arrAvg and call computeAvg here)

    return fRT;
}

/*
 * Provided code - DO NOT CHANGE THIS METHOD
 */
FILE *generateTestInput( int min, int max, int size )
{
    int i;
    FILE *data = fopen( DATA_FILE_NAME, "w" );

    if( data==NULL )
    {
        printf("Failed to create file %s\n", DATA_FILE_NAME);
        exit(-1);
    }

    //add size to start of file
    fprintf( data, "%d ", size );
    //Fill the file with random data
    for( i=0; i<size; i++ )
    {
        fprintf( data, "%d ", rand()%(max-min+1)+min );
    }
    fclose(data);

    data = fopen( DATA_FILE_NAME, "r" );
    if( data==NULL )
    {
        printf("Failed to create file %s\n", DATA_FILE_NAME);
        exit(-1);
    }
    return data;
}

/* TODO: TO BE COMPLETED BY YOU
 * Calculate and insert the average runtime for each set of test data into fRT
 */
void computeAvg( functionRuntimes fRT )
{

}

/* TODO: TO BE COMPLETED BY YOU
 * Print the information in fRT as a 2d table.  Display 3 digits after the decimal point.  You can assume all of the runtimes are <= 99.999 seconds.
 */
void printRuntimeTable( functionRuntimes fRT )
{

}

/* TODO: TO BE COMPLETED BY YOU
 * Free all of the dynamically allocated memory in fRT
 */
void freeFunctionRuntimes( functionRuntimes fRT )
{

}

Question 2.

Design a 16-1 MUX using any number of lower MUXs, such as 8-1 or 4-1 only. No other gates are allowed.

. Write   a   function   that   takes,   as   arguments,   two   objects,   value1   and   value2.       If   value1   and   value2   are   either   integers   or   strings   containing   only   digits,   cast   value1   and   value2   to   integers   and   compute   their   average.       If   their   average   is   greater   than   50,   return   the   string   “Above   50”   and   if   the   average   is   less   than   50,   return   the   string   “Below   50”.       If   the   average   is   equal   to   50,   return   the   string   “Equal   to   50”,   and   if   value1   or   value2   are   not   integers   or   strings   containing   only   digits,   return   the   string   “Invalid   Input”.       Name   this   function   compareToFifty(value1,   value2).       value1   value2   compareToFifty(value1,   value2)   25   25   “Below   50”   100   “300”   “Above   50”   “45”   “100”   “Above   50”   25   75   “Equal   to   50”   24.5   67   “Invalid   Input”   “hello”   “world”   “Invalid   Input”  

1.Discuss the interdependence that exists between DSDLC stages.

2.How does normalization eradicate update anomalies from a relation?

3.The scope of database security extends beyond just DBMS controls. Discuss the role of the database administrator in database security and recovery.

Reverse the following selection sort to sort the items from right to left by computing the max instead of min in java. (just write the algorithm)

public class Selection{

public static void sort(Comparable[] a) {

// Sort a[] into increasing order.

int N = a.length;

// array length

for (int i = 0; i < N; i++) {

// Exchange a[i] with smallest entry in a[i+1...N).

int min = i;

// index of minimal entr.

for (int j = i+1; j < N; j++)

if (less(a[j], a[min])) min = j;

exch(a, i, min);

}

}

}

identify a company that you consider as Agile and another company that is not. Explain the rationale for your selections and compare and contrast the two companies.

•Use commented pseudo-code to describe a process for each of the following:

1)Assigning a shopper to one of several checkout lines based on:

•the number of shoppers already in each line, and

•the number of items in the shopper’s cart, and

•the type of items (e.g., “Food”, “Clothing”, “Housewares”, etc.)

2)Assigning a new student into the correct desk in a room of students seated in alphabetical order

•Design classes (attributes and methods) for the following data structures:

4)Stack

5)Queue

Write in Python and as 2 seperate programs

Write a program that allows the user to enter the total rainfall for each of 12 months into a LIST. The program should calculate and display the total rainfall for the year, the average monthly rainfall, and the months with the highest and lowest rainfall amounts. Data: January 7.9 inches February 10.1 inches March 3.4 inches April 6.7 inches May 8.9 inches June 9.4 inches July 5.9 inches August 4.1 inches September 3.7 inches October 5.1 inches November 7.2 inches December 8.3 inches

Write comments through both programs (file creation program, and display program) telling what the program is doing

Asymptotic Notation. (a) [10 pts.] Prove that n3 −91n2 −7n−14 = Ω(n3). Your answer must clearly specify the constants c and n0. (b) [10 pts.] Let g(n) = 27n2 +18n and let f(n) = 0.5n2−100. Find positive constants n0, c1 and c2 such that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0. Be sure to explain how you arrived at the constants.

You are required to write an interactive program that prompts the user for seven (7) real numbers and performs the following tasks:

1. Reads and stores the numbers into one-dimensional array called A.
2. Calculates the sum of the numbers.
3. Find the average of the numbers.
4. Finds the smallest value of the numbers.
5. Prints all the results with proper headings.

Program requirements:

-     The program must contain at least five functions using necessary parameters. These functions should read the data, perform the above tasks, and print the results.

-     The program must be fully documented.

-    You must submit a properly labeled output. .

-     Test your program for different values using real numbers.

Please submit with through comments & spacings/indentations from the source code.

Java Programming. I'm writing this in an IDE called Eclipse.

If you could also use comments to help me understand the code / your way of thinking, I'd highly appreciate your efforts.

This needs to use a for each loop, it will generates and return= an array of random 2-digit integers and it also needs to be printed out all on one line, separated by spaces.

Program71:

Write a program with a custom method that generates and returns an array of random 2-digit integers. The main method should prompt the user to specify the size of the array and call the custom method with this input as an argument. Use a foreach loop in main to display the integers all on one line separated by spaces.

Sample Output (user input in blue)
How many random 2-digit integers are desired?
12
Here are your integers:
43 76 22 38 64 30 87 14 55 63 35 42

Write a c++ program to load two column of numbers, do arithmetic operations to the data points by following the steps below carefully. Also we need to capture the running time in microseconds for each of these and also the time taken for basic operation.

Steps to complete.

0. Download the data file named Datafile1.data from the file area of the assignment.

1. Load two columns of data points, each column into a storage area, preferably a vector.

2. Initialize/start the clock to capture start of addition clock.

3. Add each position of the data and store it in another storage area.

4. Capture the clock for capturing time end for additions.

5. Start the clock for capturing multiplication

6. Multiply each position of the data and store it to another storage area.

7. Capture the clock for end of multiplications.

8. Print both elapsed time for addition and multiplication in microseconds.

9. Print basic operation time for addition and multiplication in microseconds.

10. Write the results of addition and multiplication to a file named Output.data

Datafile1.data

9.144548371       0.62072663
7.766500067       1.107554175
6.428523445       0.409904615
4.864271967       1.142139412
7.064106885       1.138740729
2.262955152       1.198965847
9.800966285       0.624420569
8.466914743       0.172152387
7.089199692       0.650149663
6.042680886       0.526675179
1.320701358       0.893658642
3.576178301       0.966546628
4.939756105       0.53583099
3.386905283       0.24428521
5.231554752       0.660683916
3.736280728       0.378121052
7.527971435       0.917047269
2.533630929       1.029850114
9.188222671       0.237647807
1.800088589       0.763132902
9.702171329       1.187835787
4.713240732       0.602808579
0.350114291       0.126105779
1.375572924       0.534626533
3.699384174       0.670885379
7.183110563       1.327536861
7.434890545       1.174302317
9.781202522       1.271484048
7.153021655       0.99647769
0.516259776       0.868291689
9.637573135       0.596947716
7.056519481       0.350322259
0.160533268       0.565683307
9.008315924       0.919842547
9.173718748       0.593500412
6.921833783       0.015908284
6.736418485       0.719292318
3.353631576       1.363438995
1.604967361       0.679785674
5.672035588       0.171718917
7.794867595       0.550310846
5.889160186       0.07760882
1.690701207       0.829202546
4.155650455       0.94739278
6.018503489       0.989127529
1.46468541       1.171169011
2.670443291       0.505688273
8.22853784       0.514127061
9.631840542       0.238298413
1.669453846       1.27499486
3.311515543       0.789657118
5.969493897       0.053853209
2.478574394       1.206080543
7.696244495       0.099599082
3.769765061       1.193693451
1.992200015       0.895544331
4.030882115       0.398607671
2.939993773       0.360149058
8.499182913       0.645159168
1.33467738       0.264472403
3.475730127       0.826362657
7.471431245       1.220818624
6.140279634       0.462733534
3.740656241       1.363952935
5.174154405       1.157155608
9.466008548       0.261690906
9.225005657       0.158991829
7.061522707       0.200296564
2.527050453       0.668705617
3.989058951       0.659984653
5.969333965       0.297768248
6.813173789       1.23032852
7.47467435       0.289477322
0.27004337       0.808100642
0.226724804       0.947863653
8.491775489       0.703714179
9.67169797       0.439579426
7.171630039       0.893035833
8.435125276       0.053497387
1.740878827       1.135864744
1.624571489       0.537973501
9.398492585       1.285333242
9.855769556       1.156707773
5.536670988       0.524629176

using this code under, I want when the user input only letter q an error message appears that there is no second smallest, how I can do that?

#include <iostream>

#include <sstream>

#include <vector>

#include <algorithm>

using namespace std;

int secondSmallestNumber(vector<int> &I);

int main() {

   cout << "Enter the numbers in random order: (close by entering q)" << endl;

   vector<int> I;

   int input;

   stringstream ss;

   string str;

   bool flag = false;

   while (!flag) {

       getline(cin, str);

       ss.clear();

       ss << str;

       while (ss >> input || !ss.eof()) {

           if (ss.fail()) {

               flag = true;

               break;

           }

           I.push_back(input);

       }

   }

   int result;

   try {

       result = secondSmallestNumber(I);

       cout << "The second smallest number is: " << result << endl;

   }

   catch (const runtime_error& e ) {

       cout << "error: no second smallest" << endl;

   }

   return 0;

}

int secondSmallestNumber(vector<int> &I){

   std::sort(I.begin(), I.end());

   int number = I.at(0);

   for (int i = 0; i < I.size() - 1; i++) {

       if (I.at(i + 1) > number) {

           return I.at(i + 1);

       }

   }

   throw runtime_error("error");

}

1. Keeping in mind the various definitions of operating system, consider whether the operating system should include applications such as web browsers and mail programs. Argue both that it should and that it should not, and support your answers

2. How does the distinction between kernel mode and user mode function as a rudimentary form of protection (security) system?

You need to complete the methods getSmallerValue, getLargerValue, compareTo, and equals.

Code:

public class Domino implements Comparable<Domino> {

/**

* The smallest possible value for a side of a domino.

*/

public static final int MIN_VALUE = 0;

/**

* The largest possible value for a side of a domino.

*/

public static final int MAX_VALUE = 6;

/**

* The two values on the domino.

*/

private int val1;

private int val2;

public Domino() {

this(0, 0);

}

public Domino(int value1, int value2) {

if (!isValueOK(value1) || !isValueOK(value2)) {

throw new IllegalArgumentException();

}

this.val1 = value1;

this.val2 = value2;

}

public Domino(Domino other) {

this(other.val1, other.val2);

}

private static boolean isValueOK(int value) {

return value >= MIN_VALUE && value <= MAX_VALUE;

}

@Override

public int hashCode() {

return this.getSmallerValue() + 11 * this.getLargerValue();

}

@Override

public String toString() {

return "[" + this.getSmallerValue() + " : " + this.getLargerValue() + "]";

}

/*

* You need to implement the four methods below. Both compareTo and equals

* should make use of getSmallerValue and getLargerValue.

*/

public int getSmallerValue() {

}

public int getLargerValue() {

}

@Override

public int compareTo(Domino other) {

}

@Override

public boolean equals(Object obj) {

}

}