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.
● Please write neatly when showing your work.
○ Hardly unrecognizable work might be marked as zero points.
● 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
● Do not modify auxiliary files
○ utils.h, utils.cpp, evaluate.cpp, and so on.
● 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]_assignment1.zip
● .zip file named (i.e. 20241234_assignment1.zip) containing:
○ pa1.cpp (do not change your filename!)
○ wa1.pdf (your 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 #1

Q1. (1pt)
Order the following functions by ascending asymptotic growth rate using big-Oh notation. Assume the base of given log function as 2. (1pt)
3log + 5 210 2 4 + 8log 5 + 32
3 + 42 3 2log log3 !

Q2. (Total 1pt, 0.5pt each)
1) Compute the time complexity of countVowels using big-O notation, given that the length of the input string str is n.
int countVowels(string str) { int result = 0;
string vowels = “aeiouAEIOU”;

for (int i = 0; i < str.length(); i++) { for (int j = 0; j < vowels.length(); j++) { if (str[i] == vowels[j]) { result++;
}
}
}
return result;
}

2) Compute the time complexity of triangularNumber using big-O notation.
int triangularNumber(int n) { int result = 0; int i = 1;
while (result < n) { result += i;
i++;
}
return result;
}
Q3. (Total 1pt, 0.5pt each)
You are given an array of n elements. All elements in an array are integers ranging from 0 to n-2. All elements are unique except for two; there are two elements with duplicate values. Your task is to identify the duplicate value in the array.
1) Compute the time complexity of findDuplicate using big-O notation.
int findDuplicate(int arr[], int n) { int result = -1;
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { result = arr[i]; break;
}
}
}
return result;
}

2) Compute the time complexity of findDuplicate2 using big-O notation.
int findDuplicate2(int arr[], int n) { int result = -1;
int* count = new int[n-1];
for (int i = 0; i < n; i++) { if (count[arr[i]] == 1) { result = arr[i]; break;
} else { count[arr[i]]++;
}
}
delete count;
return result;
}

Programming Assignment #1

Basic Instruction
Please refer to C++ Environment Setup Guide, which is on PLMS.
Use the command below to compile your code:
$ g++ -std=c++11 -o pa1 pa1.cpp utils.cpp

[Task 1] List (3pts)

Description
● Implement a function that can insert or delete an integer into the list.
● A user can:
○ Insert an element in ascending order
○ Delete an element from the list at the specific index
● If the specified index is out of range of the given list, print “ERROR”.
Input
● Sequence of commands, which is one of the following:
○ (‘insert’, integer value): insert integer value at the appropriate position in the list, ensuring that the elements within the array are always in ascending order.
○ (‘delete’, index): delete an element at the index in the list.
● Index indicates zero-based index.
Output
● After all sequence of commands are processed, the resulting string of list elements should have spaces between each element, but no space after the last element.
● “ERROR” should be printed if the deleting index is out of range.

Input Output
[(‘insert’,2), (‘insert’,1), (‘insert’,3)] 1 2 3
[(‘insert’,0), (‘insert’,0), (‘insert’,1)] 0 0 1
[(‘insert’,0), (‘insert’,1), (‘delete’,0)] 1
[(‘insert’,1), (‘delete’,1)] ERROR
[(‘delete’,0)] ERROR
[(‘insert’,5), (‘insert’,9), (‘delete’,0),
(‘insert’,1), (‘insert’,2)] 1 2 9
Example Usage
$ ./pa1 1 “[(‘insert’,2), (‘insert’,1), (‘insert’,3)]”

The file named “submit.txt” will be generated with the content below, or if already exists, the following output will be added at the end of the file:
[Task 1]
1 2 3

[Task 2] Postfix Expression Calculator / Stack (4pt)

Description
● Postfix expression is the expression of the form
○ [operand1] [operand2] [operator]
● c.f. Infix expression is the expression of the form
○ [operand1] [operator] [operand2]
● Implement an array-based stack and a function EvaluatePostfix.
● This function returns the string that contains the evaluated value of the given postfix expression, utilizing your implementation of stack.
Input
● A string of postfix expression. Input is given without space.
● The operators that need to be implemented is shown below:
○ ‘+’: addition
○ ‘-’: subtraction
○ ‘*’: multiplication
○ ‘/’: integer division
● The operands can be 1-digit integers between 0-9.
Output
● “ERROR” for the cases of:
○ The operator does not have enough number of available operands.
○ More than one value left after evaluation
● “DIVISIONBYZERO” for division by zero case
● Otherwise, the resulting Integer value of the expression
○ Use to_string(int value) to convert int to string
● You need not to handle the case of exceeding maximum stack capacity
More Specifications
● You should handle numbers next to each other in the input as separate values ○ 42 should be handled as 4 and 2, not the value 42.
● During the operations, you’ll also need to handle the values other than 1-digit numbers. ● You do not need to handle the case of exceeding maximum stack capacity.

Input Output
2 2
234+* 14
56*34*+ 42
68-* ERROR
71 ERROR
733-/ DIVISIONBYZERO
Example Usage
$ ./pa1 2 “56*34*+”

The file named “submit.txt” will be generated with the content below, or if already exists, the following output will be added at the end of the file:
[Task 2]
42

[Task 3] Round Robin / Circular Queue (5pt)

Description
● Round-robin (RR) is one of the CPU scheduling algorithms, where each process is allocated with equal share of CPU time. Processes are put into a circular queue, and when the allocated time expires, the process goes to the very back of the queue, allowing the next process to be processed by the CPU.
● For further knowledge, see the link below:
https://en.wikipedia.org/wiki/Round-robin_scheduling ● Implement RR algorithm utilizing circular queue.
● For the simplicity of the given task, you only need to handle the case where all processes arrive at the queue at the same arrival time.
Input
● Sequence of instructions, each containing process name and its burst time (total time required to complete the process)
○ (‘process_name’,t): enqueue the process named process_name with burst time t to the circular queue. Burst time t is assumed to be > 1.
Output
● Sequence of names of the processes handled at each time point (t = 0, 1, 2, 3, …) until the end of the execution. The names should be separated with a blank ‘ ’.
● See examples for better understanding. More Specifications
● You should assume that the time quantum = 1, which is the allocated time for a process to run in a preemptive manner.
○ The process should go back to the queue even if there’s still remaining execution time to be finished.
○ If the process finishes, then it is dequeued from the circular queue.
● Hint: Implement rotate() without using enqueue and dequeue, which is to be used in moving unfinished process to the back

Input Output
[(‘P0’,5), (‘P1’,3)] P0 P1 P0 P1 P0 P1 P0 P0
[(‘P0’,3)] P0 P0 P0
[(‘P0’,2), (‘P1’,1), (‘P2’,3)] P0 P1 P2 P0 P2 P2
Example Usage
$ ./pa1 3 “[(‘P0’,2), (‘P1’,1), (‘P2’,3)]”

The file named “submit.txt” will be generated with the content below, or if already exists, the following output will be added at the end of the file:
[Task 3]
P0 P1 P2 P0 P2 P2