CST 370 – Homework 5

CST 370 –
Homework 5

How to turn in? 
•    Submit your three C++ (or Java) source files on the iLearn. 


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


1. Write a C++ (or Java) program named hw5_1.cpp (or hw5_1.java) which checks if an input string is a palindrome or not. In the problem, a palindrome means an alphanumeric string which reads the same front to back. For the problem, you should ignore case and remove all non-alphanumeric characters in the input string. For example, “Race car”, “I did, did I?”, “7...8 Don't nod 87.” are all palindromes. But “CSU MB” is not a palindrome.
In this program, you have to use a recursive function to check the palindrome. For the grading, we will read your source code. If you do not use a recursive function to check it, you will get zero even if your program passes all test cases.


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

Race car

This is the correct output of your program.

TRUE


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

7...8 Don't nod 78.

This is the correct output of your program.

FALSE


 
2. Write a C++ (or Java) program named hw5_2.cpp (or hw5_2.java) that displays the city names in the range of hop(s) from a starting city. For this problem, refer to the sample BFS program at https://repl.it/@YBYUN/BFS

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. The next line (= 6 in the example) indicates the number of edges in the graph. The following six lines are the edge information with the “source city” and “destination city”. The following city (= Monterey in the example) is the starting city, and the last line (= 2 in the example) indicates the hops from the starting city. Thus, the problem is to list the city names that can be reached from the source in two hops. This is the graph with the input information. 











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

4
Monterey
LA
SF
SD
6
Monterey LA
LA SD
SD Monterey
SF Monterey
SF LA
SF SD
Monterey
2

This is the correct output. Your program should present the city names in the ascending order like below.  Note that LA can be reached from Monterey in one hop, Monterey in zero hop, and SD in two hops. For the problem, you can assume that the city name is always one word.

LA
Monterey 
SD


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

4
Monterey
LA
SF
SD
6
Monterey LA
LA SD
SD Monterey
SF Monterey
SF LA
SF SD
LA
1

This is the correct output. 

LA
SD



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

5
Fresno
LA
SD
SF
NYC
6
SD LA
SD NYC
LA NYC
SF Fresno
SF SD
Fresno SD
SF
2

This is the correct output.

Fresno
LA
NYC
SD
SF


This is the graph for the input data

















 
3. Write a C++ (or Java) program called hw5_3.cpp (or hw5_3.java) that implements the Depth-First Search (DFS) algorithm using a stack and a mark array as you learned in the class. 

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. For the homework, you can assume that the first vertex starts from the number 0. The second line (= 2 in the example) represents the number of edges, and following two lines are the edge information. This is the graph with the input information.











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

3 
2
0 1
1 2

This is the correct output. Your program should display the mark array of DFS. For the problem, you can assume that the starting vertex is always 0. And also, you can assume that the graph is connected.

Mark[0]:1
Mark[1]:2
Mark[2]:3


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

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

This is the correct output. 

Mark[0]:1
Mark[1]:2
Mark[2]:5
Mark[3]:3
Mark[4]:4


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

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

This is the correct output. 

Mark[0]:1
Mark[1]:2
Mark[2]:4
Mark[3]:5
Mark[4]:3