The University of Melbourne
School of Computing and Information Systems
COMP90038 Algorithms and Complexity
Assignment 2, Semester 2, 2018
Released: Tuesday 25 September. Deadline: Sunday 14 October at 23:59
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
1. [1 Mark] Consider the data sequence S = [82, 91, 13, 92, 64, 10, 28, 55, 96, 97]. Draw a
valid AVL tree for it, assuming that the data has arrived one at the time. Show detailed steps
by giving the AVL tree after inserting each element.
2. Consider two sets of integers, X = [x1, x2, . . . , xn] and Y = [y1, y2, . . . , yn]. Write two
versions of a FindSetIntersection(X,Y ) algorithm to find the common elements in both
sets. Each of your algorithms should return an array with the common elements, or an empty
array if there are no common elements.
You may make use of any algorithm introduced in the lectures to help you develop your
solution. That is, you do not have to write the ‘standard’ algorithms – just use them.
Therefore, you should be able to write each algorithm in about 10 lines of code. You must
include appropriate comments in your pseudocode.
(a) [2 Marks] Write a pre-sorting based algorithm of FindSetIntersection(X,Y ). Your
algorithm should strictly run in O (n log n).
(b) [2 Marks] Write a Hashing based algorithm of FindSetIntersection(X,Y ). Your
algorithm should run in O (n).
3. [4 Marks] Sloppy Inc. has a very unusual way to communicate the decisions made by its
CEO to all employees. Each day, any employee that knows the decision can disclose it to at
most one of its direct subordinates. Design an efficient algorithm to compute the minimum
number of days required for the decision to be disclosed to all employees. What is the time
complexity of your algorithm?
To help you design your algorithm, assume that Sloppy Inc. has a hierarchical structure
resembling an n-ary tree. Each employee is labeled {0, 1, . . . , n− 1}, where 0 corresponds to
root of the tree (the CEO). To store the tree you can use a two-dimensional array C [n] [n],
where k = C [i] [0] is the number of direct subordinates of employee i, and C [i] [1 . . . k] contains
the labels of each direct subordinate employee. Any other entry in the array has value of −1.
Note that the order in which the messages are distributed matters, e.g., employees with deeper
subordinate trees should probably receive the message first.
Hint : Solving this problem requires a recursion.
4. Given an array of n numbers A [0 . . . n− 1]. Write an efficient algorithm for below cases:
(a) [3 Marks] For each of the element A [i], find the minimum j so that A [j] > A [i] and
j > i. Your algorithm should return an array of length n. If such j does not exist for
some i, that entry should be -1. What is the complexity of your algorithm?
(b) [3 Marks] For each of the element A [i], find the minimum A [j] so that A [j] > A [i] and
j > i. Your algorithm should return an array of length n. If such j does not exist for
some i, that entry should be -1. Your algorithm should have O (n log n) complexity.
To help you verify your algorithm, for the sequence [80, 19, 49, 45, 65, 71, 76, 28, 68, 66]
the results are:
(a) [−1, 2, 4, 4, 5, 6, −1, 8, −1, −1]
(b) [−1, 7, 4, 4, 9, 6, −1, 9, −1, −1]
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.
• Marks are primarily allocated for correctness, but elegance of algorithms and how clearly you
communicate your thinking will also be taken into account. Where indicated, the complexity
of algorithms also matters.
• 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.
• You are reminded that your submission for this assignment is to be your own individual work.
For many students, discussions with friends will form a natural part of the undertaking of the
assignment work. However, it is still an individual task. You should not share your answers
(even draft solutions) with other students. Do not post solutions (or even partial solutions)
on social media or the discussion board. It is University policy that cheating by students in
any form is not permitted, and that work submitted for assessment purposes must be the
independent work of the student concerned.
Please see https://academicintegrity.unimelb.edu.au
If you have any questions, you are welcome to post them on the LMS discussion board so long as
you do not reveal details about your own solutions. You can also email the Head Tutor, Lianglu Pan
(lianglu.pan@unimelb.edu.au) or the Lecturer, Andres Munoz-Acosta (munoz.m@unimelb.edu.au).
In your message, make sure you include COMP90038 in the subject line. In the body of your
message, include a precise description of the problem.
Late Submission and Extension
Late submission will be possible, but a late submission penalty will apply: a flagfall of 2 marks,
and then 1 mark per 12 hours late. Extensions will only be awarded in extreme/emergency cases,
assuming appropriate documentation is provided simply submitting a medical certificate on the
due date will not result in an extension.