Algorithms and complexity
1. This document is available https://www.overleaf.com/read/cgwdgmvhppzr
2. Submit as a pdf on Learnline
3. Hand drawings can be scanned and inserted
Question 1 (4 marks)List and QueueGiven 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
2. 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 emptytree. [1 mark
2. Using the tree traversal algorithms and the BST from (1) above, show theoutput 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 resul-tant 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 [fromhttps://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 var-ious 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) =nn+ 6n5 11
2. f(n) =3log2n+ 12n
3. f(n) =30 + 2n420n2+n
4. f(n) =7n5/7+ 2n
Question 5 (4 marks)Division
Suppose you are given two integer values x and y. Construct a recursive algo-rithm that uses any combination of the following operations: addition, subtrac-tion, 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
