CST 370 –  Homework 6

CST 370 – 
Homework 6

How to turn in? 
•    Submit your three source files on the iLearn. 

This is the HackerRank link: https://www.hackerrank.com/cst370-s20-hw6 

1. Write a C++ (or Java) program named hw6_1.cpp (or hw6_1.java) which displays the biggest number in an array with n integer numbers using a divide-and-conquer technique. For example, if your algorithm has an input array such as 1, 3, 11, 7, 5, 6, 4, 9, your algorithm should display 11.
In this program, you have to use a divide-and-conquer technique to display the max value. For the grading, we will read your source code. If you do not use a divide-and-conquer technique to find it, you will get zero even if your program passes all test cases.


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

8
1 3 11 7 5 6 4 9

The first line (= 8 in the example) indicates the number of input data, and the following line shows the input values. This is the correct output of your program.

11


Sample Run 2: Assume that the user typed the following one line

3
-3 1 -5

This is the correct output of your program.

1


Sample Run 3: Assume that the user typed the following one line

4
10 99 99 10

This is the correct output of your program.

99
 
2. Write a C++ (or Java) program called hw6_2.cpp (or hw6_2.java) that solves the Knapsack problem. Your program should read the weight and value of each item from a user and determine the best subset. In the program, you can assume that the number of items is less than 15. 

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







The first line (= 2 in the example) is the number of items, and the next line (= 5 in the example) is knapsack capacity. Then, the following two lines indicate the weights and values of 2 items. In this case, the first item’s weight is 3 and the value of it is $12. The second item’s weight is 4 and the value is $10.

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

2
5
3 12
4 10


This is the correct output. Your program should display the item(s) for the optimal solution and the solution’s capacity and value.

Items:1
Capacity:3
Value:12

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

3
5
2 12
1 10
3 20

This is the correct output.

Items:1 3
Capacity:5
Value:32


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

3
1
2 12
3 10
4 20

This is the correct output. Note that there is no solution to the input values. 

Items:
Capacity:
Value:



 
3. Write a C++ (or Java) program called hw6_3.cpp (or hw6_3.java) that connects several connected components of a graph with minimum number of edges to create a single connected component of the graph.

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










The first line (= 6 in the example) indicates that there are six vertices in the graph. For the homework, you can assume that the first vertex starts from the number 0. The second line (= 6 in the example) represents the number of edges in the graph, and following six lines are the edges. This is the graph with the input data. Note that there are three connected components in the graph with the vertices of {0, 2, 4}, {1, 3}, and {5}.











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

6 
6
0 2
2 0
2 4
4 2
3 1
1 3

This is the correct output. Your program should display the new edge(s) to connect the three connected components to make a single connected component.

Edge: 0-1
Edge: 1-5



Because the input graph has three connected components, you need at least two new edges to connect them to make a single component. In this homework, you have to connect the vertices with the smallest vertex numbers in each component. In other words, the vertices, 0, 1, and 5 are the smallest vertex numbers in each component. Thus, the new edges you need to connect are (0, 1) and (1, 5). This is the result graph after adding the two new edges. 











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

5 
8
0 1
1 0
1 2
2 1
4 3
3 4
2 0
0 2


This is the correct output. 

Edge: 0-3



This is the input graph.












To make a single connected component, you need a minimum one edge. In our case, we connect the vertex 0 and vertex 3.


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

3 
4
0 1
1 0
0 2
2 0

This is the correct output. 

No new edge:


This is the input graph. Note that the graph already has only one connected component. Thus, your program should display the message “No new edge:” to indicate that there is no edge necessary in this case.












To make a single connected component, you need a minimum one edge. In our case, we connect the vertex 0 and vertex 3.

Hint: Use the sample BFS program (https://repl.it/@YBYUN/BFS) to identify the connected components in a graph.