HIT220 Algorithms and Complexity
Task:
All questions total marks are shown
Question 1
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.
2. Write pseudo code with comments to remove duplicates
3. Draw a queue loaded with the data. Draw the diagram for first and last two steps.
4. Using the final diagram from both (1) and (3), redraw them after removing the root node. Clearly label each diagram
Question 2
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.
2. Using the tree traversal algorithms and the BST from (1) above, show the output sequence for a
(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.
(b) Briefly describe both methods that you have used.
Question 3 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 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. 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
