COMP90038 Assignment 2 Solution

Objectives
To improve your understanding of data structures and algorithms for sorting and search. To consolidate your knowledge of trees and tree-based algorithms. To develop problem-solving and design skills. To develop skills in analysis and formal reasoning about complex concepts. To improve written communication skills; in particular the ability to use pseudo-code and present algorithms clearly, precisely and unambiguously.
Problems

The search algorithm is presented below. We assume that each node has the fields {key,up,down, left,right}, where key represents the key value, and the remaining four are pointers to the adjacent nodes or null. Starting at the leftmost node L in the highest level, we scan through each level as far as we can without passing the target value x, and then proceed down to the next level. The search ends when we find the node with the largest key that is less or equal than x. Since each level of the skip list has about half of the nodes as the previous, the total number of levels is O (logn), and the overall expected search time is O (logn).
1: function Search(x,L)
2: u ← L
3: while u.down 6= null do
4: u ← u.down ⊲ Drop a level down
5: while x ≥ u.right.key do
6: u ← u.right ⊲ Scan forward
7: return u
1: u ← u.up
2: while CoinFlip()
3: v ← NewNode(x,u,v) 4: if isHead(u) then
5: u ← u.left
6: function InsertNode(x,u)
7: v ← NewNode(x,u,null)
8: while u.up = null and u.left 6= null do
9: w ← NewNode(−∞,null,u)
10: NewNode(∞,w,v.right)
11: return v
An α > 0 indicates that the staff member and its supervisor dislike each other, whereas an α < 0 indicates that they actually like each other. If the guest list does not include an employee and its supervisor, then the added awkwardness is zero. To help you model Klutzy Pty Ltd assume that each node has the following fields: (a) L is a pointer to the left child or null if there is no left child; (b) R is a pointer to the right child or null if there is no right child; and (c) alpha is the awkwardness score of the inviting the employee and its supervisor. Provide a method that finds the score of the least awkward party, i.e., minimise the overall awkwardness score. For example, your algorithm should return ‘-1’ and ‘0’ for the two trees in the figure below. You must provide:

Submission and Evaluation
• You must submit a PDF document via the LMS. Note: handwritten, scanned images, and/or Microsoft Word submissions are not acceptable — if you use Word, create a PDF version for submission.
• We expect your work to be neat — parts of your submission that are difficult to read or decipher will be deemed incorrect. Make sure that you have enough time towards the end of the assignment to present your solutions carefully. Time you put in early will usually turn out to be more productive than a last-minute effort.
• Number of lines are given as an indication only and should not be considered as the actual length of the code. Correct solutions could have a few lines more or less depending on your notation, but not many more (if you see yourself writing ten more extra lines, then you are probably doing something wrong).
Please see https://academicintegrity.unimelb.edu.au