CST 370 – Homework 3

CST 370 –
Homework 3
How to turn in? 
•    Submit three C++ (or Java) source files (hw3_1.cpp (or hw3_1.java), hw3_2.cpp (or hw3_2.java), and hw3_3.cpp (or hw3_3.java)) on the iLearn. 

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


1. Write a C++ program called hw3_1.cpp (or hw3_1.java) that reads a number of elements in a set and then read the elements of the set. After that, your program should display all possible binary numbers and corresponding subsets one by one. For the program, you can assume that the number of elements in a set is less than 10.

Sample Run 1: Assume that the user typed the following input. Note that there are three elements in the set with the elements A, B, and C.

3
A B C

This is the correct output.  

000:EMPTY
001:C
010:B
011:B C
100:A
101:A C
110:A B
111:A B C

The first line shows that the binary number is “000”. Note that the first bit ‘0’ is for the element ‘A’, the second bit ‘0’ for the element B, and the last bit ‘0’ for the element C. Since all three bits are ‘0’, the binary number “000” means the empty set. 
The next line indicates that the binary number is “001” and it corresponds to the subset {C} because only the last bit is ‘1’. Similarly, the last line indicates that the binary number is “111” and it corresponds to the subset {A, B, C} because all bits are ‘1’.


Sample Run 2: Assume that the user typed the following input.

2
CST238 CST370

This is the correct output.  

00:EMPTY
01:CST370
10:CST238
11:CST238 CST370


Sample Run 3: Assume that the user typed the following input.

0

This is the correct output of your program.

0:EMPTY



 
2. Write a C++ program named hw3_2.cpp (or hw3_2.java) which partitions n positive integers into two disjoint sets with the same sum. Of course, the problem does not always have a solution. 

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





The first number (= 4 in the example) indicates that there will be four integer values in the input. Then, all values in the second line (= 2, 3, 7, and 8 in the example) are actual numbers. Thus, your program should read them and present one equal set which includes the smallest number of the input values. Because the input values can have two equal sets of {2, 8} and {3, 7}, your program should display 2 and 8 on the screen. Note that the sum of {2, 8} is 10 and the sum of {3, 7} is also 10. For the problem, you can assume that the max number of input integer values is 15. Also, you can assume that the input values are all distinct.

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

4
2 3 7 8

This is the correct output of your program.

Equal Set: 2 8

Note that the sequence of output values is important. Your program has to display the set with the smallest value in the input. So, the correct set is {2, 8}. For the set, your program should display it in the ascending order. Thus, the correct answer is 2 and then 8. 



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

3
7 5 1

This is the correct output of your program.

Equal Set: 0

Since it is not possible to have two equal sets from the input, your program should display just “0” on the screen. 


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

6
3 5 20 7 1 14


This is the correct output of your program.

Equal Set: 1 3 7 14



Sample Run 4: Assume that the user typed the following two lines

5
10 8 6 4 2

This is the correct output of your program.

Equal Set: 0



[Hint]: hw3_1.cpp (or hw3_1.java) can be used for this problem. In other words, you need to consider all possible subsets of the input numbers to solve the problem. 
For example, in the case of first sample run, you have to consider all 16 subsets such as {}, {2}, {3}, {7}, … {2,3,7,8}. For the subsets, you can use the binary representation as you did at hw3_1.cpp. 
For instance, let’s say that you have a binary number 1001. 
Note that the first and last digits of the binary number are ones, and second and third digits are zeros.
Using this information, you can compare two subsets.





 
3. Write a C++ program called hw3_3.cpp (or hw3_3.java) that converts a directed graph data from a user into a corresponding adjacency list format. Your program should read an input graph data from a user. Then, your program should convert it to the adjacency matrix format. In the assignment, you can assume that the maximum number of vertices in the input graph is less than or equal to 50.

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








The first line (= 3 in the example) indicates that there are three vertices in the graph. The second line (= 4 in the example) presents the number of edges in the graph. The remaining four lines are the edge information in the graph. For the homework, you should assume that the first vertex starts from the number 0. Thus, t1.txt describes a directed graph like below:









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

3
4
0 1
0 2
2 1
2 0

This is the correct output of your program.

0->1->2
1
2->0->1 

Note that the sequence of output values is important. For example, when you display the neighbor vertices of the vertex 0, the sequence should be 1 and then 2 (= ascending order). If your program displays 2 and then 1, it’s not correct. Similarly, for the vertex 2, your program should display 0 and then 1.




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

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


This is the correct output of your program.

0->2
1->2
2->3->4
3->4
4


Note that this is the directed graph of the input data:











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

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

This is the correct output of your program.

0->1->2
1->0->2
2->0->1