Question

MINIMUM MAIN.CPP CODE

/********************************
* Week 4 lesson:               *
*   finding the smallest number *
*********************************/

#include <iostream>

using namespace std;

/*
* Returns the smallest element in the range [0, n-1] of array a
*/
int minimum(int a[], int n)
{
   int min = a[0];

   for (int i = 1; i < n; i++)
       if (min > a[i]) min = a[i];

   return min;
}

int main()
{
   int a[10];

   for (int i = 0; i < 10; i++)
   {
       a[i] = rand()%100;
       cout << a[i] << " ";
   }

   cout << endl << "Min = " << minimum(a, 10) << endl;

   return 0;

}

FACTORIAL MAIN.CPP CODE

/************************************************
*   implementing a recursive factorial function *
*************************************************/

#include <iostream>

using namespace std;

/*
* Returns the factorial of n
*/
long factorial(int n)
{
   if (n == 1)
       return 1;
   else
       return n * factorial(n - 1);
}

int main()
{
   int n;

   cout << "Enter a number: ";
   cin >> n;

   if (n > 0)
       cout << n << "!= " << factorial(n) << endl;
   else
       cout << "Input Error!" << endl;   return 0;
}

SORTING ALGORITHMS ARRAYLIST CODE

/********************************************
* Week 4 lesson:                           *
*   ArrayList class with sorting algorithms *
*********************************************/

#include <iostream>
#include "ArrayList.h"

using namespace std;

/*
* Default constructor. Sets length to 0, initializing the list as an empty
* list. Default size of array is 20.
*/
ArrayList::ArrayList()
{
   SIZE = 20;
   list = new int[SIZE];
   length = 0;
}

/*
* Destructor. Deallocates the dynamic array list.
*/
ArrayList::~ArrayList()
{
   delete [] list;
   list = NULL;
}

/*
* Determines whether the list is empty.
*
* Returns true if the list is empty, false otherwise.
*/
bool ArrayList::isEmpty()
{
   return length == 0;
}

/*
* Prints the list elements.
*/
void ArrayList::display()
{
   for (int i=0; i < length; i++)
       cout << list[i] << " ";
   cout << endl;
}

/*
* Adds the element x to the end of the list. List length is increased by 1.
*
* x: element to be added to the list
*/
void ArrayList::add(int x)
{
   if (length == SIZE)
   {
       cout << "Insertion Error: list is full" << endl;
   }
   else
   {
       list[length] = x;
       length++;
   }
}

/*
* Removes the element at the given location from the list. List length is
* decreased by 1.
*
* pos: location of the item to be removed
*/
void ArrayList::removeAt(int pos)
{
   if (pos < 0 || pos >= length)
   {
       cout << "Removal Error: invalid position" << endl;
   }
   else
   {
       for ( int i = pos; i < length - 1; i++ )
           list[i] = list[i+1];
       length--;
   }
}

/*
* Bubble-sorts this ArrayList
*/
void ArrayList::bubbleSort()
{
   for (int i = 0; i < length - 1; i++)
       for (int j = 0; j < length - i - 1; j++)
           if (list[j] > list[j + 1])
           {
               //swap list[j] and list[j+1]
               int temp = list[j];
               list[j] = list[j + 1];
               list[j + 1] = temp;
           }
}

/*
* Quick-sorts this ArrayList.
*/
void ArrayList::quicksort()
{
   quicksort(0, length - 1);
}

/*
* Recursive quicksort algorithm.
*
* begin: initial index of sublist to be quick-sorted.
* end: last index of sublist to be quick-sorted.
*/
void ArrayList::quicksort(int begin, int end)
{
   int temp;
   int pivot = findPivotLocation(begin, end);

   // swap list[pivot] and list[end]
   temp = list[pivot];
   list[pivot] = list[end];
   list[end] = temp;

   pivot = end;

   int i = begin,
       j = end - 1;

   bool iterationCompleted = false;
   while (!iterationCompleted)
   {
       while (list[i] < list[pivot])
           i++;
       while ((j >= 0) && (list[pivot] < list[j]))
           j--;

       if (i < j)
       {
           //swap list[i] and list[j]
           temp = list[i];
           list[i] = list[j];
           list[j] = temp;

           i++;
           j--;
       } else
           iterationCompleted = true;
   }

   //swap list[i] and list[pivot]
   temp = list[i];
   list[i] = list[pivot];
   list[pivot] = temp;

   if (begin < i - 1)
       quicksort(begin, i - 1);
   if (i + 1 < end)
       quicksort(i + 1, end);
}

/*
* Computes the pivot location.
*/
int ArrayList::findPivotLocation(int b, int e)
{
   return (b + e) / 2;
}

SORTING ALGORITHMS ARRAYLIST HEADER

/********************************************
* Week 4 lesson:                           *
*   ArrayList class with sorting algorithms *
*********************************************/

/*
* Class implementing an array based list. Bubblesort and quicksort algorithms
* are implemented also.
*/
class ArrayList
{
public:
   ArrayList ();
   ~ArrayList();
   bool isEmpty();
   void display();
   void add(int);
   void removeAt(int);
   void bubbleSort();
   void quicksort();
private:
   void quicksort(int, int);
   int findPivotLocation(int, int);
   int SIZE;       //size of the array that stores the list items
   int *list;       //array to store the list items
   int length;   //amount of elements in the list
};

SORTING ALGORITHMS MAIN.CPP CODE

/********************************************
* Week 4 lesson:                           *
*   ArrayList class with sorting algorithms *
*********************************************/

#include <iostream>
#include "ArrayList.h"
#include <time.h>

using namespace std;

/*
* Program to test the ArrayList class.
*/
int main()
{
   srand((unsigned)time(0));

   //creating a list of integers
   ArrayList numbersCopy1, numbersCopy2;

    //filling the list with random integers
    for (int i = 0; i<10; i++)
   {
       int number = rand()%100;
       numbersCopy1.add(number);
       numbersCopy2.add(number);
   }

    //printing the list
    cout << "Original list of numbers:" << endl <<"\t";
    numbersCopy1.display();

    //testing bubblesort
    cout << endl << "Bubble-sorted list of numbers:" << endl <<"\t";
    numbersCopy1.bubbleSort();
    numbersCopy1.display();

    //testing quicksort
    cout << endl << "Quick-sorted list of numbers:" << endl <<"\t";
   numbersCopy2.quicksort();
    numbersCopy2.display();

   return 0;
}

QUESTIONS

PART 1

Design and implement an algorithm that, when given a collection of integers in an unsorted array, determines the third smallest number (or third minimum). For example, if the array consists of the values 21, 3, 25, 1, 12, and 6 the algorithm should report the value 6, because it is the third smallest number in the array. Do not sort the array.

To implement your algorithm, write a function thirdSmallest that receives an array as a parameter and returns the third-smallest number. To test your function, write a program that populates an array with random numbers and then calls your function.

PART 2

The following problem is a variation of Exercise C-4.27 in the Exercises section of Chapter 4 in Data Structures and Algorithms in C++ (2nd edition) textbook.

Implement a recursive function for computing the n-th Harmonic number:

Hn=∑i=1n1i/

Here you have some examples of harmonic numbers.

H₁ = 1
H₂ = 1 + 1/2 = 1.5
H₃ = 1 + 1/2 + 1/3 = 1.8333
H_4 = 1 + 1/2 + 1/3 + 1/4 = 2.0833

PART 3

In this week's lesson, the algorithms quicksort and bubblesort are described. In Sorting Algorithms (Links to an external site.) you can find the class ArrayList, where these sorting algorithms are implemented. Write a program that times both of them for various list lengths, filling the array lists with random numbers. Use at least 10 different list lengths, and be sure to include both small values and large values for the list lengths (it might be convenient to add a parameterized constructor to the class ArrayList so the size of the list can be set at the moment an ArrayList object is declared).

Create a table to record the times as follows.

List Length	Bubblesort Time (seconds)	Quicksort Time (seconds)

Regarding the efficiency of both sorting methods, what are your conclusions? In addition to the source code and a screenshot of the execution window, please submit a separate document with the table and your conclusions about the experiment.

Note: To time a section of your source code, you can do this.

#include <chrono>

using namespace std;

int main()
{
    start = chrono::steady_clock::now();
     //add code to time here
    end = chrono::steady_clock::now();
    chrono::duration<double> timeElapsed = chrono::duration_cast<chrono::duration<double>>(end-start);
    cout << "Code duration: "  << timeElapsed.count() << " seconds" << endl;      
}

Answer 1

Please let me know if anything is required.

PART1:

Copyable code:

#include <iostream>

using namespace std;

/*
* Returns the 3rd smallest element in the range [0, n-1] of array a
*/
int minimum(int a[], int n)
{
int min1 = a[0],min2=min1,min3=min1;

for (int i = 1; i < n; i++)
if ( a[i]<min1)
{   
min3=min2;
min2=min1; //if first min is greater than the array[i] then we got new min
min1=a[i];//so min1 = a[i] and min3=min2 and min2 = min1
}
else if(a[i]<min2)
{
min3=min2;//if second min is greater than the array[i] then we got new min for second min
min2=a[i];//so min2 = a[i] and min3=min2
}

else if(a[i]<min3) //if a[i] is less than third min then we got new min for min3
{
min3=a[i];
}

  
return min3;//retunring the 3rd minimum element
}

int main()
{
int a[10];

//randomly generating the numbers
for (int i = 0; i < 10; i++)
{
a[i] = rand()%100;
cout << a[i] << " ";
}

cout << endl << "3rd minimum element is: " << minimum(a, 10) << endl;//printing the 3rd minimum element

return 0;

}

Sample output:

Part2:

Copyable code:

#include <iostream>

using namespace std;

//recursive Harmonic function
float Harmonic(float n)
{
if (n <=1) //if number is less than or equal to 1 then returning 1 which is a base condition
return 1;
  
else
return 1/n+(Harmonic(n - 1)); //summing the value and calling the Harmonic function
}

int main()
{
float number;
cout<<"Enter the number: ";
cin>>number; //taking the number input from the user
cout<<"H"<<number<<" = "<<Harmonic(number)<<"\n";//printing the output

return 0;
}

Sample output1: