CST 370 –  Homework 9 

CST 370 – 
Homework 9 

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


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


1. Write a C++ (or Java) program called hw9_1.cpp (or hw9_1.java) to conduct heap operations. 

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















The first line (= 5 in the example) indicates that there are five numbers in the second line (= 10, 20, 30, 40, and 70 in the example). Your program should read the numbers and display if it’s a max heap or not. If it’s not a max heap, your program should construct a heap with the numbers. Thus, this is the heap built with the input data. 












The third line (= 10 in the example) indicates the number of commands you have to conduct to the heap. The commands include “displayMax”, “insert” (= insert a number to the heap and do the “heapify” to adjust the heap), “deleteMax”, “delete” (= delete a number from the heap and do the “heapify” to adjust the heap) , “update” (= update a number in the heap and do the “heapify” to adjust the heap), and “display” (= display all nodes in the heap on the screen).
Thus, for the “displayMax” command, your program should display “70” on the screen. After that, your program should insert “50” and “15” to the heap. This is the result after the two insert operations.














For the “deleteMax” command, your program should delete the max (= 70) from the heap. This is the result.












For the “delete” command, your program should search the heap from the root and remove it by overwriting it with the last element in the heap. After that, you should do the “heapify” to adjust the heap. For the sample command (= delete 40), your program should swap 40 with 15. Then heapify the heap. This is the result after the operation. Note that the delete command is not a standard operation of the heap. However, you should implement it for the educational purpose.











For the “update” command, your program should search the heap from the root and update the value in the index with the value provided. After that, you should do the “heapify” to adjust the heap. For the sample command (= update 2 55), your program should update the value in the index 2 (= “20” at the moment) with 55. Then, heapify the heap. This is the result after the operation. Note that the update command is not a standard operation of the heap. However, you should implement it for the educational purpose.













As another example of the “update” command, this is the result after the command “update 2 5”. 















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

5
10 20 30 40 70
10
displayMax
insert 50
insert 15
deleteMax
delete 40
display
update 2 55
display
update 2 5
display


This is the correct output. For the input data, your program should display that it’s not a heap. Then, 70 is the current max of the heap for the command “displayMax”. The result (= 50 20 30 10 15) is the result of “display” command after “delete 40”. After that, the two results of “55 50 30 10 15” and “55 15 30 10 5” are the results of commands “update 2 55” and “update 2 5”. 

This is NOT a heap.
70
50 20 30 10 15
55 50 30 10 15
55 15 30 10 5


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

6
20 10 8 1 3 5
5
display
deleteMax
displayMax
update 4 9
display

This is the correct output. 

This is a heap.
20 10 8 1 3 5
10
10 9 8 5 3



 
2. Write a C++ program (or Java) called hw9_2.cpp (or hw9_2.java) that displays the alphabetical order of characters for an alien language.


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







The first line (= 3 in the example) indicates that there are three words in the following lines which are “caa”, “aaa”, and “aab”. Note that the three words presented in the input are “sorted” order in the alien language. As you can see, the sorted sequence of words is different from our English. 
For the program, you should remember that the alphabetical order of characters in the alien language is different from our English. Your program should determine the correct order of characters of the language. For the homework, you can assume the alien alphabet consists of 26 or fewer characters.

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

3
caa
aaa
aab

This is the correct output. Since the word “caa” comes before “aaa” and “aab”, you know that the character ‘c’ should come before the character ‘a’. Similarly, you know that the character ‘a’ precedes ‘b’ based on the sequence “aaa” and “aab”.

c->a->b


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

9
caa
eeb
eef
aaa
aab
deed
deeb
def
daad

This is the correct output. 

c->e->a->d->b->f



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

3
aaa
bbb
abab


This is the correct output. Note that this input sequence is not valid. Since the words “bbb” follows “aaa”, you know that the character ‘a’ should come before the character ‘b’. However, the word “abab” follows “bbb”, which indicates that the character ‘b’ should come before the character ‘a’. If the input is not valid or your program can’t decide the order of characters from the input words given, your program should display “Invalid input.” on the screen.

Invalid input.


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

5
aab
bba
ddd
cca
ccc

This is the correct output. 

a->b->d->c


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

5
aab
bba
ddd
ccc
cca

This is the correct output. 

Invalid input.


Hint: Construct a direct graph using all characters in the words. Then, use a topological sorting to identify the sequence of the characters.