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

Programming Assignment #1
Lecturer: Prof. Seung-Hwan Baek
Teaching Assistants: Hoon-Gyu Chung, Suhyun Shin, Jinnyeong Kim, Eunsue Choi

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

Due date: 11:59PM March 19, 2025

Evaluation policy:
● Late submission penalty
○ 11:59PM March 19 ~ 11:59PM March 20
■ Late submission penalty (30%) will be applied to the total score.
○ After 11:59PM March 20:
■ 100% penalty is applied for that submission.
● Your code will be automatically tested using an evaluation program.
○ Each problem has a maximum score.
○ A score will be assigned based on the behavior of the program.
○ Full points will be awarded only if all test cases are passed; there are no partial
points.
○ Points will be deducted for any typos or incorrect formatting.
● We won’t accept any submission via email - it will be ignored.
● Do not modify auxiliary files.
○ Such as: utils.h/cpp, [Link], and so on.
● Compile your file(s) using ‘Replit’ or ‘CLion’ and check your program before the
submission.
● All characters in [Link] should be in uppercase letters, e.g., ‘TURE’,’FALSE’,(except
for [Task1], [Task2])
● Please do not use C++ standard template library.
○ Such as:
■ #include <queue>
■ #include <vector>
■ #include <stack>

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

○ Any submission using STL library will be disregarded.

File(s) you need to submit:

● [Link] (Do not change the filename!)

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

0. Basic instruction
Please refer to the instruction document, “DataStructure_PA_instructions.pdf”.

>> g++ -std=c++11 -o [Link] [Link] [Link]

1. Asymptotic analysis (1 pts)

a. Choose the time complexity of the following Fibonacci series.
b. Fibonacci series
- Input : An integer n>=1
- Output : The n-th fibonacci number, where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2), for
n>=2
int fibonacci(int n){
if (n<=1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
1. O(log(n))
2. O(n)
3. O(2^n)
4. O(n^2)

c. Example output : If you choose O(log(n)), then print 1

>> ./[Link] 1
[Task 1]
1

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

2. Asymptotic analysis (1 pts)

a. Choose the time complexity of the following binary search function.
b. Binary search
- Input : A sorted array arr of size n, and an integer x to search.
- Output : Returns the index of x if found, otherwise returns -1.
int binarySearch(int arr[], int n, int x) {
int low = 0, high = n-1;
while(low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] > x) high = mid - 1;
else low = mid + 1;
}
return -1;
}
1. O(1)
2. O(log(n))
3. O(n)
4. O(n^2)

c. Example output : If you choose O(1), then print 1

>> ./[Link] 2
[Task 2]
1

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

3. Linked List (3 pts)

a. Implement a function that can insert or delete an integer into a linked list. A user can
insert an element in ascending order or delete an element at a specific index. If the specified
index is out of range, print "ERROR".
b. Input & Output
Input : Sequence of commands, which is one of the following,
- (‘insert’, integer value): insert integer value at the appropriate position in the linked list,
ensuring that elements are always in ascending order.
- (‘delete’, index) : Delete the element at the given zero-based index.
- Array index indicates zero-based index.
Output :
- After inserting or deleting elements, the resulting linked list should be converted into a
space-separated string with no trailing spaces.
- “ERROR” if the index is out of range.

c. Example Input & Output

Input Output

[('insert',1), ('insert',4), ('insert',2), ('delete',1), ('insert',3),('insert',5), 1356

('delete',2), ('insert',6)]

[('delete',0)] ERROR

[('insert',3), ('delete',2)] ERROR

[('insert', 1), ('insert', 2), ('insert', 1), ('insert', 3), ('delete', 2)] 113

d. Example execution
>> ./[Link] 3 “[('insert',1), ('insert',4), ('insert',2), ('delete',1),
('insert',3),('insert',5), ('delete',2), ('insert',6)]”
[Task 3]
1356

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

4. Arithmetic Expression Evaluation / Stack (3 pts)

a. An arithmetic expression consists of single-digit positive integers (0-9) and the following
operators:
Addition (+), Subtraction (-), Multiplication (*), Division (/), and Parentheses (()).
The operators follow standard mathematical rules:
- Operation precedence: (1) Parentheses, (2) * and /, (3) + and –
- Operations with the same precedence are evaluated from left to right
Your task is to implement a stack-based calculator that correctly evaluates a given arithmetic
expression. You may choose any valid approach that utilizes a stack
- Implement a stack to assist in processing the arithmetic expression.
- Implement a function EvaluateExpression, which takes a string representing an
arithmetic expression and returns the calculated result as an integer

b. Input & Output

Input:
- A valid arithmetic expression represented as a string
- The expression contains only single-digit positive integers (0-9) and the following
operators: +, -, *, /, () .
- The input does not contain spaces and is guaranteed to be valid
- Division by zero will not occur in any test cases.
- Floating-point numbers and decimal results do not need to be considered (all operations
result in integers)
- The input expression has a maximum length of 100 characters
Output :
- Print the evaluated integer result of the given arithmetic expression.

c. Example Input & Output

Input Output

1+2+3 6

(3+2)*4 20

1*2*3 6

8/(4-2)+7*3 25

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

d. Example execution
>> ./[Link] 4 “1+2+3”
[Task 4]
6

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

5. Queue (3 pts)
a. Implement a function that shows the values in a queue based on a linked list, which
follows First-In First-Out order. We “enqueue(e)” values in the queue and “dequeue(d)” the
front value (first inserted value). If “d” operation is called for an empty queue, you should print
“EMPTY”.
- We set the max size of queue as 100 and we will not test over the maximum size. You do
not need exceptions for this situation.

b. Input & Output (integer value range: 1 to 231 − 1)

Input: Sequence of commands, which is one of the following,
- ('e',integer): enqueue integer into the current queue
- ('d',0): dequeue the front value from the current queue.
- ('p',0): print the front value
- ('s',0): show all values in queue (ex : value) in descending order (check the example
below). If empty, print nothing.
Output:
- Print the current state of the queue in order of priority when 's' is entered.
- Print the first value of the queue when 'p' is entered.
- print 'Empty' when 'd' command fails on empty queue.

c. Example input & output

Input Output

[('e',5), ('e',3), ('d',0), ('s', 0)] 3

[('e',5), ('e',3), ('p', 0)] 5

[('d',0), ('s', 0), ('d',0), ('p', 0)] EMPTY

EMPTY

[('e',5), ('e',3), ('e',8), ('e',11), ('s', 0), ('d',0), ('s', 0), ('p', 0)] 5
3
8
11
3
8

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

11
3

d. Example execution
>> ./[Link] 5 "[('e',5), ('e',3), ('d',0), ('s', 0)]"
[Task 5]
3

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

6. Circular Queue (3 pts)

a. Implement a function that shows the values in a circular queue with a counter. If “e” is
called for an already full queue or the “d” operation is called for an empty queue, there should
be no changes to the queue. The maximum number of elements (n) in the queue is five and we
limit the input as integer 1 to 99.

b. Input & Output

Input: Sequence of commands, which is one of the following.
- (‘e’, int): enqueue integer into the current queue
- (‘d’): dequeue from the current queue
- (‘show’): show the value of the current queue. If the queue is empty, print ‘EMPTY’
- (‘rotate’): rotate shifts the elements in the circular queue by one position. In this case
only the front element moves to the rear.
Output :
- Values in the circular queue (mod size n = 5), from the front to the rear. String separated
with the spacebar.
- No pointer movement if dequeue applied on an empty queue or enqueue applied on a
full queue or rotate applied on an empty queue.

c. Example input & output

Input Output

[('e',5), ('e', 1), ('e',3), ('d', NULL), ('d', NULL), ('show', NULL)] 3

[('e',5), ('e', 2), ('e',5), ('rotate', NULL), ('show', NULL)] 255

[('d', NULL), ('show', NULL), ('d', NULL), ('show', NULL)] EMPTY

EMPTY

[('e',5), ('e', 99), ('e',3), ('e', 4), ('e',8), ('e', 31), ('e',11), 5 99 3 4 8
('show', NULL), ('rotate', NULL), ('show', NULL)] 99 3 4 8 5

[('e',5), ('rotate', NULL), ('e',3), ('rotate', NULL), ('e',51), 3 5 51

('show', NULL)]

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

d. Example execution
>> ./[Link] 6 "[('e',5), ('e', 99), ('e',3), ('e', 4), ('e',8), ('e', 31), ('e',11), ('show',
NULL), ('rotate', NULL), ('show', NULL)]"
[Task 6]
5 99 3 4 8
99 3 4 8 5

-10-