CST 370 – Homework 4

CST 370 –
Homework 4

How to turn in? 
•    Submit three source files (hw4_1.cpp, hw4_2.cpp, hw4_3.cpp (or hw4_1.java, hw4_2.java, hw4_3.java)) on the iLearn. 


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


1. Write a C++ (or Java) program called hw4_1.cpp (or hw4_1.java) that reads a string and check if it’s well-formed or not.


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




The input has only one string with the characters {, }, (, ), [, and ]. If the different types of brackets match in the correct order, we say that it’s well-matched. For example, the sample input is well-matched. As another example, “[()[]{()()}]” is also well-matched. But “{]” and “{()[[]}” are not well-matched.

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

([]){()}

This is the correct output. 

TRUE


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

[()[]{()(

This is the correct output. 

FALSE



 
2. Write a C++ (or Java) program called hw4_2.cpp (or hw4_2.java) that reads a number of input values and the values themselves. Then, your program should put all negative numbers in front of all positive numbers. Remember that we covered this problem in a puzzle. For your reference, read this document: https://bit.ly/2tVfxKt 


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





The first line (= 8 in the example) indicates that there are 8 integer values in the second line, and the actual 8 values in the second line. 

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

8
5 -3 1 -9 -8 2 -4 7

This is the correct output. Your program should display the results of the two approaches described in the document (= https://bit.ly/2tVfxKt) on the screen.

-4 -3 -8 -9 1 2 5 7
-3 -9 -8 -4 1 2 5 7


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

8
-4 3 9 -6 2 -5 8 7

This is the correct output. 

-4 -5 -6 9 2 3 8 7
-4 -6 -5 3 2 9 8 7


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

5
-10 -30 25 -15 40

This is the correct output. 

-10 -30 -15 25 40
-10 -30 -15 25 40




 
3. Write a C++ (or Java) program called hw4_3.cpp or (hw4_3.java) that reads an input graph data from a user first. Then, it should present a path for the travelling salesman problem (TSP). In the assignment, you can assume that the maximum number of vertices in the input graph is less than or equal to 20.

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



















The first line (= 4 in the example) indicates that there are four vertices in the graph. The following four lines describe the names of four cities such as Monterey, LA, SF, and SD. For the problem, you should assume that the first city (= Monterey in the example) is the starting city of the TSP. In addition, you can assume that the city name is always one word. The next line (= 12 in the example) indicates the number of edges in the graph. The remaining 12 lines are the edge information with the “source city”, “destination city”, and “cost”. Thus, the input data describes a directed graph like below:












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

4
Monterey
LA
SF
SD
12
Monterey LA 2
Monterey SD 7
Monterey SF 5
LA Monterey 2
LA SF 8
LA SD 3
SF Monterey 5
SF LA 8
SF SD 1
SD Monterey 7
SD LA 9
SD SF 1

This is the correct output. Your program should present the path and total cost in separate lines.

Path:Monterey->LA->SD->SF->Monterey
Cost:11 


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

5
Fresno
LA
SD
SF
NYC
6
Fresno SD 8
SD LA 7
SD NYC 3
LA NYC 100
SF Fresno 20
SF SD 19

This is the correct output.

Path:
Cost:-1 

Note that if there is no path for the TSP, your program should present empty path and -1 cost.









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

5
Fresno
LA
SD
SF
NYC
7
Fresno SD 8
SD LA 7
SD NYC 3
LA NYC 100
SF Fresno 20
SF SD 19
NYC SF 50

This is the correct output of your program.

Path:Fresno->SD->LA->NYC->SF->Fresno
Cost:185 

This is the directed graph of the input data:













[Hint]: To solve this problem, you can use all permutations with the cities, except the origin city. For example, there are three cities, LA, SF, and SD in the first sample run, except the origin city Monterey. To make the explanation easy, you can think that LA is number 1, SF is number 2, and SD is number 3. This is all permutations with the three cities
    1, 2, 3
    1, 3, 2
    2, 1, 3,
    2, 3, 1
    3, 1, 2
    3, 2, 1

For each permutation, you can calculate the cost. For example, in the case of the permutation “1, 2, 3”, add the origin city at the very beginning and end to the permutation which generates “0, 1, 2, 3, 0”. This list corresponds to the path “Monterey  LA  SF  SD  Monterey”. Therefore, the cost of this path is “18”. Similarly, the next permutation (= 1, 3, 2) corresponds to “Monterey  LA  SD  SF  Monterey”. The cost is 11. This way, you can check all possible paths for the TSP.


This is a sample C++ program to display permutations: https://repl.it/@YBYUN/permutationsusingSTL