CST 370  Homework 10 

CST 370 
Homework 10 

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

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


1. Write a C++ (or Java) program called hw10_1.cpp (or hw10_1.java) to conduct the radix sort covered in the lecture 27. 

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

5
77 23 17 5 12


The first line (= 5 in the example) indicates that there are five numbers in the second line (= 77, 23, 17, 5, and 12 in the example) for the sorting. 

This is the correct output. Note that your program should present the intermediate steps of the radix sort.

12 23 5 77 17
5 12 17 23 77


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

12
9 87 199 15 3 214 19 26 58 2 102 23

This is the correct output. 

2 102 3 23 214 15 26 87 58 9 199 19
2 102 3 9 214 15 19 23 26 58 87 199
2 3 9 15 19 23 26 58 87 102 199 214


 
2. Write a C++ (or Java) program called hw10_2.cpp (or hw10_2.java) to simulate the operations of linear probing covered in the class. 

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















The first line (= 5 in the example) is the initial size of the hash table. The second line (= 12 in the example) indicates the number of commands you have to conduct to the hash table. The commands include “insert” (= insert a key to the table), “displayStatus” (= display the status of an entry in the table), “tableSize” (= display the size of the table), “search” (= search a key in the table) and “delete” (= delete a key in the table).
For the first two “insert” commands, the table will be like below. 
Index    Key Value    State
0        Empty
1        Empty
2    17    Active
3    12    Active
4        Empty







Note that if the load factor becomes greater than 0.5 after a new insert, you have to conduct the rehashing. In other words, you have to find the first prime number that is twice as large as the current table size and move the valid keys in the current table to the new table. After that, you have to insert the new key value. This is the result after the “insert 20” command.
Index    Key Value    State
0        Empty
1    12    Active
2        Empty
3        Empty
4        Empty
5        Empty
6    17    Active
7        Empty
8        Empty
9    20    Active
10        Empty






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

5
12
insert 17
insert 12
displayStatus 2
tableSize 
insert 20
tableSize
search 20
search 15
displayStatus 1
delete 12
displayStatus 1
displayStatus 2

This is the correct output. For the “displayStatus” command, your program should display the status of an entry of the table. For example, your program should display “17 Active” for the first “displayStatus 2” command. For the second “displayStatus 2” command, it should display “Empty”.

17 Active
5
11
20 Found
15 Not found
12 Active
12 Deleted
Empty



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

7
8
insert 100
insert 16
insert 37
delete 16
displayStatus 3
insert 72
displayStatus 2
displayStatus 3

This is the correct output. 

16 Deleted
100 Active
72 Active