**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****Evaluation policy: ● ■ 100% penalty is applied for that submission ● Your code will be automatically tested using an evaluation program ○ Each problem has the maximum score We won’t accept any submission via email ● – it will be ignored Please do not use the containers in C++ standard template library (STL) ● ○ Such as: ■ #include ■ #include ■ #include ○ Any submission using the containers in STL will be disregardedFile(s) you need to submit : pa2.cpp, tree.cpp, tree.h, heap.cpp, heap.h ( Do not change the filename! ● )Any questions? Please use PLMS – Q&A board.0. Basic instruction a. Please refer to the attached file named “DataStructure_PA_instructions.pdf”. 1. Quiz (2 pts) 1.1. Let T is a general tree, and T’ is a binary tree converted from T. Which of the following traversal visits the nodes in the same order as the inorder traversal of T’? (1) Preorder traversal of T (2) Inorder traversal of T (3) Postorder traversal of T (4) None of the aboves1. What is the time complexity of rearranging min-heap into a max-heap? (5) O(1) (6) O(log n) (7) O(n) (8) O(2^n)● Example execution – If you choose “(1) Preorder traversal of T” for 1-1., print your answer as shown below >> ./pa2.exe 1 1 [Task 1] 1– If you choose “(1) O(1)” for 1-2., print your answer as shown below >> ./pa2.exe 1 2 [Task 1] 1pre-2. Construct Binary TreeNote: pre-2 is not a problem that will be evaluated, but this is a short prerequisite to solve problems 2,3, and 4. Don’t worry. We are providing utility functions to help you.a. For problems 2, 3, and 4, you would need to implement member functions of BinaryTree class. To construct a BinaryTree class instance from an input, we use the string with bracket representation as input. The recursive definition of the bracket representation is as follows. Tree = Root(LeftChild)(RightChild). Below are some examples. The left tree is represented as 1(2)(3), and the right tree is 1(2()(4))(3()(5))b. To implement “a”, we provide a function to construct BinaryTree class from the bracket representation, which is BinaryTree::buildFromString function. It creates a pointer-based BinaryTree class instance from the given string. It would be helpful to read the implementation details of BinaryTree::buildFromStringc. To sum up, you will need to use BinaryTree class for problems 2, 3 and 4. Please try to understand the code for BinaryTree class.2. Traverse Binary Tree (2 pts)a. Implement BinaryTree::preOrder, BinaryTree::postOrder and BinaryTree:inOrder function that can traverse a binary tree with given traverse modeb. Input & Output Input: – String with bracket representation. – String representing traverse mode. Either “preorder”, “postorder” or “inorder” Output: – A sequence of node values acquired from the tree traversal. The value is separated with a white spacec. Example input & output Input Output “1(2)(3)” “preorder” 1 2 3 “1(2()(4))(3()(5))” “postorder” 4 2 5 3 1 “4(2(3)(1))(6(5))” “preorder” 4 2 3 1 6 5 “4(2(3)(1))(6(5))” “inorder” 3 2 1 4 5 6 “4(2(3)(1))(6(5))” “postorder” 3 1 2 5 6 4d. Example execution >> ./pa2.exe 2 “4(2(3)(1))(6(5))” “inorder” [Task 2] 3 2 1 4 5 63. Depth/Height of Binary Tree (3 pts)a. Implement BinaryTree::getDepthHeight function that can calculate the depth and height of a specific node in a given binary tree.b. Input & Output Input: – A given binary tree represented by string with bracket representation. – All node values in the tree are unique. – A specific node represented by integer value. Output: – Depth and height of the specific node in a given binary tree. – If the specific node doesn’t exist in the binary tree, return “error“.c. Example input & output Input Output “1(2)(3)” 2 1 0 “1(2(3(4)))(5)” 3 2 1 “1(2(3(4)))(5)” 6 errord. Example execution >> ./pa2.exe 3 “1(2(3(4)))(5)” 3 [Task 3] 2 14. Properness, Fullness, Completeness of Binary Tree (3 pts)a. Implement BinaryTree::isProper, BinaryTree::isFull, BinaryTree::isComplete function that can check whether if the given binary tree is a proper, full, complete binary tree or notb. Input & Output Input: – String with bracket representation – Specify what you want to check. Either “proper”, “full”, “complete” Output: – String “True” if the giben binary tree is a binary tree that matches the property, “False” otherwisec. Example input & output Input Output “1(2)(3)”, “proper” True “1(2(4)(5))(3(6))”, “proper” False “1(2)(3)”, “full” True “1(2(4)(5))(3()(7))”, “full” False “1(2)(3)”, “complete” True “1(2(4)(5))(3(6))”, “complete” True “1(2()(4))(3(6))”, “complete” Falsed. Example execution >> ./pa2.exe 4 “1(2(4)(5(6)(7))(3)”, “proper” [Task 4] True5. Min-heap Insertion (2 pts)Note: For solving problems 5 and 6, the similar utility functions provided in PA1 will be used to parse an input string. Therefore, you won’t need to try implementing a string parser. Please read pa2.cpp, and find the lines where your code would be located.a. Implement a function that inserts a new element to a binary min-heap. Your heap should maintain the min-heap property even after the insertion. Each test case will insert less than 100 valuesb. Input & Output Input: A sequence of commands – (‘insert’,integer): insert integer into the current min heap Output: – Values in a heap in a node number order, in a string separated with the white space (automatically printed with built-in function) – Do not consider the exceptional cases such as overflow, underflow or empty heap. We will not use the test cases for those scenarios.c. Example Input & Output Input Output [(‘insert’,5),(‘insert’,-3),(‘insert’,2)] -3 5 2 [(‘insert’,4),(‘insert’,-2),(‘insert’,9), (‘insert’,10),(‘insert’,15),(‘insert’,-25)] -25 4 -2 10 15 9 [(‘insert’,28),(‘insert’,9),(‘insert’,27), (‘insert’,10),(‘insert’,3),(‘insert’,45)] 3 9 27 28 10 45d. Example execution >> ./pa2.exe 5 “[(‘insert’,5),(‘insert’,3),(‘insert’,2)]” [Task 5] 2 5 36. Min-heap Deletion (3 pts)a. Implement a function that deletes the minimum value or the indexed value from the binary min-heap. Your heap should maintain the min heap property even after the deletion.b. Input & Output Input: A sequence of commands, which is one of the following – (‘insert’,integer): insert integer into the current min heap – (‘delMin’,NULL): delete minimum value from current binary min heap and rearrange heap to maintain the min heap property. – (‘delete’,index): delete the value indexed by the given index from current binary min heap and rearrange heap to maintain the min heap property. Output: – Values in a heap in a node number order, in a string separated with the white space (automatically printed with built-in function) – Do not consider the exceptional cases such as overflow, underflow or empty heap. We will not use the test cases for those scenarios.c. Example Input & Output Input Output [(‘insert’,5),(‘insert’,-3),(‘insert’,22), (‘delMin’,NULL)] 5 22 [(‘insert’,28),(‘insert’,9),(‘insert’,27), (‘insert’,10),(‘insert’,3),(‘insert’,45), (‘delMin’,NULL)] 9 10 27 28 45 [(‘insert’,28),(‘insert’,9),(‘insert’,27), (‘insert’,10),(‘insert’,3),(‘insert’,45), (‘delMin’,NULL),(‘insert’,22)] 9 10 22 28 45 27 [(‘insert’,3),(‘insert’,7),(‘insert’,6),(‘inser t’,25),(‘delMin’,NULL),(‘insert’,12),(‘delete’, 2),(‘insert’,-1),(‘delMin’,NULL)] 6 7 12d. Example execution >> ./pa2.exe 6 “[(‘insert’,4),(‘insert’,-2),(‘insert’,9), (‘insert’,10),(‘insert’,15),(‘insert’,-25),(‘delMin’,NULL)]” [Task 6] -2 4 9 10 15
0. Basic instruction Please refer to the instruction document, “DataStructure_PA_instructions.pdf”. >> g++ -std=c++11 -o pa1.exe pa1.cpp utils.cpp 1. Asymptotic analysis (1 pts) a. Choose the TIGHT bound of the following arraySum function. b. arraySum Input: An integer n >= 1, an array A storing n integers Output: Sum of the given array A1. O(1) 2. O(n) 3. O(n log (n)) 4. O(n^2) c. Example output: If you choose O(1), then print 12. Asymptotic analysis (1 pts) a. Choose the TIGHT bound of the following primeSearch function. b. primeSearch Input: An integer n >= 1 Output: The total number of prime numbers less than n1. O(log (n)) 2. O(n log (n)) 3. O( ) 4. O(n ) c. Example output: If you choose O(log (n)), then print 13. List (4 pts) a. Implement a function that can insert or delete an integer into the list. An user can insert or delete an element at the specific index. If the specified index is out of range of the given list, print “error”. b. Input & Output Input: Sequence of commands, which is one of the following, – (‘insert’, index): insert “# of elements in the current list” at the index in the list. index indicates zero-based index. – (‘delete’, index): delete an element at the index in the list. index indicates zero-based index. Output: – An array after insertion/deletion in a string separated with the spacebar – “error” if the index is out of range c. Example input & output Input Output [(‘insert’,0),(‘insert’,1),(‘insert’,2)] 0 1 2 [(‘insert’,0),(‘insert’,0),(‘insert’,1)] 1 2 0 [(‘insert’,0),(‘insert’,1),(‘delete’,0)] 1 [(‘insert’,0),(‘delete’,1)] error [(‘insert’,1)] error [(‘insert’,0),(‘insert’,1),(‘delete’,0), (‘insert’,1),(‘insert’,0)] 2 1 1 d. Example execution4. Stack (3 pts) a. Implement a function that prints the top values of the stack when “top” operation is called after the sequence of “push” or “pop” operations. If the “top” operation is called for an empty stack, print “-1”, If “pop” operation is called for an empty stack, print “error” b. Input & Output Input: Sequence of commands, which is one of the following, – (‘push’,integer): push integer into the current stack (integer is always positive) – (‘pop’,NULL): pop the top value of the current stack (this operation will print nothing) – (‘top’,NULL): print the top value of the current stack (print ‘-1’ if the current stack is empty) Output: – Expected printed values after processing the whole sequence, in a string separated with the spacebar – “error” if the pop operation is executed on an empty stack c. Example Input & Output Input Output [(‘push’,5),(‘push’,3),(‘top’,NULL)] 3 [(‘push’,3),(‘top’,NULL),(‘pop’,NULL), (‘push’,5),(‘top’,NULL)] 3 5 [(‘push’,5),(‘pop’,NULL),(‘top’,NULL)] -1 [(‘pop’,NULL)] error [(‘pop’,NULL),(‘push’,5),(‘top’,NULL)] error d. Example execution >> ./pa1.exe 4 “[(‘push’,3),(‘top’,NULL),(‘pop’,NULL), (‘push’,5),(‘top’,NULL)]” [Task 4] 3 5 5. Queue (3 pts) a. Implement a function that shows the value of a queue after a sequence of arbitrary queue operations. If the queue after the operations is empty, print “empty”. If “dequeue” operates on an empty queue, print “error”. b. Input & Output Input: Sequence of commands, which is one of the following, – (‘enqueue’,integer): enqueue integer into the current queue – (‘dequeue’,NULL): dequeue from the current queue Output: – Values in the queue from the front to the rear, in a string separated with the spacebar – “empty” if the queue is empty – “error” if the “dequeue” operation is executed on an empty queue c. Example Input & Output Input Output [(‘enqueue’,5),(‘enqueue’,3),(‘dequeue’,NUL L)] 3 [(‘enqueue’,5),(‘enqueue’,3),(‘dequeue’,NUL L),(‘enqueue’,5)] 3 5 [(‘enqueue’,3),(‘dequeue’,NULL)] empty [(‘enqueue’,5),(‘dequeue’,NULL),(‘dequeue’, NULL)] error d. Example execution6. Circular Queue (3 pts) a. Implement a function that shows the values in a circular queue with a counter. If “enqueue” is called for an already full queue or the “dequeue” 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 four. b. Input & Output Input: Sequence of commands, which is one of the following, – (‘enqueue’,integer): enqueue integer into the current queue – (‘dequeue’,NULL): dequeue from the current queue Output – Values in the circular queue (mod size n = 4), from the front to the rear. String separated with the spacebar, empty memory shows NULL – No pointer movement if dequeue applied on an empty queue or enqueue applied on a full queue c. Example input & output Input Output [(‘enqueue’,5),(‘enqueue’,3),(‘dequeue’,NULL)] 3 [(‘enqueue’,5),(‘enqueue’,3),(‘dequeue’,NULL), (‘enqueue’,6)] 3 6 [(‘enqueue’,3),(‘dequeue’,NULL)] [(‘enqueue’,5),(‘dequeue’,NULL),(‘enqueue’,3), (‘enqueue’,6),(‘enqueue’,9),(‘enqueue’,1), (‘dequeue’,NULL),(‘dequeue’,NULL), (‘enqueue’,7),(‘enqueue’,2)] 9 1 7 2 d. Example execution
Evaluation Policy: ■ 100% penalty will be applied for the submission and marked as zero. ● We do not accept any submission via email; they will be ignored. ● We do not accept any keyboard-typed submissions for the written assignment. ● 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. ○ Please describe your process of solving the problems 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. ○ 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 , , , 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: task_1.cpp task_2.cpp task_3.cpp ● .zip file named [your_student_id]_assignment4.zip (i.e. 20241234_assignment4.zip) containing: ○(do not change your filename!) ○(do not change your filename!) ○(do not change your filename!) ○ ds.h (optional) ○ wa4.pdf (your written assignment) If You Find Bugs in the Program: ● Please notify us as soon as possible Any other questions? Please use PLMS Q&A board in English.Written Assignment #4 Q1. Graph Representation (Total 3pt) Given a graph and its corresponding adjacency matrix or adjacency list representation, perform the following tasks. At each step, describe your reasoning and visually represent changes, if applicable. Q1.1. Convert Adjacency Matrix to Adjacency List (1pt) (1) Convert the adjacency matrix below into an adjacency list representation: (0.5pts) Adjacency Matrix: (Directed Graph) 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 (2) Then identify whether the graph is connected or contains disconnected components. Explain your findings. (0.5pts) Q1.2 Convert Adjacency List to Adjacency Matrix (2pt) (1) Convert the adjacency list below into an adjacency matrix representation: (0.5pts) Adjacency List: (Directed Graph) 1: [2, 3] 2: [4] 3: [5] 4: [6, 1] 5: [ ] 6: [3] (2) Draw a directed graph. (0.5pts) (3) Determine whether the graph is cyclic or acyclic. Justify your answer using the definition of cycles in directed graphs. (1pt) Q2. MST (Total 3pts) Q2.1 Convert Adjacency Matrix to Edge List (1pt) (1) Given the following adjacency matrix for an undirected weighted graph, convert it into an edge list representation. (1pt) 1 2 3 4 5 ————————– 1 | 0 2 0 6 0 2 | 2 0 3 8 5 3 | 0 3 0 0 7 4 | 6 8 0 0 9 5 | 0 5 7 9 0 (2) Apply Kruskal’s algorithm to find the Minimum Spanning Tree (MST) of the given graph. Clearly outline each step of the algorithm, explaining the selection of edges and the reasoning behind each decision. Present the MST in edge list representation and calculate the total weight of the MST. (2pts) Programming Assignment #4 Basic Instruction Please refer to C++ Environment Setup Guide, which is on PLMS. Make sure your code can be compiled using command below: $ g++ -std=c++11 -o task_1 task_1.cpp Please ensure your program correctly handles inputs and outputs using cin and cout from , adhering strictly to the format provided in the example. Note: You are not required to submit the output of your program. Example code: ex.cpp #include using namespace std; int main() { int A, B, C; cin >> A >> B >> C; // Do something with A, B, C cout
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****Evaluation Policy: – 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. ○ 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 , , , 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 usAny other questions? Please use PLMS Q&A board in English.Written Assignment #3Q1. (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 #3Basic 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 75 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),
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****EvaluaAon Policy: ■ 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 wriPen assignment ● We do not accept any . ● You can do your wriUen 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 MicrosoR 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 automa]cally tested using an evalua]on program. ○ Each problem has the maximum score. ○ Full points will be given only if all test cases are passed; there are no parAal points if only some por]on of the test cases work, and the others don’t. ○ Points will be deducted for any typos or incorrect formaVng ● 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 , , , or other container libraries ○ Any submission using such STL library will be disregarded. ○ Using only the given libraries will suffice. ○ , , , , “ds.h”Files You Need to Submit: [your_student_id]_assignment2.zip ● .zip file named (i.e. 20241234_assignment2.zip) containing: ○ task_1.cpp ○ task_2.cpp ○ task_3.cpp ○ ds.h ○ wa2.pdf (your wriUen assignment)as soon as possible If You Find Bugs in the Program: ● Please noAfy usAny other quesAons? Please use PLMS Q&A board in English.Wri.en Assignment #2Q1. (Total 2pt, 1pt each) Descrip)on Given the postorder and inorder sequences of a binary tree, reconstruct the tree and visually represent each step at the node level. At every step, show how the tree evolves as you insert nodes. If tree reconstruc]on is impossible for specific step, please stop drawing and write the reason.1) postorder: inorder: 2) postorder: inoder: Q2. (2pt) Descrip)on Given a tree represented by Tree[] and Label[] array, perform the following tasks: 1. Draw the corresponding tree structure. 2. Convert the tree into its LeS Child-Right Sibling (LC-RS) form and draw it. You can choose the order of the children freely, but ensure that the LC-RS representa]on accurately reflects the order of original tree structure you drew.Programming Assignment #2Basic Instruc@on Please refer to C++ Environment Setup Guide, which is on PLMS. Use the command below to compile your code: $ g++ -std=c++11 -o task_* task_*.cpp For example, you can command $ g++ -std=c++11 -o task_1 task_1.cpp [Task 0] Data Structure Implementa@on (0pts) In this assignment, you are encouraged to define all necessary data structures in a file named “ds.h”. For example, implement essen]al structures such as Queue and Stack in this file. These structures are shared across all tasks. For each task, create separate files (e.g., “task_*.cpp”) that include “ds.h” to solve the given problem. Although it is not for grading, it is highly recommended to improve your programming skills, code readability, and reusability. To simplify the compila]on process, make sure to include #include “ds.h” in all your task files.[Task 1] Construct Ternary Tree (4pts) Descrip)on Your task is to construct tree, especially ternary tree which has children up to three. The tree starts with root node (index 0), and you need to process a series of opera]ons to either add(ADD) or delete(DEL) nodes in the tree. Your task is to write a program that reads these opera]ons from an input file “input_1.txt”, processes them to construct the tree, and finally outputs the tree structure to an output file “output_1.txt”. Assume there is no duplicate index. The opera]ons consist of two types: ADD P C: Add node C as a child of node P (if P has at most two children). DEL X: Delete node X and all of its descendants from the tree. ● Implement a “task_1.cpp” that constructs tree according to input.Input ● N: the number of opera]on lines. (N is unsigned integer < 1,000) ● Opera]on 1~N: ADD P C or DEL X, (P, C, X are unsigned integer < 1,000) ○ e.g.) ADD 0 3: Add child 3 to the parent 0 ○ e.g.) DEL 5: Delete subtree which has node 5 as rootOutput The program should output each parent node index followed by its corresponding children indices. The parent indices must be in ascending order, and for each parent, the children indices should also be in ascending order. 1. No node is available for dele]on, 2. The parent node for adding children does not exist 3. There is no space to add more nodes the program should output “Error” in “output_1.txt” and then terminate.e.g.) input_1.txt output_1.txte.g.) input_1.txt output_1.txte.g.) input_1.txt output_1.txte.g.) input_1.txt output_1.txt[Task 2] Lowest Common Ancestor (LCA) (6pts) Descrip)on Given a mul]-ary tree (assume that they are always connected), we are finding the Lowest Common Ancestor (LCA) of two given nodes. The LCA of two nodes ! and ” in a tree is defined as the deepest node that is an ancestor of both ! and “. ● Implement a “task_2.cpp” that can find LCA of tree given.Input ● N: the number of input lines. (N is unsigned integer < 1,000) ● Line 1~N: the index of parent and its children. (unsigned integers, separated by space) ○ The leSmost value is the parent node index, and the remaining values are the indices of its children. ○ e.g.) 12 9 14 8: Parent index 12 has three children which have index 9, 14, and 8. ● ! and ” (unsigned integer < 1,000) ○ e.g.) 3 11: LCA of node 3 and 11 (note that ! and ” can be same) For example, if “input_2.txt” is given as:The corresponding tree can be visualized as:Output ● Implement a program that outputs the index of LCA for the tree from “input_2.txt”. ● For invalid input, such as when there is no node corresponding to either ! or “, the program should output “Error” in the “output_2.txt”. e.g.) input_2.txt output_2.txte.g.) input_2.txt output_2.txte.g.) input_2.txt output_2.txt[Task 3] Parsing and Evalua@ng Complex Nested Ternary Expressions Using Binary Trees (8pt) (recommend to use string header file) Descrip)on You are tasked with parsing and evalua]ng a nested ternary expression that refers to values from the array. The ternary expression will be provided in a single-line format. Your goal is to construct this nested expression as a binary tree, where each node contains a condi]on, and the children represent the True and False cases based on the Boolean outcome of the condi]on. Once the ternary expression is constructed as a binary tree, evaluate it by looking up the values referred in the array. You can assume that parentheses () are always given for grouping the case statements in all input. Ternary Expression Format: condi]on ? (true_case_statement) : (false_case_statement) Opera]ons used in this task are: [ ‘>’, ‘ 0 ? (2 > -1 ? (1) : (3)) : (-3) Output: 1Input ● N: the number of array values. (N is unsigned integer < 1,000) ● Line 1~N: array values from index 0 (signed integers) ● Nested Ternary Expression (string, length < 1,000) Output ● Implement a program that outputs the outcome of nested ternary expression from “input_3.txt”. ● For invalid input such as syntax error, output “Error”.For example, if “input_3.txt” is given as:Given N=6, the array contains 6 elements: [1, 2, -1, 3, 5, 2]. • i0 refers to the 0-th element: 1, • i3 refers to the 3-rd element: 3, • i4 refers to the 4-th element: 5, and so on. Then, parse Nested ternary expression line (recommend you to use string header file) i1 > 0 ? (i3 == -1 ? (i5) : (1 > 2 : (1) : (3))) : (i5 < 4 ? (i1) : (-1)) This expression can be represented as a binary tree, where each node represents a condi]on (leaf node for value) and branches lead to the True or False cases.Now, let’s solve it manually. The root node is a condi]on (i1 > 0). (Tip: right term can be referring value such as i2) Referring to the array, i1 is 2, so the condi]on becomes (2 > 0), which is True. Since this is True, we follow the leS branch to evaluate (i3 == -1). Referring to the array, i3 is 3, so the condi]on becomes (3 == -1), which is False. Since this is False, we follow the right branch to evaluate (1 > 2). (Tip: without “i” nota]on, it is assumed to be constant) Since (1 > 2) is False, we follow the right branch, which leads to a leaf node with the value 3. Result: The final output of the ternary expression is 3. e.g.) input_3.txt output_3.txt
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****Evaluation Policy: ■ 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. ○ 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 , , , 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 usAny other questions? Please use PLMS Q&A board in English.Written Assignment #1Q1. (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 #1Basic 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 backInput 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
Introduction The purpose of this assignment is to become more familiar with the concepts of process control and signalling. You’ll do this by writing a simple Unix shell program that supports job control. Logistics Only upload a single source code of your shell to LMS. Hand Out Instructions The procedure is similar to previous labs. You can obtain your file from: ˜/handout/shlab start by copying the file shlab-handout.tar to your home directory: cp ˜/handout/shlab/shlab-handout.tar ˜/ • Type the command tar -xvf shlab-handout.tar to expand the tarfile. • Type the command make to compile and link some test routines. • Type your name and POVIS ID in the header comment at the top of tsh.c. Looking at the tsh.c (tiny shell) file, you will see that it contains a functional skeleton of a simple Unix shell. To help you get started, we have already implemented the less interesting functions. Your assignment is to complete the remaining empty functions listed below. As a sanity check for you, we’ve listed the approximate number of lines of code for each of these functions in our reference solution (which includes lots of comments). • eval: Main routine that parses and interprets the command line. [70 lines] • builtincmd: Recognizes and interprets the built-in commands: quit, fg, bg, and jobs. [25 lines] • dobgfg: Implements the bg and fg built-in commands. [50 lines] • waitfg: Waits for a foreground job to complete. [20 lines] • sigchldhandler: Catches SIGCHILD signals. 80 lines] • siginthandler: Catches SIGINT (ctrl-c) signals. [15 lines] • sigtstphandler: Catches SIGTSTP (ctrl-z) signals. [15 lines] Each time you modify your tsh.c file, type make to recompile it. To run your shell, type tsh to the command line: unix> ./tsh tsh> [type commands to your shell here] General Overview of Unix Shells A shell is an interactive command-line interpreter that runs programs on behalf of the user. A shell repeatedly prints a prompt, waits for a command line on stdin, and then carries out some action, as directed by the contents of the command line. The command line is a sequence of ASCII text words delimited by whitespace. The first word in the command line is either the name of a built-in command or the pathname of an executable file. The remaining words are command-line arguments. If the first word is a built-in command, the shell immediately executes the command in the current process. Otherwise, the word is assumed to be the pathname of an executable program. In this case, the shell forks a child process, then loads and runs the program in the context of the child. The child processes created as a result of interpreting a single command line are known collectively as a job. In general, a job can consist of multiple child processes connected by Unix pipes. If the command line ends with an ampersand ”&”, then the job runs in the background, which means that the shell does not wait for the job to terminate before printing the prompt and awaiting the next command line. Otherwise, the job runs in the foreground, which means that the shell waits for the job to terminate before awaiting the next command line. Thus, at any point in time, at most one job can be running in the foreground. However, an arbitrary number of jobs can run in the background. For example, typing the command line tsh> jobs causes the shell to execute the built-in jobs command. Typing the command line tsh> /bin/ls -l -d runs the ls program in the foreground. By convention, the shell ensures that when the program begins executing its main routine int main(int argc, char *argv[]) the argc and argv arguments have the following values: • argc == 3, • argv[0] == ‘‘/bin/ls’’, • argv[1]== ‘‘-l’’, • argv[2]== ‘‘-d’’. Alternatively, typing the command line tsh> /bin/ls -l -d & runs the ls program in the background. Unix shells support the notion of job control, which allows users to move jobs back and forth between background and foreground, and to change the process state (running, stopped, or terminated) of the processes in a job. Typing ctrl-c causes a SIGINT signal to be delivered to each process in the foreground job. The default action for SIGINT is to terminate the process. Similarly, typing ctrl-z causes a SIGTSTP signal to be delivered to each process in the foreground job. The default action for SIGTSTP is to place a process in the stopped state, where it remains until it is awakened by the receipt of a SIGCONT signal. Unix shells also provide various built-in commands that support job control. For example: • jobs: List the running and stopped background jobs. • bg : Change a stopped background job to a running background job. • fg : Change a stopped or running background job to a running in the foreground. • kill : Terminate a job. The tsh Specification Your tsh shell should have the following features: • The prompt should be the string “tsh> ”. • The command line typed by the user should consist of a name and zero or more arguments, all separated by one or more spaces. If name is a built-in command, then tsh should handle it immediately and wait for the next command line. Otherwise, tsh should assume that name is the path of an executable file, which it loads and runs in the context of an initial child process (In this context, the term job refers to this initial child process). • tsh need not support pipes (|) or I/O redirection (< and >). • Typing ctrl-c (ctrl-z) should cause a SIGINT (SIGTSTP) signal to be sent to the current foreground job, as well as any descendents of that job (e.g., any child processes that it forked). If there is no foreground job, then the signal should have no effect. • If the command line ends with an ampersand &, then tsh should run the job in the background. Otherwise, it should run the job in the foreground. • tsh should support the following built-in commands: – The quit command terminates the shell. – The jobs command lists all background jobs. – The bg command restarts by sending it a SIGCONT signal, and then runs it in the background. The argument can be either a PID or a JID. – The fg command restarts by sending it a SIGCONT signal, and then runs it in the foreground. The argument can be either a PID or a JID. • tsh should reap all of its zombie children. If any job terminates because it receives a signal that it didn’t catch, then tsh should recognize this event and print a message with the job’s PID and a description of the offending signal. Checking Your Work We have provided some tools to help you check your work. Reference solution. The Linux executable tshref is the reference solution for the shell. Run this program to resolve any questions you have about how your shell should behave. Your shell should emit output that is identical to the reference solution (except for PIDs, of course, which change from run to run). Shell driver. The sdriver.plprogram executes a shell as a child process, sends it commands and signals as directed by a trace file, and captures and displays the output from the shell. Use the -h argument to find out the usage of sdriver.pl: unix> ./sdriver.pl -h Usage: sdriver.pl [-hv] -t -s -a Options: -h Print this message -v Be more verbose -t Trace file -s Shell program to test -a Shell arguments -g Generate output for autograder We have also provided 16 trace files (trace{01-16}.txt)that you will use in conjunction with the shell driver to test the correctness of your shell. The lower-numbered trace files do very simple tests, and the higher-numbered tests do more complicated tests. You can run the shell driver on your shell using trace file trace01.txt (for instance) by typing: unix> ./sdriver.pl -t trace01.txt -s ./tsh -a “-p” (the -a “-p” argument tells your shell not to emit a prompt), or unix> make test01 Similarly, to compare your result with the reference shell, you can run the trace driver on the reference shell by typing: unix> ./sdriver.pl -t trace01.txt -s ./tshref -a “-p” or unix> make rtest01 For your reference, tshref.out gives the output of the reference solution on all races. This might be more convenient for you than manually running the shell driver on all trace files. The neat thing about the trace files is that they generate the same output you would have gotten had you run your shell interactively (except for an initial comment that identifies the trace). For example: bass> make test15 ./sdriver.pl -t trace15.txt -s ./tsh -a “-p” # # trace15.txt – Putting it all together # tsh> ./bogus ./bogus: Command not found. tsh> ./myspin 10 Job (9721) terminated by signal 2 tsh> ./myspin 3 & [1] (9723) ./myspin 3 & tsh> ./myspin 4 & [2] (9725) ./myspin 4 & tsh> jobs [1] (9723) Running ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> fg %1 Job [1] (9723) stopped by signal 20 tsh> jobs [1] (9723) Stopped ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> bg %3 %3: No such job tsh> bg %1 [1] (9723) ./myspin 3 & tsh> jobs [1] (9723) Running ./myspin 3 & [2] (9725) Running ./myspin 4 & tsh> fg %1 tsh> quit bass> Hints • Read every word of Chapter 8 (Exceptional Control Flow) in your textbook. • Use the trace files to guide the development of your shell. Starting with trace01.txt, make sure that your shell produces the identical output as the reference shell. Then move on to trace file trace02.txt, and so on. • The waitpid, kill, fork, execve, setpgid, and sigprocmaskfunctions will come in very handy. The WUNTRACED and WNOHANG options to waitpid will also be useful. • When you implement your signal handlers, be sure to send SIGINT and SIGTSTP signals to the entire foreground process group, using ”-pid” instead of ”pid” in the argument to the kill function. The sdriver.pl program tests for this error. • One of the tricky parts of the assignment is deciding on the allocation of work between the waitfg and sigchldhandler functions. We recommend the following approach: – In waitfg, use a busy loop around the sleep function. – In sigchldhandler, use exactly one call to waitpid. While other solutions are possible, such as calling waitpidin both waitfgand sigchldhandler, these can be very confusing. It is simpler to do all reaping in the handler. • In eval, the parent must use sigprocmask to block SIGCHLD signals before it forks the child, and then unblock these signals, again using sigprocmask after it adds the child to the job list by calling addjob. Since children inherit the blocked vectors of their parents, the child must be sure to then unblock SIGCHLD signals before it execs the new program. The parent needs to block the SIGCHLD signals in this way in order to avoid the race condition where the child is reaped by sigchldhandler (and thus removed from the job list) before the parent calls addjob. • Programs such as more, less, vi, and emacs do strange things with the terminal settings. Don’t run these programs from your shell. Stick with simple text-based programs such as /bin/ls, /bin/ps, and /bin/echo. • When you run your shell from the standard Unix shell, your shell is running in the foreground processgroup. If your shell then creates a child process, by default that child will also be a member of the foreground process group. Since typing ctrl-c sends a SIGINT to every process in the foreground group, typing ctrl-c will send a SIGINT to your shell, as well as to every process that your shell created, which obviously isn’t correct. Here is the workaround: After the fork, but before the execve, the child process should call setpgid(0, 0), which puts the child in a new process group whose group ID is identical to the child’s PID. This ensures that there will be only one process, your shell, in the foreground process group. When you type ctrl-c, the shell should catch the resulting SIGINT and then forward it to the appropriate foreground job (or more precisely, the process group that contains the foreground job). Evaluation Your score will be computed out of a maximum of 90 points based on the following distribution: 80 Correctness: 16 trace files at 5 points each. 10 Style points. We expect you to have good comments (5 pts) and to check the return value of EVERY system call (5 pts). Your solution shell will be tested for correctness on a Linux machine, using the same shell driver and trace files that were included in your lab directory. Your shell should produce identical output on these traces as the reference shell, with only two exceptions: • The PIDs can (and will) be different. • The output of the /bin/ps commands in trace11.txt, trace12.txt, and trace13.txt will be different from run to run. However, the running states of any mysplit processes in the output of the /bin/ps command should be identical. Hand In Instructions • Make sure you have included your name and POVIS ID in the header comment of tsh.c. • To hand in your shell source code, first type: make handin This would copy your tsh code into a fila named “Your ID”-tsh.c • Then upload the “Your ID”-tsh.c file onto LMS. Good luck!
Table of Contents § GCC Optimization § Manual Optimization GCC § GCC provides some optimization options. • https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html • The optimization option tends to improve the performance / reduce the size of the binary. § We can enable the optimization options by using the –O{level} argument. • -O, -O1, -O2, -O3, -O0, -Os, -Ofast, … • level controls the optimization level. • Higher optimization level increases the compilation time. GCC Optimization Levels (1) -O0 (Default) • Reduces compilation time. • Makes debugging produce the expected results. -O1, -O • Consume more time and memory for compilation. • Reduces the code size and execution time. GCC Optimization Levels (2) -O2 • Performs nearly all supported optimizations. • Does not involve space-speed tradeoff. • Improve the performance with increased compilation time. • … -O3 • Turns on more optimization flags. • Does not guarantee better performance. GCC Optimization Levels (3) -Os • Removed the optimizations that increases code size from –O2. • Tunes for code size rather than execution speed. -Ofast • Included the optimizations which disregard strict standards compliance to –O3. -Og • Optimizes debugging experience. • Only for edit-compile-debug cycle. • Recommended when debugging the program instead of –O0. GCC Optimization Levels: SummaryGCC Optimization Flags Optimization level includes optimization flags. • https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html For example, -O1 uses the following flags:GCC Optimization Flags – Example -funroll-loops • Unrolls loops whose number of iterations can be determined at compile time or upon entry to the loop. • Turns on complete loop peeling, i.e., complete removal of loops with a small constant number of iterations. • The code size becomes larger.GCC Optimization – Example gcc –O1 –fno-defer-pop –o test test.c • Use optimization level –O1 and optimization flag –fno-defer-pop. • The further flags override the flags from the optimization level. • i.e., -O1 set –fdefer-pop as default. Manual Optimization We can optimize the program by ourself! • Remove redundant variables, reduce the number of function calls, exploit locality, … • Or write the ASM code manually! ASM Code in C (1) § We use __asm() or __asm__() function for inline assembler. § It can be used anywhere inside the C / C++ code. § We use inline ASM for: • Spot-optimizing speed-critical sections of code. • Making direct hardware access for device drivers. ASM Code in C (2) Assembler template is the literal string with assembler instructions. • We divide each line with the character . %n: register mapped to the n th argument. %, {, |, } should be used with %.ASM Code in C (3)1: GCC Optimization (1) We will test the following GCC optimization levels with the code loops.c. • -O1, -Os, -O2.1: GCC Optimization (2) § Use time command to see the compilation time. • ex) time gcc loops.c –O § Run the binary file generated with gcc and check the spent time. • ex) ./a.out 2: ASM Code in C § Fill in the blank parts of asm.c. • The program should results 105. § Hints • mov v1 v2 -> copy the value of v1 to v2. • add v1 v2 -> v2 = v1 + v2Quiz
1 Logistics This is an individual project. You must run this lab on a 64-bit x86-64 machine. If you have any question, feel free to ask on PLMS. 2 Overview This lab will help you understand the impact that cache memories can have on the performance of your C programs. The lab consists of two parts. In the first part you will write a small C program (about 200-300 lines) that simulates the behavior of a cache memory. In the second part, you will optimize a small matrix transpose function, with the goal of minimizing the number of cache misses. 3 Downloading the assignment Download the assignment materials cachelab-handout.tar posted on PLMS. Start by copying cachelab-handout.tar to a protected Linux directory in which you plan to do your work. Then give the command linux> tar xvf cachelab-handout.tar This will create a directory called cachelab-handout that contains a number of files. You will be modifying two files: csim.c and trans.c. To compile these files, type: 4 Description The lab has two parts. In Part A you will implement a cache simulator. In Part B you will write a matrix transpose function that is optimized for cache performance. 4.1 Reference Trace Files The traces subdirectory of the handout directory contains a collection of reference trace files that we will use to evaluate the correctness of the cache simulator you write in Part A. The trace files are generated by a Linux program called valgrind. For example, typing linux> valgrind –log-fd=1 –tool=lackey -v –trace-mem=yes ls -l on the command line runs the executable program “ls -l”, captures a trace of each of its memory accesses in the order they occur, and prints them on stdout. Valgrind memory traces have the following form: I 0400d7d4,8 M 0421c7f0,4 L 04f6b868,8 S 7ff0005c8,8 Each line denotes one or two memory accesses. The format of each line is [space]operation address,size The operation field denotes the type of memory access: “I” denotes an instruction load, “L” a data load, “S” a data store, and “M” a data modify (i.e., a data load followed by a data store). There is never a space before each “I”. There is always a space before each “M”, “L”, and “S”. The address field specifies a 64-bit hexadecimal memory address. The size field specifies the number of bytes accessed by the operation. 4.2 Part A: Writing a Cache Simulator In Part A you will write a cache simulator in csim.c that takes a valgrind memory trace as input, simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions. We have provided you with the binary executable of a reference cache simulator, called csim-ref, that simulates the behavior of a cache with arbitrary size and associativity on a valgrind trace file. It uses the LRU (least-recently used) replacement policy when choosing which cache line to evict. The reference simulator takes the following command-line arguments: Usage: ./csim-ref [-hv] -s -E -b -t • -h: Optional help flag that prints usage info • -v: Optional verbose flag that displays trace info • -s : Number of set index bits (S =2s is the number of sets) • -E : Associativity (number of lines per set) • -b : Number of block bits (B =2b is the block size) • -t : Name of the valgrind trace to replay The command-line arguments are based on the notation (s, E, and b) from page 597 of the CS:APP2e textbook. For example: linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace hits:4 misses:5 evictions:3 The same example in verbose mode: linux> ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace L 10,1 miss M 20,1 miss hit L 22,1 hit S 18,1 hit L 110,1 miss eviction L 210,1 miss eviction M 12,1 miss eviction hit hits:4 misses:5 evictions:3 Your job for Part A is to fill in the csim.c file so that it takes the same command line arguments and produces the identical output as the reference simulator. Notice that this file is almost completely empty. You’ll need to write it from scratch. Programming Rules for Part A • Include your student# and name in the header comment for csim.c. ex) /* 20170354 Seunghun Baek */ • Your csim.c file must compile without warnings in order to receive credit. • Your simulator must work correctly for arbitrary s, E, and b. This means that you will need to allocate storage for your simulator’s data structures using the malloc function. Type “man malloc” for information about this function. • To receive credit for Part A, you must call the function printSummary, with the total number of hits, misses, and evictions, at the end of your main function: printSummary(hit_count, miss_count, eviction_count); • For this this lab, you should assume that memory accesses are aligned properly, such that a singlememory access never crosses block boundaries. By making this assumption, you can ignore the request sizes in the valgrind traces. 4.3 Part B: Optimizing Matrix Transpose In Part B you will write a transpose function in trans.c that causes as few cache misses as possible. Let A denote a matrix, and Aij denote the component on the ith row and jth column. The transpose of A, denoted AT, is a matrix such that Aij = ATji. To help you get started, we have given you an example transpose function in trans.c that computes the transpose of N × M matrix A and stores the results in M × N matrix B: char trans_desc[] = “Simple row-wise scan transpose”; void trans(int M, int N, int A[N][M], int B[M][N]) The example transpose function is correct, but it is inefficient because the access pattern results in relatively many cache misses. Your job in Part B is to write a similar function, called transpose_submit, that minimizes the number of cache misses across different sized matrices: char transpose_submit_desc[] = “Transpose submission”; void transpose_submit(int M, int N, int A[N][M], int B[M][N]); Do not change the description string (“Transpose submission”) for your transpose_submit function. The autograder searches for this string to determine which transpose function to evaluate for credit. Programming Rules for Part B • Include your student# and name in the header comment for trans.c. ex) /* 20170354 Seunghun Baek */ • Your code in trans.c must compile without warnings to receive credit. • You are allowed to define at most 12 local variables of type int per transpose function. • You are not allowed to side-step the previous rule by using any variables of type long or by using any bit tricks to store more than one value to a single variable. • You are NOT allowed to define any arrays in your code or to use any variant of malloc. 5 Evaluation This section describes how your work will be evaluated. The full score for this lab is 53 points: • Part A: 27 Points • Part B: 26 Points 5.1 Evaluation for Part A For Part A, we will run your cache simulator using different cache parameters and traces. There are eight test cases, each worth 3 points, except for the last case, which is worth 6 points: linux> ./csim -s 1 -E 1 -b 1 -t traces/yi2.trace linux> ./csim -s 4 -E 2 -b 4 -t traces/yi.trace linux> ./csim -s 2 -E 1 -b 4 -t traces/dave.trace linux> ./csim -s 2 -E 1 -b 3 -t traces/trans.trace linux> ./csim -s 2 -E 2 -b 3 -t traces/trans.trace linux> ./csim -s 2 -E 4 -b 3 -t traces/trans.trace linux> ./csim -s 5 -E 1 -b 5 -t traces/trans.trace linux> ./csim -s 5 -E 1 -b 5 -t traces/long.trace You can use the reference simulator csim-ref to obtain the correct answer for each of these test cases. During debugging, use the -v option for a detailed record of each hit and miss. For each test case, outputting the correct number of cache hits, misses and evictions will give you full credit for that test case. Each of your reported number of hits, misses and evictions is worth 1/3 of the credit for that test case. That is, if a particular test case is worth 3 points, and your simulator outputs the correct number of hits and misses, but reports the wrong number of evictions, then you will earn 2 points. 5.2 Evaluation for Part B For Part B, we will evaluate the correctness and performance of your transpose_submit function on three different-sized output matrices: • 32×32 (M =32, N =32) • 64×64 (M =64, N =64) • 61×67 (M =61, N =67) 5.2.1 Performance (26 pts) For each matrix size, the performance of your transpose_submit function is evaluated by using valgrind to extract the address trace for your function, and then using the reference simulator to replay this trace on a cache with parameters (s =5, E =1, b =5). Your performance score for each matrix size scales linearly with the number of misses, m, up to some threshold: • 32×32: 8 points if m < 300, 0 points if m > 600 • 64×64: 8 points if m < 1,300, 0 points if m > 2,000 • 61×67: 10 points if m < 2,000, 0 points if m > 3,000 Your code must be correct to receive any performance points for a particular size. Your code only needs to be correct for these three cases and you can optimize it specifically for these three cases. In particular, it is perfectly OK for your function to explicitly check for the input sizes and implement separate code optimized for each case. 6 Working on the Lab 6.1 Working on Part A We have provided you with an autograding program, called test-csim, that tests the correctness of your cache simulator on the reference traces. Be sure to compile your simulator before running the test: linux> make linux> ./test-csim Your simulator Reference simulator Points (s,E,b) Hits Misses Evicts Hits Misses Evicts 3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace 3 (4,2,4) 4 5 2 4 5 2 traces/yi.trace 3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace 3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace 3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace 3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace 3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace 6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace 27 For each test, it shows the number of points you earned, the cache parameters, the input trace file, and a comparison of the results from your simulator and the reference simulator. Here are some hints and suggestions for working on Part A: • Do your initial debugging on the small traces, such as traces/dave.trace. • The reference simulator takes an optional -v argument that enables verbose output, displaying the hits, misses, and evictions that occur as a result of each memory access. You are not required to implement this feature in your csim.c code, but we strongly recommend that you do so. It will help you debug by allowing you to directly compare the behavior of your simulator with the reference simulator on the reference trace files. • We recommend that you use the getopt function to parse your command line arguments. You’ll need the following header files: #include #include #include See “man 3 getopt” for details. • Each data load (L) or store (S) operation can cause at most one cache miss. The data modify operation(M) is treated as a load followed by a store to the same address. Thus, an M operation can result in two cache hits, or a miss and a hit plus a possible eviction. 6.2 Working on Part B We have provided you with an autograding program, called test-trans.c, that tests the correctness and performance of each of the transpose functions that you have registered with the autograder. You can register up to 100 versions of the transpose function in your trans.c file. Each transpose version has the following form: /* Header comment */ char trans_simple_desc[] = “A simple transpose”; void trans_simple(int M, int N, int A[N][M], int B[M][N]) { /* your transpose code here */ } Register a particular transpose function with the autograder by making a call of the form: registerTransFunction(trans_simple, trans_simple_desc); in the registerFunctions routine in trans.c. At runtime, the autograder will evaluate each registered transpose function and print the results. Of course, one of the registered functions must be the transpose_submit function that you are submitting for credit: registerTransFunction(transpose_submit, transpose_submit_desc); See the default trans.c function for an example of how this works. The autograder takes the matrix size as input. It uses valgrind to generate a trace of each registered transpose function. It then evaluates each trace by running the reference simulator on a cache with parameters (s =5, E =1, b =5). For example, to test your registered transpose functions on a 32×32 matrix, rebuild test-trans, and then run it with the appropriate values for M and N: linux> make linux> ./test-trans -M 32 -N 32 Step 1: Evaluating registered transpose funcs for correctness: func 0 (Transpose submission): correctness: 1 func 1 (Simple row-wise scan transpose): correctness: 1 func 2 (column-wise scan transpose): correctness: 1 func 3 (using a zig-zag access pattern): correctness: 1 Step 2: Generating memory traces for registered transpose funcs. Step 3: Evaluating performance of registered transpose funcs (s=5, E=1, b=5) func 0 (Transpose submission): hits:1766, misses:287, evictions:255 func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151 func 2 (column-wise scan transpose): hits:870, misses:1183, evictions:1151 func 3 (using a zig-zag access pattern): hits:1076, misses:977, evictions:945 Summary for official submission (func 0): correctness=1 misses=287 In this example, we have registered four different transpose functions in trans.c. The test-trans program tests each of the registered functions, displays the results for each, and extracts the results for the official submission. Here are some hints and suggestions for working on Part B. • The test-trans program saves the trace for function i in file trace.fi. These trace files are invaluable debugging tools that can help you understand exactly where the hits and misses for each transpose function are coming from. To debug a particular function, simply run its trace through the reference simulator with the verbose option: linux> ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 S 68312c,1 miss L 683140,8 miss L 683124,4 hit L 683120,4 hit L 603124,4 miss eviction S 6431a0,4 miss … • Since your transpose function is being evaluated on a direct-mapped cache, conflict misses are apotential problem. Think about the potential for conflict misses in your code, especially along the diagonal. Try to think of access patterns that will decrease the number of these conflict misses. • Blocking is a useful technique for reducing cache misses. See http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf for more information. 6.3 Putting it all Together To run the driver, type: linux> python2 driver.py 7 Handing in Your Work Each time you type make in the cachelab-handout directory, the Makefile creates a tarball, called userid-handin.tar, that contains your current csim.c and trans.c files. Please change the name of userid-handin.tar file as student#.tar. ex) 20170354.tar IMPORTANT: Do not create the handin tarball on a Windows or Mac machine, and do not handin files in any other archive format, such as .zip, .gzip, or .tgz files.
1 Introduction This assignment involves generating a total of five attacks on two programs having different security vulnerabilities. Outcomes you will gain from this lab include: • You will learn different ways that attackers can exploit security vulnerabilities when programs do notsafeguard themselves well enough against buffer overflows. • Through this, you will get a better understanding of how to write programs that are more secure, aswell as some of the features provided by compilers and operating systems to make programs less vulnerable. • You will gain a deeper understanding of the stack and parameter-passing mechanisms of x86-64machine code. • You will gain a deeper understanding of how x86-64 instructions are encoded. • You will gain more experience with debugging tools such as GDB and OBJDUMP. Note: In this lab, you will gain firsthand experience with methods used to exploit security weaknesses in operating systems and network servers. Our purpose is to help you learn about the runtime operation of programs and to understand the nature of these security weaknesses so that you can avoid them when you write system code. We do not condone the use of any other form of attack to gain unauthorized access to any system resources. You will want to study Sections 3.10.3 and 3.10.4 of the CS:APP3e book as reference material for this lab. 2 Logistics As usual, this is an individual project. You will generate attacks for target programs that are custom generated for you. 2.1 Getting Files You can obtain your files by pointing your Web browser at: http://127.0.0.1:15513/ The server will build your files and return them to your browser in a tar file called targetk.tar, where k is the unique number of your target programs. Note: It takes a few seconds to build and download your target, so please be patient. Save the targetk.tar file in a (protected) Linux directory in which you plan to do your work. Then give the command: tar -xvf targetk.tar. This will extract a directory targetk containing the files described below. You should only download one set of files. If for some reason you download multiple targets, choose one target to work on and delete the rest. The files in targetk include: README.txt: A file describing the contents of the directory ctarget: An executable program vulnerable to code-injection attacks rtarget: An executable program vulnerable to return-oriented-programming attacks cookie.txt: An 8-digit hex code that you will use as a unique identifier in your attacks. farm.c: The source code of your target’s “gadget farm,” which you will use in generating return-oriented programming attacks. hex2raw: A utility to generate attack strings. In the following instructions, we will assume that you have copied the files to a protected local directory, and that you are executing the programs in that local directory. 2.2 Important Points Here is a summary of some important rules regarding valid solutions for this lab. These points will not make much sense when you read this document for the first time. They are presented here as a central reference of rules once you get started. • You must do the assignment on a machine that is similar to the one that generated your targets. – The addresses for functions touch1, touch2, or touch3. – The address of your injected code – The address of one of your gadgets from the gadget farm. 3 Target Programs Both CTARGET and RTARGET read strings from standard input. They do so with the function getbuf defined below: 1 unsigned getbuf() 2 { 3 char buf[BUFFER_SIZE]; 4 Gets(buf); 5 return 1; 6 } The function Gets is similar to the standard library function gets—it reads a string from standard input (terminated by ‘ ’ or end-of-file) and stores it (along with a null terminator) at the specified destination. In this code, you can see that the destination is an array buf, declared as having BUFFER_SIZE bytes. At the time your targets were generated, BUFFER_SIZE was a compile-time constant specific to your version of the programs. Functions Gets() and gets() have no way to determine whether their destination buffers are large enough to store the string they read. They simply copy sequences of bytes, possibly overrunning the bounds of the storage allocated at the destinations. If the string typed by the user and read by getbuf is sufficiently short, it is clear that getbuf will return 1, as shown by the following execution examples: unix> ./ctarget Cookie: 0x1a7dd803 Type string: Keep it short! No exploit. Getbuf returned 0x1 Normal return Typically an error occurs if you type a long string: unix> ./ctarget Cookie: 0x1a7dd803 Type string: This is not a very interesting string, but it has the property … Ouch!: You caused a segmentation fault! Better luck next time (Note that the value of the cookie shown will differ from yours.) Program RTARGET will have the same behavior. As the error message indicates, overrunning the buffer typically causes the program state to be corrupted, leading to a memory access error. Your task is to be more clever with the strings you feed CTARGET and RTARGET so that they do more interesting things. These are called exploit strings. Both CTARGET and RTARGET take several different command line arguments: -h: Print list of possible command line arguments -q: Don’t send results to the grading server -i FILE: Supply input from a file, rather than from standard input Your exploit strings will typically contain byte values that do not correspond to the ASCII values for printing characters. The program HEX2RAW will enable you to generate these raw strings. See Appendix A for more information on how to use HEX2RAW. Important points: • Your exploit string must not contain byte value 0x0a at any intermediate position, since this is the ASCII code for newline (‘ ’). When Gets encounters this byte, it will assume you intended to terminate the string. • HEX2RAW expects two-digit hex values separated by one or more white spaces. So if you want to create a byte with a hex value of 0, you need to write it as 00. To create the word 0xdeadbeef you should pass “ef be ad de” to HEX2RAW (note the reversal required for little-endian byte ordering). When you have correctly solved one of the levels, your target program will automatically send a notification to the grading server. For example: unix> ./hex2raw < ctarget.l2.txt | ./ctarget Cookie: 0x1a7dd803 Type string:Touch2!: You called touch2(0x1a7dd803) Valid solution for level 2 with target ctarget PASSED: Sent exploit string to server to be validated. NICE JOB! The server will test your exploit string to make sure it really works, and it will update the Attacklab scoreboard page indicating that your userid (listed by your target number for anonymity) has completed this phase. You can view the scoreboard by pointing your Web browser at http://127.0.0.1:15513/scoreboard Unlike the Bomb Lab, there is no penalty for making mistakes in this lab. Feel free to fire away at CTARGET and RTARGET with any strings you like. Phase Program Level Method Function Points 1 CTARGET 1 CI touch1 10 2 CTARGET 2 CI touch2 25 3 CTARGET 3 CI touch3 25 4 RTARGET 2 ROP touch2 35 5 RTARGET 3 ROP touch3 5 CI: Code injection ROP: Return-oriented programming Figure 1: Summary of attack lab phases IMPORTANT NOTE: You can work on your solution on any Linux machine, but in order to submit your solution, you will need to be running on one of the following machines: Figure 1 summarizes the five phases of the lab. As can be seen, the first three involve code-injection (CI) attacks on CTARGET, while the last two involve return-oriented-programming (ROP) attacks on RTARGET. 4 Part I: Code Injection Attacks For the first three phases, your exploit strings will attack CTARGET. This program is set up in a way that the stack positions will be consistent from one run to the next and so that data on the stack can be treated as executable code. These features make the program vulnerable to attacks where the exploit strings contain the byte encodings of executable code. 4.1 Level 1 For Phase 1, you will not inject new code. Instead, your exploit string will redirect the program to execute an existing procedure. Function getbuf is called within CTARGET by a function test having the following C code: 1 void test() 2 { 3 int val; 4 val = getbuf(); 5 printf(“No exploit. Getbuf returned 0x%x “, val); 6 } When getbuf executes its return statement (line 5 of getbuf), the program ordinarily resumes execution within function test (at line 5 of this function). We want to change this behavior. Within the file ctarget, there is code for a function touch1 having the following C representation: 1 void touch1() 2 { 3 vlevel = 1; /* Part of validation protocol */ 4 printf(“Touch1!: You called touch1() “); 5 validate(1); 6 exit(0); 7 } Some Advice: • All the information you need to devise your exploit string for this level can be determined by exam-ining a disassembled version of CTARGET. Use objdump -d to get this dissembled version. • The idea is to position a byte representation of the starting address for touch1 so that the ret instruction at the end of the code for getbuf will transfer control to touch1. • Be careful about byte ordering. • You might want to use GDB to step the program through the last few instructions of getbuf to make sure it is doing the right thing. • The placement of buf within the stack frame for getbuf depends on the value of compile-time constant BUFFER_SIZE, as well the allocation strategy used by GCC. You will need to examine the disassembled code to determine its position. 4.2 Level 2 Phase 2 involves injecting a small amount of code as part of your exploit string. Within the file ctarget there is code for a function touch2 having the following C representation: 1 void touch2(unsigned val) 2 { 3 vlevel = 2; /* Part of validation protocol */ 4 if (val == cookie) { 5 printf(“Touch2!: You called touch2(0x%.8x) “, val); 6 validate(2); 7 } else { 8 printf(“Misfire: You called touch2(0x%.8x) “, val); 9 fail(2); 10 } 11 exit(0); 12 } Your task is to get CTARGET to execute the code for touch2 rather than returning to test. In this case, however, you must make it appear to touch2 as if you have passed your cookie as its argument. Some Advice: • You will want to position a byte representation of the address of your injected code in such a way thatret instruction at the end of the code for getbuf will transfer control to it. • Recall that the first argument to a function is passed in register %rdi. • Your injected code should set the register to your cookie, and then use a ret instruction to transfer control to the first instruction in touch2. • Do not attempt to use jmp or call instructions in your exploit code. The encodings of destination addresses for these instructions are difficult to formulate. Use ret instructions for all transfers of control, even when you are not returning from a call. • See the discussion in Appendix B on how to use tools to generate the byte-level representations ofinstruction sequences. 4.3 Level 3 Phase 3 also involves a code injection attack, but passing a string as argument. Within the file ctarget there is code for functions hexmatch and touch3 having the following C representations: 1 /* Compare string to hex represention of unsigned value */ 2 int hexmatch(unsigned val, char *sval) 3 { 4 char cbuf[110]; 5 /* Make position of check string unpredictable */ 6 char *s = cbuf + random() % 100; 7 sprintf(s, “%.8x”, val); 8 return strncmp(sval, s, 9) == 0; 9 } 10 11 void touch3(char *sval) 12 { 13 vlevel = 3; /* Part of validation protocol */ 14 if (hexmatch(cookie, sval)) { 15 printf(“Touch3!: You called touch3(“%s”) “, sval); 16 validate(3); 17 } else { 18 printf(“Misfire: You called touch3(“%s”) “, sval); 19 fail(3); 20 } 21 exit(0); 22 }Figure 2: Setting up sequence of gadgets for execution. Byte value 0xc3 encodes the ret instruction. Your task is to get CTARGET to execute the code for touch3 rather than returning to test. You must make it appear to touch3 as if you have passed a string representation of your cookie as its argument. Some Advice: • You will need to include a string representation of your cookie in your exploit string. The string shouldconsist of the eight hexadecimal digits (ordered from most to least significant) without a leading “0x.” • Recall that a string is represented in C as a sequence of bytes followed by a byte with value 0. Type“man ascii” on any Linux machine to see the byte representations of the characters you need. • Your injected code should set register %rdi to the address of this string. • When functions hexmatch and strncmp are called, they push data onto the stack, overwriting portions of memory that held the buffer used by getbuf. As a result, you will need to be careful where you place the string representation of your cookie. 5 Part II: Return-Oriented Programming Performing code-injection attacks on program RTARGET is much more difficult than it is for CTARGET, because it uses two techniques to thwart such attacks: • It uses randomization so that the stack positions differ from one run to another. This makes it impos-sible to determine where your injected code will be located. Fortunately, clever people have devised strategies for getting useful things done in a program by executing existing code, rather than injecting new code. The most general form of this is referred to as return-oriented programming (ROP) [1, 2]. The strategy with ROP is to identify byte sequences within an existing program that consist of one or more instructions followed by the instruction ret. Such a segment is referred to as a gadget. Figure 2 illustrates how the stack can be set up to execute a sequence of n gadgets. In this figure, the stack contains a sequence of gadget addresses. Each gadget consists of a series of instruction bytes, with the final one being 0xc3, encoding the ret instruction. When the program executes a ret instruction starting with this configuration, it will initiate a chain of gadget executions, with the ret instruction at the end of each gadget causing the program to jump to the beginning of the next. For example, one version of rtarget contains code generated for the following C function: void setval_210(unsigned *p) { *p = 3347663060U; } The chances of this function being useful for attacking a system seem pretty slim. But, the disassembled machine code for this function shows an interesting byte sequence: 0000000000400f15 : 400f15: c7 07 d4 48 89 c7 movl $0xc78948d4,(%rdi) 400f1b: c3 retq The byte sequence 48 89 c7 encodes the instruction movq %rax, %rdi. (See Figure 3A for the encodings of useful movq instructions.) This sequence is followed by byte value c3, which encodes the ret instruction. The function starts at address 0x400f15, and the sequence starts on the fourth byte of the function. Thus, this code contains a gadget, having a starting address of 0x400f18, that will copy the 64-bit value in register %rax to register %rdi. Your code for RTARGET contains a number of functions similar to the setval_210 function shown above in a region we refer to as the gadget farm. Your job will be to identify useful gadgets in the gadget farm and use these to perform attacks similar to those you did in Phases 2 and 3. Important: The gadget farm is demarcated by functions start_farm and end_farm in your copy of rtarget. Do not attempt to construct gadgets from other portions of the program code. 5.1 Level 2 For Phase 4, you will repeat the attack of Phase 2, but do so on program RTARGET using gadgets from your gadget farm. You can construct your solution using gadgets consisting of the following instruction types, and using only the first eight x86-64 registers (%rax–%rdi). A. Encodings of movq instructions movq S, D Source S Destination D %rax %rcx %rdx %rbx %rsp %rbp %rsi %rdi %rax 48 89 c0 48 89 c1 48 89 c2 48 89 c3 48 89 c4 48 89 c5 48 89 c6 48 89 c7 %rcx 48 89 c8 48 89 c9 48 89 ca 48 89 cb 48 89 cc 48 89 cd 48 89 ce 48 89 cf %rdx 48 89 d0 48 89 d1 48 89 d2 48 89 d3 48 89 d4 48 89 d5 48 89 d6 48 89 d7 %rbx 48 89 d8 48 89 d9 48 89 da 48 89 db 48 89 dc 48 89 dd 48 89 de 48 89 df %rsp 48 89 e0 48 89 e1 48 89 e2 48 89 e3 48 89 e4 48 89 e5 48 89 e6 48 89 e7 %rbp 48 89 e8 48 89 e9 48 89 ea 48 89 eb 48 89 ec 48 89 ed 48 89 ee 48 89 ef %rsi 48 89 f0 48 89 f1 48 89 f2 48 89 f3 48 89 f4 48 89 f5 48 89 f6 48 89 f7 %rdi 48 89 f8 48 89 f9 48 89 fa 48 89 fb 48 89 fc 48 89 fd 48 89 fe 48 89 ff B. Encodings of popq instructions Operation Register R %rax %rcx %rdx %rbx %rsp %rbp %rsi %rdi popq R 58 59 5a 5b 5c 5d 5e 5f C. Encodings of movl instructions movl S, D Source S Destination D %eax %ecx %edx %ebx %esp %ebp %esi %edi %eax 89 c0 89 c1 89 c2 89 c3 89 c4 89 c5 89 c6 89 c7 %ecx 89 c8 89 c9 89 ca 89 cb 89 cc 89 cd 89 ce 89 cf %edx 89 d0 89 d1 89 d2 89 d3 89 d4 89 d5 89 d6 89 d7 %ebx 89 d8 89 d9 89 da 89 db 89 dc 89 dd 89 de 89 df %esp 89 e0 89 e1 89 e2 89 e3 89 e4 89 e5 89 e6 89 e7 %ebp 89 e8 89 e9 89 ea 89 eb 89 ec 89 ed 89 ee 89 ef %esi 89 f0 89 f1 89 f2 89 f3 89 f4 89 f5 89 f6 89 f7 %edi 89 f8 89 f9 89 fa 89 fb 89 fc 89 fd 89 fe 89 ff D. Encodings of 2-byte functional nop instructions Operat ion Register R %al %cl %dl %bl andb R, R 20 c0 20 c9 20 d2 20 db orb R, R 08 c0 08 c9 08 d2 08 db cmpb R, R 38 c0 38 c9 38 d2 38 db testb R, R 84 c0 84 c9 84 d2 84 db Figure 3: Byte encodings of instructions. All values are shown in hexadecimal. movq : The codes for these are shown in Figure 3A. popq : The codes for these are shown in Figure 3B. ret : This instruction is encoded by the single byte 0xc3. nop : This instruction (pronounced “no op,” which is short for “no operation”) is encoded by the single byte 0x90. Its only effect is to cause the program counter to be incremented by 1. Some Advice: • All the gadgets you need can be found in the region of the code for rtarget demarcated by the functions start_farm and mid_farm. • You can do this attack with just two gadgets. • When a gadget uses a popq instruction, it will pop data from the stack. As a result, your exploit string will contain a combination of gadget addresses and data. 5.2 Level 3 Before you take on the Phase 5, pause to consider what you have accomplished so far. In Phases 2 and 3, you caused a program to execute machine code of your own design. If CTARGET had been a network server, you could have injected your own code into a distant machine. In Phase 4, you circumvented two of the main devices modern systems use to thwart buffer overflow attacks. Although you did not inject your own code, you were able inject a type of program that operates by stitching together sequences of existing code. You have also gotten 95/100 points for the lab. That’s a good score. If you have other pressing obligations consider stopping right now. To solve Phase 5, you can use gadgets in the region of the code in rtarget demarcated by functions start_farm and end_farm. In addition to the gadgets used in Phase 4, this expanded farm includes the encodings of different movl instructions, as shown in Figure 3C. The byte sequences in this part of the farm also contain 2-byte instructions that serve as functional nops, i.e., they do not change any register or memory values. These include instructions, shown in Figure 3D, such as andb %al,%al, that operate on the low-order bytes of some of the registers but do not change their values. Some Advice: • You’ll want to review the effect a movl instruction has on the upper 4 bytes of a register, as is described on page 183 of the text. • The official solution requires eight gadgets (not all of which are unique). Good luck and have fun! A Using HEX2RAW HEX2RAW takes as input a hex-formatted string. In this format, each byte value is represented by two hex digits. For example, the string “012345” could be entered in hex format as “30 31 32 33 34 35 00.” (Recall that the ASCII code for decimal digit x is 0x3x, and that the end of a string is indicated by a null byte.) The hex characters you pass to HEX2RAW should be separated by whitespace (blanks or newlines). We recommend separating different parts of your exploit string with newlines while you’re working on it. HEX2RAW supports C-style block comments, so you can mark off sections of your exploit string. For example: 48 c7 c1 f0 11 40 00 /* mov $0x40011f0,%rcx */ Be sure to leave space around both the starting and ending comment strings (“/*”, “*/”), so that the comments will be properly ignored. If you generate a hex-formatted exploit string in the file exploit.txt, you can apply the raw string to CTARGET or RTARGET in several different ways: 1. You can set up a series of pipes to pass the string through HEX2RAW. unix> cat exploit.txt | ./hex2raw | ./ctarget 2. You can store the raw string in a file and use I/O redirection: unix> ./hex2raw < exploit.txt > exploit-raw.txt unix> ./ctarget < exploit-raw.txt This approach can also be used when running from within GDB: unix> gdb ctarget (gdb) run < exploit-raw.txt 3. You can store the raw string in a file and provide the file name as a command-line argument: unix> ./hex2raw < exploit.txt > exploit-raw.txt unix> ./ctarget -i exploit-raw.txt This approach also can be used when running from within GDB. B Generating Byte Codes Using GCC as an assembler and OBJDUMP as a disassembler makes it convenient to generate the byte codes for instruction sequences. For example, suppose you write a file example.s containing the following assembly code: # Example of hand-generated assembly code pushq $0xabcdef # Push value onto stack addq $17,%rax # Add 17 to %rax movl %eax,%edx # Copy lower 32 bits to %edx The code can contain a mixture of instructions and data. Anything to the right of a ‘#’ character is a comment. You can now assemble and disassemble this file: unix> gcc -c example.s unix> objdump -d example.o > example.d The generated file example.d contains the following: example.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 : 0: 68 ef cd ab 00 pushq $0xabcdef 5: 48 83 c0 11 add $0x11,%rax 9: 89 c2 mov %eax,%edx The lines at the bottom show the machine code generated from the assembly language instructions. Each line has a hexadecimal number on the left indicating the instruction’s starting address (starting with 0), while the hex digits after the ‘:’ character indicate the byte codes for the instruction. Thus, we can see that the instruction push $0xABCDEF has hex-formatted byte code 68 ef cd ab 00. From this file, you can get the byte sequence for the code: 68 ef cd ab 00 48 83 c0 11 89 c2 This string can then be passed through HEX2RAW to generate an input string for the target programs.. Alternatively, you can edit example.d to omit extraneous values and to contain C-style comments for readability, yielding: 68 ef cd ab 00 /* pushq $0xabcdef */ 48 83 c0 11 /* add $0x11,%rax */ 89 c2 /* mov %eax,%edx */ This is also a valid input you can pass through HEX2RAW before sending to one of the target programs. References [2] E. J. Schwartz, T. Avgerinos, and D. Brumley. Q: Exploit hardening made easy. In USENIX Security Symposium, 2011.
The nefarious Dr. Evil has planted a slew of “binary bombs” on our class machines. A binary bomb is a program that consists of a sequence of phases. Each phase expects you to type a particular string on stdin. If you type the correct string, then the phase is defused and the bomb proceeds to the next phase. Otherwise, the bomb explodes by printing “BOOM!!!” and then terminating. The bomb is defused when every phase has been defused. Step 1: Get Your Bomb You can obtain your bomb by pointing your Web browser at: http://127.0.0.1:15213 This will display a binary bomb request form for you to fill in. Enter your user name and email address and hit the Submit button. The server will build your bomb and return it to your browser in a tar file called bombk.tar, where k is the unique number of your bomb. Save the bombk.tar file to a (protected) directory in which you plan to do your work. Then give the command: tar -xvf bombk.tar. This will create a directory called ./bombk with the following files: • README: Identifies the bomb and its owners. • bomb: The executable binary bomb. • bomb.c: Source file with the bomb’s main routine and a friendly greeting from Dr. Evil. If for some reason you request multiple bombs, this is not a problem. Choose the first downloaded bomb to work on and delete the rest. Step 2: Defuse Your Bomb Your job for this lab is to defuse your bomb. You must do the assignment on one of the class machines. In fact, there is a rumor that Dr. Evil really is evil, and the bomb will always blow up if run elsewhere. There are several other tamper-proofing devices built into the bomb as well, or so we hear. You can use many tools to help you defuse your bomb. Please look at the hints section for some tips and ideas. The best way is to use your favorite debugger to step through the disassembled binary. Each time your bomb explodes it notifies the bomblab server, and you lose 1/2 point (up to a max of 20 points) in the final score for the lab. So there are consequences to exploding the bomb. You must be careful! The first four phases are worth 10 points each. Phases 5 and 6 are a little more difficult, so they are worth 15 points each. So the maximum score you can get is 70 points. Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase should offset this difficulty. However, the last phase will challenge even the best students, so please don’t wait until the last minute to start. The bomb ignores blank input lines. If you run your bomb with a command line argument, for example, $./bomb answers.txt then it will read the input lines from answers.txt until it reaches EOF (end of file), and then switch over to stdin (e.g., wait until you enter input via command line interface). In a moment of weakness, Dr. Evil added this feature so you don’t have to keep retyping the solutions to phases you have already defused. Note that after you run the program, you can use Ctrl+C (SIGINT) to terminate (or kill) the program instead of typing input (This does not cause bomb to explode). To avoid accidentally detonating the bomb, you will need to learn how to single-step through the assembly code and how to set breakpoints. You will also need to learn how to inspect both the registers and the memory states. One of the nice side-effects of doing the lab is that you will get very good at using a debugger. This is a crucial skill that will pay big dividends the rest of your career. Logistics This is an individual project. All handins are electronic. Clarifications and corrections will be posted on the course message board. Handin http://127.0.0.1:15213/scoreboard This web page is updated continuously to show the progress for each bomb. Hints (Please read this!) There are many ways of defusing your bomb. You can examine it in great detail without ever running the program, and figure out exactly what it does. This is a useful technique, but it not always easy to do. You can also run it under a debugger, watch what it does step by step, and use this information to defuse it. This is probably the fastest way of defusing it. We do make one request, please do not use brute force! You could write a program that will try every possible key to find the right one. But this is no good for several reasons: • You lose 1/2 point (up to a max of 20 points) every time you guess incorrectly and the bomb explodes. • Every time you guess wrong, a message is sent to the bomblab server. You could very quickly saturatethe network with these messages, and cause the system administrators to revoke your computer access. Note that you need to defuse your own bomb. Your submission might be ignored if the bomb isn’t yours. Please double check when you download the bomb. • gdb The GNU debugger, this is a command line debugger tool available on virtually every platform. You can trace through a program line by line, examine memory and registers, look at both the source code and assembly code (we are not giving you the source code for most of your bomb), set breakpoints, set memory watch points, and write scripts. The CS:APP web site http://csapp.cs.cmu.edu/public/students.html has a very handy single-page gdb summary that you can print out and use as a reference. Here are some other tips for using gdb. – To keep the bomb from blowing up every time you type in a wrong input, you’ll want to learn how to set breakpoints. – For online documentation, type “help” at the gdb command prompt, or type “man gdb”, or “info gdb” at a Unix prompt. Some people also like to run gdb under gdb-mode in emacs. • objdump -t • objdump -d Use this to disassemble all of the code in the bomb. You can also just look at individual functions. Reading the assembler code can tell you how the bomb works. Although objdump -d gives you a lot of information, it doesn’t tell you the whole story. Calls to system-level functions are displayed in a cryptic form. For example, a call to sscanf might appear as: 8048c36: e8 99 fc ff ff call 80488d4 To determine that the call was to sscanf, you would need to disassemble within gdb. • strings This utility will display the printable strings in your bomb.
The purpose of this assignment is to become more familiar with bit-level representations of floating point numbers. You’ll solve six problems in the presentation. 2 Logistics This is an individual project. All handins are electronic. Clarifications and corrections will be posted on PLMS. If you have any question, please use Q & A board. Submitted codes are assumed to be runnable on programming server. 3 Handout Instructions Start by copying datalab-floating-point.tar to a (protected) directory on a Linux machine in which you plan to do your work. Then give the command unix> tar xvf datalab-floating-point.tar. This will cause a number of files to be unpacked in the directory. The only file you will be modifying and turning in is bits.c. The bits.c file contains a skeleton for each of the 6 programming problems. 4 The Problems 4.1 Two’s Complement Arithmetic Your assignment is to complete each function skeleton using only straightline code for the integer problems (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators: ! ˜ & ˆ | + > A few of the functions further restrict this list. Also, you are not allowed to use any constants longer than 8 bits. See the comments in bits.c for detailed rules and a discussion of the desired coding style. Table 1 describes a set of functions that make use of the two’s complement representation of integers. Again, refer to the comments in bits.c and the reference versions in tests.c for more information. Name Description Rating Max Ops negate(x) -x without negation 2 5 isLess(x,y) x < y? 3 24 Table 1: Arithmetic Functions 4.2 Floating-Point Operations Table 2 describes a set of functions that operate on the bit-level representations of floating-point numbers. Refer to the comments in bits.c and the reference versions in tests.c for more information. Functions float_neg and float_twice must handle the full range of possible argument values, including not-a-number (NaN) and infinity. The IEEE standard does not specify precisely how to handle NaN’s, and the IA32 behavior is a bit obscure. We will follow a convention that for any function returning a NaN value, it will return the one with bit representation 0x7FC00000. The included program fshow helps you understand the structure of floating point numbers. To compile fshow, switch to the handout directory and type: Name Description Rating Max Ops float_abs(uf) Compute absolute value off 2 10 float_twice(uf) Compute 2*f 4 30 float_twice(uf) Computer 2*f 4 30 float_i2f(x) Compute (float) x 4 30 Table 2: Floating-Point Functions. Value f is the floating-point number having the same bit representation as the unsigned integer uf. unix> make You can use fshow to see what an arbitrary pattern represents as a floating-point number: unix> ./fshow 2080374784 Floating point value 2.658455992e+36 Bit Representation 0x7c000000, sign = 0, exponent = f8, fraction = 000000 Normalized. 1.0000000000 X 2ˆ(121) You can also give fshow hexadecimal and floating point values, and it will decipher their bit structure. 5 Evaluation Your score will be computed out of a maximum of 19 points. Correctness points. We will evaluate your functions using the btest program, which is described in the next section. You will get full credit for a problem if it passes all of the tests performed by btest, and no credit otherwise. Autograding your work We have included some autograding tools in the handout directory — btest, dlc, and driver.pl — to help you check the correctness of your work. • btest: This program checks the functional correctness of the functions in bits.c. To build and use it, type the following two commands: unix> make unix> ./btest Notice that you must rebuild btest each time you modify your bits.c file. You’ll find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct btest to test only a single function: unix> ./btest -f bitAnd You can feed it specific function arguments using the option flags -1, -2, and -3: unix> ./btest -f bitAnd -1 7 -2 0xf Check the file README for documentation on running the btest program. 6 Handin Instructions Upload your source file bits.c and report in PLMS. You need to explain your answer in the report. The format of file is (student number) (your name).c / .pdf. 7 Advice • The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced by gcc. In particular, any declaration must appear in a block (what you enclose in curly braces) before any statement that is not a declaration. For example, it will complain about the following code: int foo(int x) { int a = x; a *= 3; /* Statement that is not a declaration */ int b = a; /* ERROR: Declaration not allowed here */ }
Minimum Submission Requirements Ensure that your Gradescope submission contains the following file: ○ Lab3.asm Objective This lab will introduce you to the RISC-V assembly language programming using RARS (RISCV Assembler and Runtime Simulator). You will write a program with nested loops in the provided file Lab3.asm to write a specific pattern to a file by the name of lab3_output.txt (which will be generated by running your submitted Lab3.asm file. lab3_output.txt does not exist prior to this action) Since this is your very first foray into assembly programming, please read this document thoroughly without skipping any sections! Resources Much like how a high-level program has a specific file extension (.c for C, .py for python) RARS based RISC-V programs have a .asm extension. In the Lab3 folder in the course Google Slide, you will see 7 assembly files. They are meant for you to read (and understand) in sequence: 1. firstRARSprogram.asm – This program just prints “Hello World” on the output console. 2. add.asm – This program accepts two integers as user inputs and prints their addition result on the output console. 3. multiply.asm – This program accepts two integers as user inputs and prints their multiplication result on the output console. This file specifically shows you how to do loops in assembly 4. fileWriteDemo.asm – This program creates a file for writing, and then writes a line of text into the file. Basically, it shows the basics to do a file Write in RARS. 5. fileReadDemo.asm – This program reads the file generated by the above .asm file and reads out its contents on the output console. Basically, it shows the basics to do a file Read in RARS. 6. patternDisplayDemo.asm – This program inputs a number n from user and generates a “* * * ….” Pattern depending on the value of n. This pattern is written into a file. Understanding how this code works will help you in writing the pattern required of this lab assignment into a file as well. 7. Lab3.asm – Some starter code has already been provided in this file which you will need to complete and then submit to your Gradescope autograding portal. The starter code mainly revolves around macros that have been created for your benefit to create and write to the file lab3_output.txt. Please download these files and make sure to open them in the RARS Text editor only. Doing otherwise will cause comments and other important code sections to not be properly highlighted and can be a hindrance to learning assembly language intuitively. Steps for opening, assembling and running a .asm file are provided later in this document. These 7 files have enough comments in the source code to jump start your understanding of RISC-V assembly programming if the lectures have not yet covered certain topics in assembly programming. For the usage of macros (which are utilized heavily in this lab to generate system calls refererred to as ecalls), please also refer to the RARS documentation on macros and ecalls as well. For lab3, you don’t even need to know what the inside of a macro block looks like so long you know just what it is supposed to do overall. Working in RARS Helpful tip: For lab3 and lab4, it is recommended that you create two separate folders in your machine, lab3 and lab4. Make each folder the workspace for your respective lab. So, for the given lab, place all the provided .asm files in the Lab3 folder along with a copy of the .jar RARS application file, and run RARS from there. This is where you will create your Lab3.asm file as well.Figure 1 Ideal workspace setup for lab3/lab4 Henceforth, run all .asm files pertinent to Lab3 on this local copy of the .jar RARS application. Open the RARS application. You should get the window below.Figure 2 Opening the RARS application Let us open firstRARSprogram.asm by clicking File -> Open. Make sure the comments (which appear in green) are properly indented and haven’t been misaligned when you downloaded the file from the Google Drive. They should appear as shown below:Figure 3 Opening an asm file on RARS Make sure to thoroughly read the entire contents of this file in the text editor. Verbose comments have been provided to guide you along in explaining each step in the source code. This will be the norm for the other .asm files in the Lab3 folder in Google Drive as well. After you have read and understood the source code, it is time to assemble the program. Before you assemble, go to Settings and make sure you have the exact following options checked (or unchecked). For this course, you are allowed to use pseudo instructions. Pseudo instructions are those instructions which are not native to the RISC-V instruction set but the RARS environment has defined these new ones by a combination of actual RISC-V instructions. Permit pseudo instructions (this actually makes coding easier for you). This should be done for every RARS code in CSE12!Figure 4 RARS setting Now click on Assemble (the Wrench and screwdriver icon). If correctly assembled, your Messages window should show the following information:Figure 5 Successful assembly Now Click on the Run button to Run the program. You will get the following output:Figure 6 Successful Runtime Now try running the other .asm files. One word of caution when your text editor contains multiple opened files is to make sure of assembling the correct assembly file. For example, in the window below, multiple files are open. If I want to only assemble and run add.asm, then my tab for add.asm should be highlighted as shown below. Only then can I click Assemble, then Run.Figure 7 Multiple tabs open A Helpful Feature in RARS RARS has a helpful feature where instead of Running the entire program at once, you can Run One Step At A Time. The corresponding button is beside the Run button. This allows you to sequentially execute each line of code and see how it affects the values of the Registers as they appear to the right of your screen. Regarding Macros The file multiply.asm makes extensive use of macros to help create a more readable main program section (Instructions on how to use macros are provided in the file comments). So does the source code in the files fileWriteDemo.asm, fileReadDemo.asm and patternDisplayDemo.asm (we will discuss more on the aspect of file reads and writes that these .asm files do shortly). Based on how we define a macro in the source code, it is tempting to confuse it with a function. However, macros are NOT functions! Whenever you place multiple instances of the same macro in your code, you are copying the macro’s contents in those code areas for the same number of times. Naming New Files in RARS When you want to open a new file on RARS, go to File->New. The default file name riscv1.asm shows up on the tab. When you save this file, you MUST make sure that you are explicitly defining the correct extension(.asm) as shown below.Figure 8 Saving a new file in RARS About File Reads and Writes in RARS File creation and manipulation is a very common part of the learning curve whenever you learn of a new high level programming language, be it C or Python. For lab3, we will be writing the display pattern to a file so that it is more convenient for the auto grader. The auto grader within Gradescope will do a file text equality check between files generated by your lab3 source code and expected correctly generated files and accordingly provide you points (or not!). To give you a demo, we have two reference assembly source code files: fileWriteDemo.asm and fileReadDemo.asm. The former file creates a file with the name fileDemo.txt. The following text is written into fileDemo.txt: “These pretzels are making me thirsty!”. The latter file fileReadDemo.asm contains code to open fileDemo.txt and extract out this text to display on the output console of RARS. The following two images shows the results of having run fileWriteDemo.asm and then fileReadDemo.asm.Figure 9 A new file generated in my workspace after running fileWriteDemo.asm. Note the file size to be shown as 1KB despite us having written only 38 bytes of data into it. That is because a file also contains metadata and a header generated by your OS as well.Figure 10 RARS output console after running fileReadDemo.asm Both fileWriteDemo.asm and fileReadDemo.asm use many macros within the source code to make the main .text section of the code more programmer friendly in terms of writing. For the purposes of lab3, you DO NOT need to understand WHAT these macros are doing within their definition block. It suffices to know simply what the result of executing a macro in your source code simply does. However, understanding the macros does help to build your foundation in RARS programming well. We will deal with register preservation in lab4 but in lab3, you will only be asked to ensure that you do not use specific registers in your Lab3.asm source code. The list of these taboo registers will be highlighted in the section later on Lab3 Besides the aforementioned 2 files related to file write and read, we also have a 3rd .asm file, patternDisplayDemo.asm. The source code in this file, once run, asks as input an integer n and then prints the pattern “* “ n number of times horizontally.Figure 11 Output console after running patternDisplayDemo.asm for user input n=3 and7. In both cases, make sure to check the contents of the created file patternDisplay.txt as well Similar to patternDisplayDemo.asm, Lab3.asm will also make use of loops (nested loops to be precise) to generate a pattern based on the value of n inputted by the user. Thus, you should thoroughly read and understand the working of source code in patternDisplayDemo.asm. Lab3 Programming Assignment This program will print out a pattern with stars (asterisks, ascii hex code 0x2a) and blank space (ascii hex code 0x20) and the newline character ‘ ’(ascii hex code 0x0a). 1. It will first prompt for the height of the pattern (i.e., the number of rows in the pattern). If the user enters an invalid input such as a negative number or zero, an error message will be printed and the user will be prompted again. These error messages are listed in the starter code in the Lab3.asm file provided. 2. Then your program should generate the following pattern, a ” right-angled triangle”, using the aforementioned characters. Refer to test cases in testCases sub folder in Lab3 folder for examples. 3. This entire pattern generated from the user input of n is written to the file lab3_output.txt. The actual task of opening the file lab3_output.txt and writing the contents to it is borne by macros used in starter code included in the Lab3.asm file. Consider the screenshot of the Lab3.asm file below:Figure 12 Lab3.asm screenshot As you can see, you should write down your code ONLY within the area indicated by the comments. The way this code works regarding file manipulation is as follows: In your student code, you can update the file buffer with any character with the macro write_to_buffer. For example, I want to the write the character sequence “**** ” to my memory buffer within Lab3.asm’s student code section. Then I would need to write the following student code as shown next:Figure 13 Modified Lab3.asm screenshot Run this Lab3.asm file and open the generated lab3_output.txt in a text editor. Specifically, if you are using Notepad++ (which is strongly recommended), make sure to apply the setting: View->Show Symbol ->Show All Characters. This will make characters such as null and newline visible.Figure 14 lab3_output.txt screenshot from running modified Lab3.asm As you can see, the blank space appears as an orange dot, newline as LF (Line Feed) and null as NUL. You can see these characters as they reside in the file buffer in memory too on RARS as shown below. If you go to Execute window after running this modified Lab3.asm, selecting 0x1004000 for view and enabling ASCII view, you will get the following screenshot:Figure 15 “* ** * ” data as it resides in file buffer Note that within each individual cell in the Data Segment matrix above, we should read the bytes from right to left. NOTE: For your student starter code, you MUST NOT use any of the registers: t0 to t6, sp. a0 to a7 should only be temporarilly used to pass parameters or receive parameters from macros. Using the registers s0 through s11 should be enough for Lab3 assignment. Example of running the actual correct Lab3.asm source code The following is a screenshot showing the runtime of the actual solved Lab3.asm code:Figure 16 Solved Lab3.asm runtime demo When we open the generated lab3_output.txt file, we get the following text:Figure 17 lab3_output.txt screenshot Your student code MUST display the prompts and error messages in response to user input EXACTLY as shown in Figure 16. Please make use of the provided strings in the .data section of the starter code in Lab3.asm to make sure you do not use any other type of sentence! NOTE: Although you are not required to print each row in the pattern on your output console, doing so (as shown in Figure 16 ) will greatly help in the real time code debugging. So, it is strongly advised to do so. Test Cases The Lab3 folder in the Google Drive contains some test cases in testCases subfolder for the case when user input was n=1, 3, 6, 8, 30. Make sure your code output generates the exact same alignment of characters as provided there for the corresponding n input in your student code. Automation Note that our grading script is automated, so it is imperative that your program’s output matches the specification exactly. The output that deviates from the spec will cause point deduction. Files to be submitted to your Lab3 gradescope portal Lab3.asm -This file contains your pseudocode and assembly code. Include a header comment as indicated in the documentation guidelines here. You should be doing this assignment completely all by yourself! Grading Rubric (100 points total) The following rubric applies provided you have fulfilled all criteria in Minimum Submission Requirements. Failing any criteria listed in that section would result in an automatic grade of zero which cannot be legible for applying for a regrade request. 20 pt Lab3.asm assembles without errors (thus even if you submit Lab3.asm having written absolutely no student code, you would still get 20 pts!) 80 pt output in file lab3_output.txt matches the specification: 20 pt error check zero and negative heights using the convention shown in Figure 16 20 pt prompts user until a correct input is entered as shown in Figure 16 20 pt number of rows match user input (i.e., if n=6, the pattern would have 6 row 20 pt correct sequence of stars and newline characters on each row Legal Notice In the case of sites such as Chegg.com, we have been able to locate course material shared by a previous quarter student. Chegg cooperated with us by providing the student’s contact details, which was sufficient proof of the student’s misconduct leading to an automatic failing grade in the course.
In this lab you will be writing a dynamic storage allocator for C programs, i.e., your own version of the malloc, free and realloc routines. You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient and fast. 2 Logistics This is an individual project. All handins are electronic. Clarifications and corrections will be posted on PLMS. If you have any question with this lab, please use Q&A board in PLMS. Submitted codes are assumed to be runnable on programming server 3 Hand Out Instructions Start by copying malloclab-handout.tar to a directory in which you plan to do your work. Then give the command: unix> tar xvf malloclab.tar This will cause a number of files to be unpacked into the directory. The only file you will be modifying and handing in is mm.c. The mdriver.c program is a driver program that allows you to evaluate the performance of your solution. Use the command make to generate the driver code and run it with the command ./mdriver -V. (The -V flag displays helpful summary information.) 4 How to Work on the Lab Your dynamic storage allocator will consist of the following four functions, which are declared in mm.h and defined in mm.c. int mm_init(void); void *mm_malloc(size_t size); void mm_free(void *ptr); void *mm_realloc(void *ptr, size_t size); In the mm.c file, we have given you implements the simplest but still functionally correct malloc package that we could think of. Using this as a starting place, modify these functions (and possibly define other private static functions), so that they obey the following semantics: • mminit: Before calling mmmalloc, mmrealloc, or mmfree, the application program (i.e., the trace-driven driver program that you will use to evaluate your implementation) calls mminit to perform any necessary initializations, such as allocating the initial heap area. The return value should be -1 if there was a problem in performing the initialization, 0 otherwise. • mmmalloc: The mmmalloc routine returns a pointer to an allocated block payload of at least size bytes. The entire allocated block should lie within the heap region and should not overlap with any other allocated chunk. We will compare your implementation to the version of malloc supplied in the standard C library (libc). Since the libc malloc always returns payload pointers that are aligned to 8 bytes, your malloc implementation should do likewise and always return 8-byte aligned pointers. • mmfree: The mm free routine frees the block pointed to by ptr. It returns nothing. This routine is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to mmmalloc or mmrealloc and has not yet been freed. • mmrealloc: The mmrealloc routine returns a pointer to an allocated region of at least size bytes with the following constraints. – if ptr is NULL, the call is equivalent to mmmalloc(size); – if size is equal to zero, the call is equivalent to mmfree(ptr); – if ptr is not NULL, it must have been returned by an earlier call to mmmalloc or mmrealloc. The call to mmrealloc changes the size of the memory block pointed to by ptr (the old block) to size bytes and returns the address of the new block. Notice that the address of the new block might be the same as the old block, or it might be different, depending on your implementation, the amount of internal fragmentation in the old block, and the size of the realloc request. The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Everything else is uninitialized. For example, if the old block is 8 bytes and the new block is 12 bytes, then the first 8 bytes of the new block are identical to the first 8 bytes of the old block and the last 4 bytes are uninitialized. Similarly, if the old block is 8 bytes and the new block is 4 bytes, then the contents of the new block are identical to the first 4 bytes of the old block. These semantics match the the semantics of the corresponding libcmalloc, realloc, and free routines. For the complete documentation, type the following command in Linux terminal: unix> man malloc 5 Heap Consistency Checker Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation. You will find it very helpful to write a heap checker that scans the heap and checks it for consistency. Some examples of what a heap checker might check are: • Is every block in the free list marked as free? • Are there any contiguous free blocks that somehow escaped coalescing? • Is every free block actually in the free list? • Do the pointers in the free list point to valid free blocks? • Do any allocated blocks overlap? • Do the pointers in a heap block point to valid heap addresses? Your heap checker will consist of the function int mmcheck(void) in mm.c. It will check any invariants or consistency conditions you consider prudent. It returns a nonzero value if and only if your heap is consistent. You are not limited to the listed suggestions nor are you required to check all of them. You are encouraged to print out error messages when mmcheck fails. This consistency checker is for your own debugging during development. When you submit mm.c, make sure to remove any calls to mmcheck as they will slow down your throughput. Style points will be given for your mmcheck function. Make sure to put in comments and document what you are checking. 6 Support Routines The memlib.c package simulates the memory system for your dynamic memory allocator. You can invoke the following functions in memlib.c: • void *memsbrk(int incr): Expands the heap by incr bytes, where incr is a positive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area. The semantics are identical to the Unix sbrk function, except that memsbrk accepts only a positive non-zero integer argument. • void *memheaplo(void): Returns a generic pointer to the first byte in the heap. • void *memheaphi(void): Returns a generic pointer to the last byte in the heap. • sizet memheapsize(void): Returns the current size of the heap in bytes. • sizet mempagesize(void): Returns the system’s page size in bytes (4K on Linux systems). 7 The Trace-driven Driver Program The driver program mdriver.c in the malloclab-handout.tar distribution tests your mm.c package for correctness, space utilization, and throughput. The driver program is controlled by a set of trace files that are included in the malloclab-handout.tar distribution. Each trace file contains a sequence of allocate, reallocate, and free directions that instruct the driver to call your mmmalloc, mmrealloc, and mmfree routines in some sequence. The driver and the trace files are the same ones we will use when we grade your handin mm.c file. The driver mdriver.c accepts the following command line arguments: • -t : Look for the default trace files in directory tracedir instead of the default directory defined in config.h. • -f : Use one particular tracefile for testing instead of the default set of tracefiles. • -h: Print a summary of the command line arguments. • -l: Run and measure libc malloc in addition to the student’s malloc package. • -v: Verbose output. Print a performance breakdown for each tracefile in a compact table. • -V: More verbose output. Prints additional diagnostic information as each trace file is processed. Useful during debugging for determining which trace file is causing your malloc package to fail. For more information, read “Building and running the driver” part in README. 8 Programming Rules • You should not change any of the interfaces in mm.c. • You should not invoke any memory-management related library calls or system calls. This excludesthe use of malloc, calloc, free, realloc, sbrk, brk or any variants of these calls in your code. • You are not allowed to define any global or static compound data structures such as arrays, structs, trees, or lists in your mm.c program. However, you are allowed to declare global scalar variables such as integers, floats, and pointers in mm.c. • For consistency with the libcmalloc package, which returns blocks aligned on 8-byte boundaries, your allocator must always return pointers that are aligned to 8-byte boundaries. The driver will enforce this requirement for you. 9 Evaluation You will receive zero points if you break any of the rules or your code is buggy and crashes the driver. Otherwise, your grade will be calculated as follows: • Correctness (20 points). You will receive full points if your solution passes the correctness tests performed by the driver program. You will receive partial credit for each correct trace. • Performance (35 points). Two performance metrics will be used to evaluate your solution: – Space utilization: The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via mmmalloc or mmrealloc but not yet freed via mmfree) and the size of the heap used by your allocator. The optimal ratio equals to 1. You should find good policies to minimize fragmentation in order to make this ratio as close as possible to the optimal. – Throughput: The average number of operations completed per second. The driver program summarizes the performance of your allocator by computing a performance index, P, which is a weighted sum of the space utilization and throughputwhere U is your space utilization, T is your throughput, and Tlibc is the estimated throughput of libc malloc on your system on the default traces. The performance index favors space utilization over throughput, with a default of w = 0.6. Observing that both memory and CPU cycles are expensive system resources, we adopt this formula to encourage balanced optimization of both memory utilization and throughput. Ideally, the performance index will reach P = w + (1 − w) = 1 or 100%. Since each metric will contribute at most w and 1 − w to the performance index, respectively, you should not go to extremes to optimize either the memory utilization or the throughput only. To receive a good score, you must achieve a balance between utilization and throughput. • Style (10 points). – Your code should be decomposed into functions and use as few global variables as possible. – Your code should begin with a header comment that describes the structure of your free and allocated blocks, the organization of the free list, and how your allocator manipulates the free list. each function should be preceeded by a header comment that describes what the function does. – Each subroutine should have a header comment that describes what it does and how it does it. – Your heap consistency checker mmcheck should be thorough and well-documented. You will be awarded 5 points for a good heap consistency checker and 5 points for good program structure and comments. 10 Handin Instructions Submit your code as [student id]mm.c (e.g., 20234567mm.c) and your report as [student id].pdf (e.g., 20234567.pdf). Do not compress the file, submit your code and report separately. 11 Hints • Use the mdriver-f option. During initial development, using tiny trace files will simplify debugging and testing. We have included two such trace files (short1,2-bal.rep) that you can use for initial debugging. • Use the mdriver-v and -V options. The -v option will give you a detailed summary for each trace file. The -V will also indicate when each trace file is read, which will help you isolate errors. • Compile with gcc -g and use a debugger. A debugger will help you isolate and identify out of bounds memory references. • Understand every line of the malloc implementation in the textbook. The textbook has a detailed example of a simple allocator based on an implicit free list. Use this is a point of departure. Don’t start working on your allocator until you understand everything about the simple implicit list allocator. • Encapsulate your pointer arithmetic in C preprocessor macros. Pointer arithmetic in memory managers is confusing and error-prone because of all the casting that is necessary. You can reduce the complexity significantly by writing macros for your pointer operations. See the text for examples. • Do your implementation in stages. The first 9 traces contain requests to malloc and free. The last 2 traces contain requests for realloc, malloc, and free. We recommend that you start by getting your malloc and free routines working correctly and efficiently on the first 9 traces. Only then should you turn your attention to the realloc implementation. For starters, build realloc on top of your existing malloc and free implementations. But to get really good performance, you will need to build a stand-alone realloc. • Start early! It is possible to write an efficient malloc package with a few pages of code. However, we can guarantee that it will be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!
Introduction This assignment gives you hands-on experience on using HMMs on part-ofspeech tagging. We will use the Wall Street Journal section of the Penn Treebank to build an HMM model for part-of-speech tagging. In the folder named data, there are three files: train, dev and test. In the files of train and dev, we provide you with the sentences with human-annotated part-of-speech tags. In the file of test, we provide only the raw sentences that you need to predict the part-of-speech tags. The data format is that, each line contains three items separated by the tab symbol ‘ ’. The first item is the index of the word in the sentence. The second item is the word type and the third item is the corresponding part-of-speech tag. There will be a blank line at the end of one sentence. Task 1: Vocabulary Creation (20 points) The first task is to create a vocabulary using the training data. In HMM, one important problem when creating the vocabulary is to handle unknown words. One simple solution is to replace rare words whose occurrences are less than a threshold (e.g. 3) with a special token ‘< unk >’. Task. Creating a vocabulary using the training data in the file train and output the vocabulary into a txt file named vocab.txt. The format of the ocabulary file is that each line contains a word type, its index in the vocabulary and its occurrences, separated by the tab symbol ‘ ’. The first line should be the special token ‘< unk >’ and the following lines should be sorted by its occurrences in descending order. Note that we can only use the training data to create the vocabulary, without touching the development and test data. What is the selected threshold for unknown words replacement? What is the total size of your vocabulary and what is the total occurrences of the special token ‘< unk >’ after replacement? Task 2: Model Learning (20 points) The second task is to learn an HMM from the training data. Remember that the solution of the emission and transition parameters in HMM are in the following formulation: t(s′|s) = count(count(s→s)s′) e(x|s) = count(count( where t(·|·) is the transition parameter and e(·|·) is the emission parameter. Task. Learning a model using the training data in the file train and output the learned model into a model file in json format, named hmm.json. The model file should contains two dictionaries for the emission and transition parameters, respectively. The first dictionary, named transition, contains items with pairs of (s,s′) as key and t(s′|s) as value. The second dictionary, named emission, contains items with pairs of (s,x) as key and e(x|s) as value. How many transition and emission parameters in your HMM? Task 3: Greedy Decoding with HMM (30 points) The third task is to implement the greedy decoding algorithm with HMM. Task. Implementing the greedy decoding algorithm and evaluate it on the development data. What is the accuracy on the dev data? Predicting the part-of-speech tags of the sentences in the test data and output the predictions in a file named greedy.out, in the same format of training data. Task 4: Viterbi Decoding with HMM (30 Points) The fourth task is to implement the viterbi decoding algorithm with HMM. Task. Implementing the viterbi decoding algorithm and evaluate it on the development data. What is the accuracy on the dev data? Predicting the part-of-speech tags of the sentences in the test data and output the predictions in a file named viterbi.out, in the same format of training data. Submission Please follow the instructions and submit a zipped folder containing: 1. A txt file named vocab.txt, containing the vocabulary created on the training data. The format of the vocabulary file is that each line contains a word type, its index and its occurrences, separated by the tab symbol ‘ ’. (see task 1). 2. A json file named hmm.json, containing the emission and transition probabilities (see task 2). 3. Two prediction files named greedy.out and viterbi.out, containing the predictions of your model on the test data with the greedy and viterbi decoding algorithms. You also need to submit your python code and a README file to describe how to run your code to produce your prediction files. (see task 3 and task 4). 4. A PDF file which contains answers to the questions in the assignmentalong with brief explanations about your solution.
Learning Outcomes • Read and interpret a written description of an algorithm • Correctly implement an algorithm from pseudocode • Generate test cases for the implementation • Design and execute benchmarks for an algorithmOverview In this lab, you will read a paper describing the scapegoat balanced binary search tree and implement the data structure based on that description.Instructions Read the provided paper and submit a report containing the following:1. Read sections 1 – 4, 6, and 8 – 9 of the provided paper and answer the following questions: a. How do scapegoat trees compare with Red-Black, AVL, and splay trees? Why might you prefer to use or not use a scapegoat tree? b. What does it mean for a node to be weight balanced? What does it mean for a tree to be weight-balanced? Draw some examples and calculate their weight balances. c. What is the interpretation of the parameter? d. What are the conditions for triggering a rebuild of a subtree (during inserts) or the entire tree (during deletes)? 2. Implement a scapegoat tree that supports insert, size, delete, and contains operations. The tree should additionally support a toList() operation that generates a list from an in-order traversal. Add a counter variable to keep track of the number of times the rebuild operation is performed. You do not need to implement the logarithmic space rebuild algorithm described in 6.1 and 6.2 – use the straightforward approach. 3. Write unit tests that involve the insert, remove, size, contains, and toList() operations. 4. Benchmark the insert, delete, and contains operations of your implementation on data sets of different sizes. Create tables and plots that include both run times and the number of times the rebuild operation was performed. 5. Analyze and interpret the benchmark results to determine if the run time of your implementation is consistent with the theoretical analysis.Submission Instructions Save your report as a PDF. Upload your report and source code files to Canvas.Rubric Full Credit Partial Credit No Credit Report writing and presentation quality 15% Reading response questions 10% The decision rule is correct for all possible inputs that conform to the problem description The described rule is correct for most inputs. The decision rule is not correct for some common cases. Implementation of the insert, size, contains, delete, and toList() operations 25% Implementations are correct without consideration of time complexity. Implementations are mostly correct without consideration of time complexity. Implementations are fundamentally flawed. Logic for triggering a rebuild on insert and rebuilding the subtree are correct 10% Implementations are correct without consideration of time complexity. Implementations are mostly correct without consideration of time complexity. Implementations are fundamentally flawed. Logic for triggering a rebuild on delete and rebuilding the entire tree are correct 10% Implementations are correct without consideration of time complexity. Implementations are mostly correct without consideration of time complexity. Implementations are fundamentally flawed. Test Cases 10% Test cases consider a range of problem sizes and complexities and potential edge cases. Limited number of test cases or only testing obvious or simple cases. No test cases. Benchmarks 10% Benchmark experiments were set up and run correctly. Benchmark experiments, implementations, or results are mostly correct. Benchmark experiments, implementations, or results are flawed. Implementation run time 10% Empirical results support theoretical run times from paper. Empirical results support theoretical run times from paper for most operations. Implementation is slower than expected from theoretical run time.
Learning Outcomes • Design an algorithm for a given computational problem statement • Justify the correctness of an algorithm • Perform asymptotic complexity analysis of the run time of an algorithm • Generate test cases for an algorithm • Correctly implement an algorithm from pseudocode • Design and execute benchmarks for an algorithmInstructionsSelection ProblemInput: A sequence of n 2 numbers and an integer 1 k n.Output: Find kth smallest number.For example, if we are given the following numbers:[5, 1, 6, 7, 3, 4, 8]and asked to find k = 3, we would return 4.It is easier to see why if we sort the numbers:[1, 3, 4, 5, 6, 7, 8]The number 4 is the 3rd smallest number. This problem commonly occurs in statistics when trying to find the medium or a percentile of a distribution.The simplest way to solve this problem is to sort the numbers and take the element at index k – 1. From class, you know that the fastest comparative sorting algorithms require O(n log n) time. If the data are partially sorted (e.g., the first k elements are sorted), the run time can be further reduced to O(k n) or O(k log n).It turns out that it is possible to create an even faster algorithm using a divide and conquer strategy. Hint: You randomly select a pivot value and partition the numbers around that pivot. The pivot value turns out to be the jth number, so the left partition contains j elements (including the pivot) and the right partition contains n – j elements.Submit a report containing the following:1. A paragraph describing the approach that you used to solve the problem. Provide at least 2 illustrations that explain the approach. 2. High-level pseudocode for an algorithm that uses that rule to solve the computational problem for any input. 3. Provide an explanation and justification for why your algorithm is correct (1-3 paragraphs). 4. A table of your test cases, the answers you expect, and the answers returned by running your implementation of the algorithm. 5. Derive a recurrence relation describing the run time in terms of the number of points n. (Hint: assume that the random pivot divides the elements in half each time.) 6. Solve the recurrence relation to get a run time in terms of n in asymptotic notation. 7. Benchmark your implementation versus an approach that sorts the numbers and picks the element at index k – 1. You should include a table and graph from benchmarking different lists with different sizes of numbers. The benchmarks should support your theoretically-derived run time and provide evidence that the run time of your algorithm grows more slowly than the sorting approach. 8. Attach all of your source code and test cases in an appendix.Submission Instructions Submit the lab report as a PDF and all source code to Canvas.Rubric Full Credit Partial Credit No Credit Lab report writing and presentation quality 20% High-level Pseudocode 10% Pseudocode describes an algorithm which is correct for all allowed inputs. Pseudocode describes an algorithm which is correct for most allowed inputs. Pseudocode is not correct for most allowed inputs. Justification of Correctness 10% Uses techniques described in class to provide a solid and convincing argument that the algorithm is correct. Provides a somewhat convincing argument that the algorithm is correct. Argument contains one or more serious flaws. Asymptotic run time analysis 10% Analysis is correct for the provided pseudocode Analysis is mostly correct except for minor flaws Analysis is significantly flawed Algorithm Implementation 10% Implementation is faithful to the pseudocode description above and correct. Implementation is mostly faithful to the pseudocode description above and correct for most inputs. Implementation is not faithful to the pseudocode or not correct for some common inputs. Test Cases 10% Test cases consider a range of problem sizes and complexities and potential edge cases. Limited number of test cases or only testing obvious or simple cases No test cases Benchmarks 10% Benchmark experiments were set up and implemented correctly. Benchmark experiments, implementations, or results are mostly correct. Benchmark experiments, implementations, or results are flawed. Algorithm run time 10% Algorithm is faster than O(k log n), as determined by both empirical and theoretical analysis results. Algorithm is faster than O(n log n). Algorithm equal to or slower than O(n log n) bruteforce search
Learning Outcomes • Design an algorithm for a given computational problem statement • Justify the correctness of an algorithm • Perform asymptotic complexity analysis of the run time of an algorithm • Generate test cases for an algorithm • Correctly implement an algorithm from pseudocode • Design and execute benchmarks for an algorithmOverview For this lab, you are given the description of several problems. You will pick one problem to work on. You will be expected to think about the problem and come up with a fundamental insight or rule that will allow you to solve the problem. Once achieved, you will be able to write and analyze an algorithm using the techniques you learned in class. Instructions Choose one of the problems described below. Submit a report containing the following: 1. A paragraph describing a “decision rule” that can be applied to solve to the computational problem. Provide at least 2 illustrations (test cases) that demonstrate how the rule is applied. 2. High-level pseudocode for an algorithm that uses that rule to solve the computational problem for any input 3. Provide an explanation and justification for why your algorithm is correct (1-3 paragraphs) 4. Perform an analysis of the worst-case run time using asymptotic notation. 5. A table of your test cases, the answers you expect, and the answers returned by running your implementation of the algorithm. 6. A table and graph from benchmarking your implementation on problem instances of different sizes. The benchmarks should support your theoretically derived run time. 7. Attach all your source code and test cases in an appendix. In addition to the lab report, you will be required to provide a working implementation of your algorithm. Your implementation should be accompanied by a handful of both simple and more complex test cases that you came up with. Determine if a Point is Located Inside a Polygon Input: • A sequence of n 3 2D points. Each point is a pair of x and y coordinates. The points correspond to the vertices of a simple (non-intersecting) polygon. The polygon is connected by line segments between each adjacent pair of points, including a line segment from the last point to the first point. • The x and y coordinates for a single point distinct from the vertex points. Output: A Boolean value indicating whether the point is located inside the polygon.Inside OutsideHints: • Draw examples of polygons with points located inside and outside the polygons. For each point, try drawing horizontal and vertical line segments that start at each point and continue infinitely in one direction. Consider any crossings between the line segments and the edges of the polygon.Determine if a Polygon is Convex Input: A sequence of n 3 2D points. Each point is a pair of x and y coordinates. The points correspond to the vertices of a simple (non-intersecting) polygon. The polygon is connected by line segments between each adjacent pair of points, including a line segment from the last point to the first point. Output: True if the polygon is convex. False otherwise.Convex ConcaveHints: • Draw multiple examples of convex and concave examples of polygons. Consider the angles. • Approach this problem as a proof by contradiction problem. You only need to find one example of a violation of the decision rule.2D Convex Hull Assume you are given a set of points (the black dots below). The convex hull (blue) is the subset of points that form a convex polygon and encloses the original set of points. Input: A sequence of n 3 2D points. Each point is a pair of x and y coordinates. Output: A subsequence of the input points that form the convex hull.Hints: • Sort the points by angle so you can process them in clockwise or counterclockwise order. • Use a stack. • Whenever a new point is being considered, see if it violates a requirement of convexity. If so, remove points so that convexity is restored. Submission Instructions Submit the lab report as a PDF, all source code in a zip file, and upload to Canvas.Rubric Full Credit Partial Credit No Credit Lab report writing and presentation quality 20% Decision Rule 10% The decision rule is correct for all possible inputs that conform to the problem description The described rule is correct for most inputs. The decision rule is not correct for some common cases. High-level Pseudocode 10% Justification of Correctness 10% Uses techniques described in class to provide a solid and convincing argument that the algorithm is correct. Provides a somewhat convincing argument that the algorithm is correct. Argument contains one or more serious flaws. Asymptotic run time analysis 10% Analysis is correct for the provided pseudocode Analysis is mostly correct except for minor flaws Analysis is significantly flawed Algorithm Implementation 10% Implementation is faithful to the pseudocode description above and correct. Implementation is mostly faithful to the pseudocode description above and correct for most inputs. Implementation is not faithful to the pseudocode or not correct for some common inputs. Test Cases 10% Test cases consider a range of problem sizes and complexities and potential edge cases. Limited number of test cases or only testing obvious or simple cases Benchmarks 10% Benchmark experiments were set up and implemented correctly. Benchmark experiments, implementations, or results are mostly correct. Benchmark experiments, implementations, or results are flawed. Algorithm run time 10% Benchmark results agree with the theoretical run time analysis. Benchmark results mostly agree with the theoretical run time analysis. Benchmark results disagree significantly with the theoretical run time analysis.
