HIT220 - Assignment 2 Cat Kutay Aug 2020 1. Submit as a pdf on Learnline 2. Hand drawings can be scanned and inserted 3. Marking rubric for each question: Marks will be awarded for accuracy, completeness, and well communicated reasoning which demonstrates your depth of understanding of the subject matter. Unless marks otherwise divided up: • Half marks will be given for right answer • Half marks will be given for working shown with verbal explanation of working For proofs include an example where you look at how the claim works with a specific set All questions total marks are shown Question 1 (4 marks) List and Queue Given the following sequence of data inserted in the following order [90, 65, 32, 67, 37, 32, 40, 26, 72, 20, 52, 65, 95]: 1. Draw a circular linked list of size 14 with the values inserted. Draw the diagram for first and last two steps. [.5 mark] 2. Write pseudo code with comments to remove duplicates [2.5 mark] 3. Draw a queue loaded with the data. Draw the diagram for first and last two steps. [.5 mark] 4. Using the final diagram from both (1) and (3), redraw them after removing the root node. Clearly label each diagram.[.5 mark] Question 2 (4 mark) Draw a BST 1. Draw the BST constructed by inserting the values [53, 25, 11, 63, 4, 88, 59, 3, 15, 82, 92, 27, 55, 14] in the order shown, into an initially empty tree. [1 mark] 1 2. Using the tree traversal algorithms and the BST from (1) above, show the output sequence for a [1 mark] (a) Preorder traversal (b) Postorder traversal 3. Delete the node with value 25 and draw the resultant tree. (a) Use two methods to delete the node with value 25 and draw the resultant tree. [1 mark] (b) Briefly describe both methods that you have used. [1 mark] Question 3 (4 marks) Code structure Using Python Code, or Pseudo code instructions, with comments for a recursive algorithm which will take a string from a small set of words as input and return the string in Larrakia. Use this wordlist attached below in your program [from https://asjp.clld.org/languages/LARRAKIA] Eg: Input: “I name water” Output: “Ngana ya kara” Question 4 (4 mark) Big O COmplexity The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O complexity, and provide suitable values to support your answer. Clearly highlight your answer and show any working you do. [1 mark each] 1. f(n) = n n + 6n 5 – 11 2. f(n) = 3log2n + 12n 3. f(n) = 30 + 2n 4–20n 2 + n 4. f(n) = 7n 5/7 + 2n Question 5 (4 marks) Division Suppose you are given two integer values x and y. Construct a recursive algorithm that uses any combination of the following operations: addition, subtraction, comparison. Calculate the remainder of x divided by y. Specify a set of example values for x and y which will result in at least 3 or more recursive calls, and draw the recursion trace diagram for your example. Question 6 (4 marks) Balanced Trees 1. Create a new balanced tree using the following sequence of values. Draw the tree at each step, specifying what rotation is necessary to balance the tree. Sequence: [1, 77, 55, 34, 78, 82, 95, 85, 12, 11, 35, 38, 43] [2 marks] 2. Remove nodes 12 77 and redraw the tree. [2 marks]