[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

Programming Assignment #3
Lecturer: Prof. Seung-Hwan Baek
Teaching Assistants: Suhyun Shin, Eun-Sue Choi, Jin-Nyeong Kim, Hoon-Gyu Chung

**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****

Due date: 11:59 PM May 8, 2025

Evaluation policy:
● Late submission penalty
○ 11:59 PM May 8 ~ 11:59 PM May 9
■ Late submission penalty (30%) will be applied to the total score
○ After 11:59 PM May 9
■ 100% penalty is applied for that submission

● Your code will be automatically tested using an evaluation program

○ Each problem has the maximum score
○ A score will be assigned based on the behavior of the program

● We won’t accept any submission via email - it will be ignored

● Do not modify auxiliary files.

○ Such as: utils.h/cpp, [Link]

● Compile your file(s) using C++ compiler on 'Replit' or 'CLion' and check your program
before the submission.

● All characters in [Link] should be in uppercase letters except task 4, e.g.,

'TRUE','FALSE',(except for [Task 1], [Task 2], … [Task 6])

● Please do not use the containers in C++ standard template library (STL)
○ Such as:
■ #include <queue>
■ #include <vector>
■ #include <stack>

-1-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

○ Any submission using the containers in STL will be disregarded

File(s) you need to submit:

● Files you need to submit. (Do not change the filename.)
○ [Link]
○ [Link] and sort.h
○ [Link] and tree.h
○ [Link] and bst.h
○ [Link] and avl.h
○ open_hash_function.cpp and open_hash_function.h
○ open_hash_table.cpp and open_hash_table.h
○ closed_hash_function.cpp and closed_hash_function.h
○ closed_hash_table.cpp and closed_hash_table.h

Any questions? Please use PLMS - Q&A board.

-2-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

1. Bubble Sort (2 pts)

a. Implement a function that sorts a given array using the Bubble Sort algorithm.
On path k, the k-th lowest key rises to k-th position. Iteratively swap the
adjacent items if the below item has a lower key value. If there were no swap in
the current iteration, the array is sorted.
You can modify [Link] and sort.h files for this problem.
b. Input & Output
Input: A sequence of integers
Output:
- Print every value in the array whenever the k-th lowest key rises to k-th
position from other position. Please use a built-in function to print the
array.
- We won’t test array size over 1000 or array size of 0.

c. Example Input & Output

-3-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

Input Output
"42 20 17 13 28 14" 13 42 20 17 14 28
13 14 42 20 17 28
13 14 17 42 20 28
13 14 17 20 42 28
13 14 17 20 28 42
"17 20 2 21 4" 2 17 20 4 21
2 4 17 20 21

"7 6 5 4 3 2 1" 1 7 6 5 4 3 2
1 2 7 6 5 4 3
1 2 3 7 6 5 4
1 2 3 4 7 6 5
1 2 3 4 5 7 6
1 2 3 4 5 6 7

d. Example execution
>> ./[Link] 1 "42 20 17 13 28 14"
[Task 1]
13 42 20 17 14 28
13 14 42 20 17 28
13 14 17 42 20 28
13 14 17 20 42 28
13 14 17 20 28 42

-4-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

2. Non-recursive Merge Sort (2 pts)

a. Implement a function that sorts a given array using the Merge Sort algorithm in
descending order using non-recursive merge sort. Start with the sorted
segments of size 1 and do pairwise merging of these sorted segments as in the
upward pass.
You can modify [Link] and sort.h files for this problem.

b. Input & Output

Input : A sequence of integers
Output:
- Starting from the initial state of the array, print all values of the array at
each iteration step after performing the necessary sorting. Print the
array values at each iteration step where sorting is performed.
- Separate the values in the array with a space for each iteration step.
- You don’t need to consider exceptional cases such as overflow or an
empty array. We will not test such cases.
- We won’t test array size over 5000 or array size of 0.

c. Example Input & Output

-5-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

Input Output

"56 42 20 17 13 28 14" 56 42 20 17 28 13 14
56 42 20 17 28 14 13
56 42 28 20 17 14 13

"36 20 17 13 14 28 15 23 32" 36 20 17 13 28 14 23 15 32
36 20 17 13 28 23 15 14 32
36 28 23 20 17 15 14 13 32
36 32 28 23 20 17 15 14 13

"1 2 3 4 5 6 7" 2 1 4 3 6 5 7
4 3 2 1 7 6 5
7 6 5 4 3 2 1

d. Example execution
>> ./[Link] 2 "56 42 20 17 13 28 14"
[Task 2]
56 42 20 17 28 13 14
56 42 20 17 28 14 13
56 42 28 20 17 14 13

-6-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

3. BST Insertion / Deletion / isBalanced (3pts)

a. Implement functions that inserts and deletes an element into a binary search
tree (BST). Also you should find whether the BST is balanced(BST is balanced if
for every node, the difference in height between its left and right sub-trees is at
most 1.), and print the pre-order and in-order of the tree. You can modify
[Link] and bst.h files for this problem.
- Input of nodes are integers from 1 to 99

<Example of balance>

Balanced Not Balanced

b. Input & output of BinarySearchTree::insertion

Input:
- ('insertion',integer): Key of the element to be inserted. The key
has a positive integer value.
Output:
- Return the -1 if the key already exists in the tree, 0 otherwise.
(If the key already exists, do not insert the element)

c. Input & output of BinarySearchTree::deletion

Input:
- ('deletion',integer): Key of the element to be deleted.
Output:

-7-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

- Return -1 if the key does not exist in the tree, 0 otherwise. If the key does
not exist, do not delete any element.
Note that replace the smallest key in right subtree when delete the node with
degree 2

d. Input & output of BinarySearchTree::isBalanced

Input:
- ('isBalanced',NULL): Check if the BST is balanced.
Output:
- Return TRUE if balanced, else FALSE.

e. task_3 prints
i. the return for each insertion/deletion for command (‘insertion’, integer)/
(‘deletion’, integer) and
ii. the return whether it is balanced or not for command (‘isBalanced’,
NULL) and
iii. the results of preorder and inorder traversal of the constructed tree for
command (‘print’, NULL).
(If empty tree, don’t return preorder and inorder traveral results)

f. Example Input & Output

Input Output

[('insertion',4), ('insertion',6), 0
('insertion',6), ('insertion',7), 0
('deletion',7), ('print', NULL), -1
('isBalanced', NULL)] 0
0
4 6
4 6
TRUE

[('insertion',12), ('insertion',5), 0
('insertion',3), 0
('insertion',8),('insertion',17),('inserti 0
on',13),('insertion',19),('insertion',18), 0
('deletion',12),('isBalanced', NULL), 0
('print', NULL)] 0
0

-8-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

0
0
FALSE
13 5 3 8 17 19 18
3 5 8 13 17 18 19

[('deletion', 3),('insertion', -1
10),('deletion', 10), ('print',NULL)] 0
0

g. Example execution
>> ./[Link] 3 "[('insertion',12), ('insertion',5),
('insertion',3),('insertion',8),('insertion',17),('insertion',1
3),('insertion',19),('insertion',18), ('isBalanced',
NULL),('deletion',12),('isBalanced', NULL)]"
[Task 3]
0
0
0
0
0
0
0
0
TRUE
0
FALSE

-9-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

4. K-th Most Frequent Letter using AVL Tree (10 pts)

Implement a class ‘AVLTree’ to efficiently count and report the frequency of each
alphabet letter in a string using AVL tree operations. This involves handling imbalances
that might occur during insertions and deletions, as well as ensuring that alphabet
letters are counted accurately. As the string is received, insert each letter sequentially
from the beginning to the end into the AVL tree.

a. AVL Tree Implementations

- Modify or implement functions in the ‘AVLTree’ class that insert and delete
elements (letters in this case).
- Implement functions in the ‘AVLTree’ class that print the all node
information in pre-order, in-order, and reverse-in-order manner.
- Ensure the AVL tree can resolve imbalances (LL, LR, RL, RR) that might occur
after modifications.
- You can modify ‘[Link]’ and ‘avl.h’ files, and if needed, add public members
to the ‘Node’ class implemented in ‘tree.h’.

b. Details of the process

- Sequentially insert each letter from the string. If a node for that letter
already exists, delete the existing node, increment the count, and re-insert
the node.
- If k is larger than the number of unique letter in the input, print “ERROR”.
- During the deletion process, if a node has both children, use the
replacement method where you find the minimum in the right subtree to
replace the node
- Use the following ordering for the AVL tree:
 If frequencies are equal, follow on the lexicographical order of the
letters.
E.g., (c, 1) < (a, 2) < (b, 2)

c. Input & Output:

- Input:

-10-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

 A string consisting of at least one alphabetical letter. You don’t need to

consider any other input cases and uppercase and lowercase of letters
are same.
 An integer k representing the k-th most frequent letter to return. (k
starts from 1)
- Output:
 Frequencies of alphabetic letters are displayed in descending order of
frequency, which corresponds to a reverse-inorder traversal of the AVL
tree.
 The k-th most frequent letter and its count.
 The results of reverse-inorder, inorder and preorder traversal of the
constructed tree.

d. task_4 prints
i. The frequencies sorted from highest to lowest (reverse-inorder)
ii. The k-th most frequent letter and the count
iii. The format of node for printing is “(letter, count)”

e. Example Input & Output

Input Output

“aabbbccccddDDd 2” Frequencies: (d, 5) (c, 4) (b, 3) (a, 2)

Inorder: (a, 2) (b, 3) (c, 4) (d, 5)
Preorder: (b, 3) (a, 2) (c, 4) (d, 5)
K-th most frequent letter: (c, 4)

“a 2” Frequencies: (a, 1)
Inorder: (a, 1)
Preorder: (a, 1)
K-th most frequent letter: ERROR

“AaaBBBccc 1” Frequencies: (c, 3) (b, 3) (a, 3)

Inorder: (a, 3) (b, 3) (c, 3)
Preorder: (b, 3) (a, 3) (c, 3)
K-th most frequent letter: (c, 3)

-11-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

f. Example execution
>> ./[Link] 4 “AaaBBBccc 1”

[Task 4]
Frequencies: (c, 3) (b, 3) (a, 3)
Inorder: (a, 3) (b, 3) (c, 3)
Preorder: (b, 3) (a, 3) (c, 3)
K-th most frequent letter: (c, 3)

5. Open hash table Distribution Tracker(2 pts)

a. Implement an open hash table using the digit-folding method as the hash
[Link] hash table uses singly linked lists (chaining) to handle collisions.
The hash function computes the sum of the digits of the key and takes the
modulo with the table size M:
index = (sum of digits of key) % M

The program should support the following operations:

- Initialize the hash table with a given size M.
- Insert integer keys into the hash table.
- Delete integer keys from the hash table.
- Report the number of used indices and the number of keys at each used index.

Note:
- No duplicate insertions or deletions of non-existent keys will be tested.
- You may modify open_hash_function.cpp, open_hash_table.cpp,
open_hash_function.h, and open_hash_table.h files for this problem.

b. Input & Output

Input: A sequence of commands
- ('M',integer): the size of a hash table.
- (The first command should always be 'M')
- ('insertion',integer): insert integer into the hash table.

-12-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

- ('deletion',integer): delete integer from the hash table.

- ('report', 0): print current distribution of the hash table.
Output: Upon receiving the 'report' command, output the following
- The number of indices currently used (i.e., indices with at least one key).
- For each used index, print the index number and the number of keys stored
at that index.
ex)
[Task 5]
USED <#used slots>
INDEX <i>: <k> KEYS
INDEX <j>: <l> KEYS
...
(Printed in increasing order of indices)
c. Example Input & Output
Input Output

[('M',5),('insertion',15),('insertion',42),(' USED 2
insertion',27),('report',0)] INDEX 1: 2 KEYS
INDEX 4: 1 KEYS

[('M',5),('insertion',15),('insertion',42),(' USED 2
insertion',27),('deletion',42),('report',0)] INDEX 1: 1 KEYS
INDEX 4: 1 KEYS

[('M',5),('insertion',15),('insertion',42),(' USED 2
insertion',27),('report',0),('deletion',42),( INDEX 1: 2 KEYS
'insertion',43),('report',0)] INDEX 4: 1 KEYS
USED 3
INDEX 1: 1 KEYS
INDEX 2: 1 KEYS
INDEX 4: 1 KEYS

d. Example execution
>> ./[Link] 5 “[('M',5), ('insertion',15), ('insertion',42),
('insertion',27), ('report',0)]"
[Task 5]
USED 2
INDEX 1: 2 KEYS
INDEX 4: 1 KEYS

-13-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

6. Closed hash table (3 pts)

a. Implement insertion of a closed hash table with rehashing implementation. This

hash table is used with integer keys and hashing into a table of size M. This hash
table uses pseudo-random probing as a collision handling method. The index of
the key 𝑘 after 𝑖-th collision, ℎ𝑖 (𝑘), is:

ℎ𝑖 (𝑘) = (ℎ(𝑘) + 𝑑𝑖 ) 𝑚𝑜𝑑 𝑀

where ℎ(𝑘) is the digit-folding method hash function. It works same with the
hash function in task 5.
𝑑1 , 𝑑2 , … , 𝑑𝑀−1 is a pseudo-random permutation of integers 1, … , M-1 and it is
generated by shift-register sequence. Please refer to slide “Example: Shift-
Register Sequence” in “Hashing” Lecture Note for detail.
Given M, k, 𝑑1 for the shift-register sequence and integers, print the result hash
table. If the hash table is full or the collision cannot be resolved, stop the
insertion and deletion, and print results of the hash table, then print FAIL.

Note:
- No duplicate insertions or deletions of non-existent keys will be tested.
- You may modify closed _hash_function.cpp, closed _hash_table.cpp,
closed_hash_function.h, and closed _hash_table.h files for this problem.

b. Input & Output

Input: A sequence of commands
- ('M',integer): the size of a hash table.
(The first command is always 'M')
- ('k',integer): a constant used for shift-register sequence.
(The second command is always 'k')
- ('d',integer): the first probing offset for the shift-register sequence .
(The third command is always 'd')
- ('insertion',integer): insert integer into the hash table.
- ('deletion',integer): delete integer into the hash table.
Output:
For each slot of the hash table, print out

-14-
[CSED233-01] 2025 Spring, Data Structure, POSTECH PA #3

- the value, if the state of the slot is occupied.

- 'EMPTY' if the state of the slot is empty.
'FAIL' if the hash table is full or the collision cannot be resolved.
c. Example Input & Output
Input Output

[('M',5),('k',3),('d',2), ('insertion',15), 0: 26
('insertion',42), ('insertion',26)] 1: 15
2: EMPTY
3: 42
4: EMPTY

[('M',4),('k',3),('d',2), ('insertion',15), 0: 11
('insertion',42), ('insertion',26), 1: 42
('deletion',42),('insertion',11),('insertion' 2: 15
,42),('insertion',51)]
3: 26
FAIL

[('M',5), ('k',3), ('d',2), ('insertion',2), 0: EMPTY

('insertion',7), ('insertion',11), 1: 11
('insertion',20), ('insertion',18)] 2: 2
3: EMPTY
4: 7
FAIL

d. Example execution
>> ./[Link] 6 “[('M',5),('k',3),('d',2), ('insertion',15),
('insertion',42), ('insertion',26)]”
[Task 6]
0: 26
1: 15
2: EMPTY
3: 42
4: EMPTY

-15-