Academic Integrity
Plagiarism is strictly prohibited. You shall not use any references other than the lecture notes and the reference book. You may discuss with others, but you need to write your own solutions.
There are 100+15 (bonus) marks in total. You get min(100, total) marks for this assignment. This assignment counts 10% of the course.
• (15 marks)
Starting with the following AVL tree, draw each of the resulting AVL tree after the operations insert 30, insert 40, and delete 10.
11
/ \
5 23 ins ins del
/ \ / \ ======> ? ======> ? ======> ? 2 7 17 31 30 40 10
\ / \
10 29 37
• (15 marks)
Write a pseudocode for left rotation at node u (assuming that its right child exists). Here the left rotation function should also maintain both the heights of the nodes u -> height and the sizes of the subtrees rooted at the nodes u -> size.
• (15 marks + 5 bonus marks + 5 bonus marks)
We call a binery search tree k-height balanced if for any node, the difference of heights of its left subtree and its right subtree is at most k. Hence AVL trees are 1-height balanced binery search trees. Prove that 2-height balanced binery search trees are also balanced, that is, the heights of 2-height balanced trees are O(log n) where n is the number of nodes in the tree.
(Bonus) Prove that k-height balanced trees are balanced for any fixed constant k.
(Bonus) We call a binery search tree size balanced if for any node u with a grandparent, the size of u (the number of nodes in the subtree rooted at u) is at most the size of the uncle of u (the other child of the grandparent of u, empty subtrees have size 0). Prove that size balanced trees are balanced.
• (15 marks) The lowest common ancestor (LCA) of two nodes u and v in a tree is the deepest (furthest from the root) node that is both an ancestor of u and an ancestor of
v. For example, in the diagram of Q.1, the LCA of 17 and 37 is 23 and the LCA of 2
and 29 is 11.
Provide a pseudocode for LCA(u, v) and briefly explain its runtime. Suppose w is the LCA of u and v in a binery search tree, and the distance between w and the root is d, then finding the LCA can be done in O(1 + d) time.
• (15 marks + 5 bonus marks) You are in a n by n maze with at most 2 locked doors. Luckily you know exactly the locations of the keys for the doors. How do you find the smallest number of steps to escape the maze?
In the following example, @ represents your current position, * represents the exit of the maze. Lowercase letters a and b represents the keys for the doors represented by uppercase letters A and B respectively. The smallest number of steps needed is 24: the first 6 steps are used to get a, the next 8 steps are used to get b and the final 10 steps are used to get to exit *.
@Ab#*
.###B
….. #.##. a….
Briefly describe the graph you should work on: what the nodes are, what the edges are, what the starting node is and what the destinations are, what the number of nodes and edges are. After building the graph correctly, this question should be solved by simply a breadth first search from the starting node to the destinations. What is the runtime needed for the breadth first search?
(Bonus) What if we have k locked doors? Briefly describe the graph and the runtime needed.
• Programming task: First Lie (25 marks)
There are n children (labeled 0 to n – 1) playing the classical game rock paper scissors. The usual game is played by two children, each of them choose one of the rock, paper or scissors. If they choose different shapes, then rock wins scissors, scissors wins paper and paper wins rock. Other when they choose the same shape, it is a draw game.
Now the n children choose their shapes simultaneously and begins their m conversa- tions. Each of the m conversations can be represented by three integers i, j and r, meaning the result between children i and children j. r can be either 0, 1 or -1. If r = 0, this conversation means “the game between children i and children j is a draw game”. If r = 1, this conversation means “children i wins children j in their game”. If r = -1, this conversation means “children i loses to children j in their game”.
In this question, you are given the m conversations (numbered 0 to m – 1) and need to find the first conversation that is contradicting to the previous conversations.
You will get full mark if the runtime of your program is O(n + m log n). If you use the disjoint set data structure, you should use one of the optimizations union by rank or path compression to guarantee the runtime is O(log n) for each operation.
Input: The first line has two integer n and m. Each of the following m lines would be three integers i, j and r representing the conversation. Our testcases satisfies 1 <= n <= 100000 and 1 <= m <= 100000.
Output: The output should be a single line with a single integer k, meaning that conversations 0 to k - 1 are consistent but conversation k is contradicting to the previous conversations.
Sample Input:
4 5
0 1 1
1 2 1
2 3 1
2 0 -1
0 3 0
Sample Output:
3
Here is an explaination of the sample input / output. Clearly the conversations 0 to 2 are consistent, for example, one possible scenario may be rock for child 0, scissors for child 1, paper for child 2 and rock for child 3. However conversation 3 contradict to the previous conversations: there is no way that child 0 wins both child 1 (conversation
0) and child 2 (conversation 3) and yet child 1 wins child 2 (conversation 1). Hence the first inconsistent conversation happens at conversation 3.
No libraries other than cstdio and iostream shall be used. Only correctness and efficiency would be tested, so you do not have to write comments for your codes.