Description

Instructor: Prof. Ilwoo Lyu
Teaching Assistants: Seunghwan Lee, Jiwon Son, Juncheol Shin, Wonjun Lee

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

Evaluation Policy:
● Late Submission Penalty
Late submission penalty (30%)
– will be applied to the total score.
100% penalty
– will be applied for the submission and marked as zero.
● We do not accept any submission via email; they will be ignored.
keyboard-typed submissions for the written assignment
● We do not accept any .
● You can do your written assignment in two ways:
○ Use tablet (i.e. Galaxy Tab, iPad, etc) and stylus pen, and save your work as .pdf.
○ Write on any paper, scan it, and save as .pdf file
– We recommend using Microsoft Lens to scan your works.
your process of solving the problems
○ Please describe as detailed as possible.
○ If you write down your answer only, you will not earn a point.
● 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
○ Full points will be given only if all test cases are passed; there are no partial points if only some portion of the test cases work, and the others don’t.
○ Points will be deducted for any typos or incorrect formatting
● Compile your code using “Replit” and check your program before submission.
You should not use C++ standard template library
● other than given ones.
○ DO NOT INCLUDE <queue>, <vector>, <stack>, or other container libraries ○ Any submission using such STL library will be disregarded.
○ Using only the given libraries will suffice.

Files You Need to Submit:
[your_student_id]_assignment3.zip
● .zip file named (i.e. 20241234_assignment3.zip) containing:
○ task1.cpp
○ task2.cpp
○ task3.cpp
○ task4.cpp
○ ds.h (optional)
○ wa3.pdf (written assignment)

If You Find Bugs in the Program:
as soon as possible
● Please notify us

Any other questions? Please use PLMS Q&A board in English.

Written Assignment #3

Q1. (1pt)
You are given an array, each element contains three values : primary key, secondary key, and tertiary key. Sort the array using bubble sort based on the following criteria, and show the intermediate arrays after each step:
1. Primary Sort : Sort by the primary key in ascending order.
2. Secondary Sort : For elements with the same primary key, sort by the secondary key in descending order
3. Tertiary Sort : For elements with the same primary and secondary keys, sort by the tertiary key in ascending order.
All the criteria above must be considered simultaneously. Do not sort sequentially by primary, secondary, and tertiary keys.
Given Array:
[(Primary: 2, Secondary: 5, Tertiary: 8), (Primary: 1, Secondary: 3, Tertiary: 7), (Primary: 2,
Secondary: 5, Tertiary: 6), (Primary: 1, Secondary: 4, Tertiary: 9), (Primary: 2, Secondary: 3, Tertiary: 5)]

Q2. (Total 1pt, 0.5pt each)
Consider following sequence of keys inserted into an initially empty tree:
12 → 5 → 7 → 100 → 30 → 60 → 90 → 70 → 55 → 43
(a) Assume a 2-3 tree. Draw the structure of the tree after each insertion.

(b) Now, delete the node with key 30. Draw the structure of the tree after this deletion.

Programming Assignment #3

Basic Instruction (Example)

$ g++ -std=c++11 -o task_* task*.cpp
But please submit your files with specified format

[Task 1] Sorting (5pts)

Description
Implement a function that sorts a given array in ascending order using both the Bubble Sort and Selection Sort sequentially. The elements of the array and number of iterations for Bubble sort will be provided as input. If the specified number of iterations is greater than the number of elements, complete the sorting using only Bubble Sort. You must show the intermediate state of the array after each iteration, including the initial array. (The total output should include the initial state + each step, for a total of number of elements results.) Refer to the Example Input & Output for clarity. Number of total instructions won’t exceed 1,000.
Input
● A sequence of instructions, each in one of the following formats:
○ (‘Bubble’, integer): Specifies the number of iterations for Bubble Sort.
○ (‘insert’, integer value): Inserts the specified integer values into the array.
● Array indices are zero-based index.
Output
● After each iteration, output the resulting array as a string of space-separated elements with no trailing space at the end.

Input Output
[(‘Bubble’,100), (‘insert’,42), (‘insert’,20),
(‘insert’,17), (‘insert’,13), (‘insert’,28), (‘insert’,14)] 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
[(‘Bubble’,0), (‘insert’,42), (‘insert’,20),
(‘insert’,17), (‘insert’,13), (‘insert’,28), (‘insert’,14)] 42 20 17 13 28 14
13 20 17 42 28 14
13 14 17 42 28 20
13 14 17 42 28 20
13 14 17 20 28 42
13 14 17 20 28 42
[(‘Bubble’,2), (‘insert’,42), (‘insert’,20),
(‘insert’,17), (‘insert’,13), (‘insert’,28),
(‘insert’,14)] 42 20 17 13 28 14
13 42 20 17 14 28
13 14 42 20 17 28
13 14 17 20 42 28
13 14 17 20 42 28
13 14 17 20 28 42
Example Usage
$ ./task1 “[(‘Bubble’,100), (‘insert’,42), (‘insert’,20),
(‘insert’,17), (‘insert’,13), (‘insert’,28), (‘insert’,14)]”
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

:

[Task 2] Binary Search Tree (5pt)

Description
Implement functions for constructing a Binary Search Tree(BST), inserting and deleting nodes, and finding the path and rank of a specific node. In this context, the path means the sequence of nodes from the root to the specified destination node, and the rank of a node with value x is the number of other nodes in the tree whose values are ≤ x (Exclude the node itself when calculating the rank. Since we won’t have duplicated values, we can think of rank as the number of other nodes in the tree whose values are < x).
The initial BST is constructed based on a pre-order or post-order traversal given as input (‘PRE’ or ‘POS’). Next, follow a sequence of instructions (‘ADD’, ‘DEL’) to add or delete nodes.
For deletions, always use the left subtree if available.
After constructing the BST, a node will be specified, and you are to output its rank and the path from the root to that node (‘NOD’). If an error occurs, print “ERROR” and the problematic instruction.
*You don’t need to consider duplicated values in different nodes.
Input
● N : number of input lines
● A Sequence of instructions
○ (‘POS’, [integer1, integer2, …]) : First instruction, gives a post-order traversal of the initial tree.
○ (‘PRE’, [integer1, integer2, …]) : First instruction, gives a pre-order traversal of the initial tree.
○ (‘ADD’, integer) : Inserts the specified integer as a node.
○ (‘DEL’, integer) : Deletes the node with the specified integer value.
○ (‘NOD’, integer) : Specifies the node for which rank and path are to be printed. (This is the last instruction)
Output
● “ERROR” and problematic instructions for the cases of:
○ If node specified by NOD operation doesn’t exist (ERROR: NOD integer)
○ If node specified by DEL operation doesn’t exist (ERROR: DEL integer) ● Rank and Path to node specified by ‘NOD’ operation for a valid input.
○ Rank: (Answer)
○ Path: (Ans1, Ans2, Ans3, …)
– Each value must be shown with spaces between each element, but no space at the end.
input_2.txt output_2.txt
4
POS [2,1,4,5,3,7,10,9,8,6]
ADD 11
DEL 6
NOD 7 Rank: 5
Path: 5 8 7

5
POS [2,1,4,5,3,7,10,9,8,6]
ADD 11
DEL 6
DEL 15
NOD 4 ERROR: DEL 15
4
POS [2,1,4,5,3,7,10,9,8,6]
ADD 11
DEL 6
NOD 6 ERROR: NOD 6

[Task 3] AVL Tree (5pt)

Description
Consider AVL tree where each node contains an interval (a closed range) rather than a single value. Implement the following operations for this tree
1. Insertion and Deletion: Use the low value of each interval as the key to maintain the AVL tree’s order. (Do not consider duplication of low values of intervals.) Handle any balance violations that occur during insertion or deletion by applying rotations as needed.
2. Interval Search: This function should return all intervals that overlap with a specified interval, traversed in pre-order
All instructions must be read from an input file, ‘input_3.txt’, and the results of the Interval
Search operation should be written to ‘output_3.txt’
* You can always assume ≤ .
Input
● N : number of input lines for construction of AVL tree ● A Sequence of instructions (N lines)
○ (‘ADD’, nst − ) : Insert a node with interval nst −
○ (‘DEL’, nst − ) : Delete node with interval nst − ● nst − : input interval for Interval Search operation.

* N lines of input + final line for interval Search will be given. (Total N+1 lines. See Example Input & Output for more detail)
Output
● For a valid input, output of Interval Search operation, following order of pre-order traversal.
● ERROR if DEL operation specifies an interval doesn’t exist.
● Interval should be formatted with hyphens between bounds, with spaces between each interval but no trailing space at the end.

input_3.txt output_3.txt
6
ADD 21-40
ADD 26-30
ADD 30-64
ADD 9-15
ADD 4-11
ADD 14-18
9-21 21-40 9-15 4-11 14-18
7
ADD 21-40
ADD 26-30
ADD 30-64
ADD 9-15
ADD 4-11
ADD 14-18
DEL 100-110
9-21 ERROR

[Task 4] Hashing (3pt)

Description
Implement a closed hash table with reshashing implementation. This hash table is used with n-bit integer keys and hashing into a table of size 2r. And, this hash table uses quadratic probing as a collision handling method. The index of the key k after i-th collision, hi(), is :
hi() = (ℎ() + ()) 2
where ℎ(k) is the binary mid-square hash function. This function maps an n-bit integer key to an index of a 2r-sized table. As a key is n bits, your code should treat the square of the key as 2 bits. You can assume that is even. () is :
() = 2 + + 1
You need to print FULL and exit for an insertion when the table is full, and print ERROR for a deletion of a key which does not exist. You don’t need to consider the case when the hash function cannot find an available slot or multiple insertions of the same key.
Number of total instructions won’t exceed 1,000.
Input
● A sequence of instructions
○ (‘n’, integer) : the size of a key. The first instruction.
○ (‘r’, integer) : the size of an index. The second instruction.
○ (‘insert’, integer) : insert integer into the hash table.
○ (‘delete’, integer) : delete integer from the hash table.
Output
● For each slot of the hash table, print out
○ The value, if the state of the slot is occupied. (OCCUPIED state) ○ ‘empty’ if the state of the slot is empty. (EMPTY & DELETED states) ● “ERROR” for deletion of a key which does not exist. ● “FULL” for insertion when the table is full ● See examples for better understanding.

Example Input & Output
Input Output
[(‘n’,4), (‘r’,2), (‘insert’,1),
(‘insert’,2), (‘insert’,3)] 0: 1
1: 3
2: empty
3: 2
[(‘n’,4), (‘r’,2), (‘insert’,1),
(‘insert’,2), (‘insert’,3),
(‘delete’,2), (‘delete’,3)] 0: 1
1: empty
2: empty
3: empty
[(‘n’,4), (‘r’,2), (‘insert’,1),
(‘insert’,2), (‘insert’,3),
(‘delete’,2), (‘delete’,3),
(‘insert’,4)] 0: 1
1: empty
2: 4
3: empty
[(‘n’,4), (‘r’,2), (‘insert’,1),
(‘insert’,2), (‘insert’,3),
(‘insert’,4), (‘insert’,6)] FULL
[(‘n’,4), (‘r’,2), (‘insert’,1),
(‘insert’,2), (‘insert’,3),
(‘delete’,2), (‘delete’,3),
(‘insert’,4), (‘delete’,3)] ERROR

● Example execution
$ ./task4 “[(‘n’,4), (‘r’,2),
(‘insert’,3)]”
0: 1
1: 3
2: empty
3: 2 (‘insert’,1), (‘insert’,2),