CST 370  Homework 7 

CST 370 
Homework 7 

How to turn in? 
•    Submit your two source files on the iLearn. 
•    Note that the hw7_1 is a bonus program. Also the due is 03/27/2020, not 03/20/2020.

This is the HackerRank link for hw7_1: https://www.hackerrank.com/cst370-s20-hw7 

1. [Bonus Problem] Write a C++ (or Java) program called hw7_1.cpp (or hw7_1.java) that collects the maximum number of apples in boxes. For the problem, you should assume that there are n boxes (= from the box number 0 to box n-1) on a table and they contain a few apples. Your program should determine the maximum number of apples you can collect from the boxes. One constraint in this problem is that if you collect the apples in a box, you should skip at least one box next to the box. For example, let’s assume that there are four boxes on the table like below:
-    Box 0: 3 apples
-    Box 1: 2 apples
-    Box 2: 3 apples
-    Box 3: 5 apples

To collect the maximum number of apples from the boxes, you have to choose the box 0 and box 3 which contain total 8 apples. Since you choose the box 0, you have to skip the next box (= box 1). And also, if you choose the box 2, you can collect total 6 apples. But by skipping this box (= box 2) as well, you can get the max 8 apples. 

This is another example. This time, assume that there are 6 boxes on the table like below:
-    Box 0: 5 apples
-    Box 1: 1 apples
-    Box 2: 2 apples
-    Box 3: 10 apples
-    Box 4: 6 apples
-    Box 5: 2 apples

For the sequence, you can collect maximum 17 apples by selecting the boxes 0, 3, and 5.

Input format: This is a sample input from a user. 










The first line (= 4 in the example) indicates that there are four boxes on the table. And following four lines are the number of apples in each box. For the homework, you can assume that there can be maximum 15 boxes on the table.

Sample Run 1: Assume that the user typed the following lines

4 
3
2
3
5


This is the correct output.

Max Apples: 8


Sample Run 2: Assume that the user typed the following lines

6
5
1
2
10
6
2

This is the correct output.

Max Apples: 17


Sample Run 3: Assume that the user typed the following lines

2
1
1

This is the correct output.

Max Apples: 1




Hint: Exhaustive search will help to consider all possible selection cases. 



 
For the hw7_2, there is no HackerRank link. Just develop the program and submit the source program on the iLearn.


2. Write a C++ (or Java) program named hw7_2.cpp (or hw7_2.java) that displays the performance of three different sorting algorithms (= insertion sort, mergesort, and quick sort) on the screen. 

Your program should read the input size (= number of input data for sorting) from a user and generate the input data (= positive integer numbers) based on the user’s choice (= numbers in the ascending order, numbers in the descending order, or numbers in the random order). After that, your program should run the sorting algorithms for the input data and display execution time information (= elapsed time) for each sorting algorithm.

For the program, you have to use a dynamic memory to hold a big input size such as 10,000, 50,000 or more. For details on the dynamic memory, refer to http://www.cplusplus.com/doc/tutorial/dynamic/ If your program uses a vector or any other container, you will get zero without grading.

For the homework, you can refer to the source programs on the Internet for the sorting algorithms. However, you have to change them properly to use the dynamic memory. And also, you have to cite the source code website(s) in your head comment. 


This is a sample result of your program:

Enter input size: 350
========== Select Order of Input Numbers ==========
     1. Ascending Order
     2. Descending Order
     3. Random Order
Choose order: 1
============================================================
Generate input data in ascending order . . .
Done.
============================================================

========================== 1st Run =========================
Insertion sort: 0.00005 milliseconds
Merge sort:     0.00021 milliseconds
Quick sort:     0.00040 milliseconds
============================================================

========================== 2nd Run =========================
Insertion sort: 0.00002 milliseconds
Merge sort:     0.00023 milliseconds
Quick sort:     0.00037 milliseconds
      ============================================================

========================== 3rd Run =========================
Insertion sort: 0.00016 milliseconds
Merge sort:     0.00031 milliseconds
Quick sort:     0.00041 milliseconds
      ============================================================

========================== Ranking =========================
(1) Insertion sort
(2) Merge sort
(3) Quick sort
      ============================================================


In the sample execution, your program should generate 350 integer numbers in the ascending order. For the homework, you have to display the “elapsed time” in milliseconds. Additionally, the elapsed time result on the sample run is not an actual execution time. It’s just random numbers entered by the instructor without any consideration. When you display the elapsed time, exclude the time to generate the input data. You have to measure only the sorting time. And also, all sorting algorithms should use the same input data.
For the performance comparison, your program should run the sorting algorithms three times. Then, it should display the ranking of them based on the average of three results.


This is another sample result:

Enter input size: 50000
========== Select Order of Input Numbers ==========
     1. Ascending Order
     2. Descending Order
     3. Random Order
Choose order: 3

============================================================
Generate input data in random order . . .
Done.
============================================================

========================== 1st Run =========================
Insertion sort: 0.012345 milliseconds
Merge sort:     0.067809 milliseconds
Quick sort:     0.008987 milliseconds
============================================================

========================== 2nd Run =========================
Insertion sort: 0.022345 milliseconds
Merge sort:     0.077689 milliseconds
Quick sort:     0.008987 milliseconds
      ============================================================

========================== 3rd Run =========================
Insertion sort: 0.012345 milliseconds
Merge sort:     0.069799 milliseconds
Quick sort:     0.004987 milliseconds
      ============================================================

========================== Ranking =========================
(1) Quick sort
(2) Merge sort
(3) Insertion sort
      ============================================================