comp2123 Assignment 2 s1 2025
This assignment is due on April 8 and should be submitted on Gradescope.
All submitted work must be done individually without consulting someone else’s
solutions in accordance with the University’s “Academic Dishonesty and Plagia rism” policies.
Before you read any further, go to the last page of this document and read
the Written Assignment Guidelines section.
Problem 1. (20 points)
Let T be a binary tree holding n distinct integer keys. A node u ∈ T is said to
be lucky if its key is smaller than its parent’s (if it has a parent) and its children’s
key (if it has any children).
Consider the following algorithm that tries to find a lucky node:
Algorithm 1
1: function FindLucky(T, u)
2: if u.le f t = Null and u.le f t.key < u.key then
3: return FindLucky(T, u.left)
4: if u.right = Null and u.right.key < u.key then
5: return FindLucky(T, u.right)
6: if u.parent = Null and u.parent.key < u.key then
7: return FindLucky(T, u.parent)
8: return u
When the input u is lucky then clearly f indlucky(T, u) returns a lucky node,
namely, u itself. But is it true that for all v ∈ T the function f indlucky(T, v)
always returns a lucky node?
Your task is to
Prove that for all v ∈ T the function f indlucky(T, v) returns a lucky node
or provide a counter example where it fails to return the correct answer.
a)
b) Provide a tight time complexity analysis of the algorithm when T is complete.
Problem 2. (40 points)
Bob Proverra is an apple farmer who maintains an orchard of apple trees. Unfor tunately for Bob, squirrels and birds have begun to infest his trees and eat all the
produce. To make matters worse, a disease has begun to strike some branches
of the trees, meaning they will no longer produce apples in the following year.
Through advanced cameras on the farm, Bob can produce high-quality im ages of the trees, which show him the number of apples on each branch, and
any sightings of squirrels or birds, as well as if any branches are diseased.
Using these images, your task is to design an algorithm to count the number
of apples on each tree and then rank the trees from healthiest to least healthy.
Keep note of the following criteria:
1
comp2123 Assignment 2 s1 2025
• If a branch contains a squirrel, any apples on that branch or higher branches
connected to it should only count for half, since the squirrel may eat some
(this effect compounds if there are more squirrels higher up in the tree).
• If a branch contains a bird, all apples in that tree count for 3
4
, since the bird
may eat some (this effect does not compound).
• The more diseased branches are sighted, the less healthy the tree is rated.
If only part of the branch has visible disease, the rest of the branch is still
considered to be diseased (from the point the disease is visible, until the
leaves of the tree).
Describe an efficient algorithm to count apples in Bob’s orchard, prove the
correctness and analyse the time complexity.
a)
Describe an efficient algorithm to order trees in Bob’s orchard by healthi ness. Note that that the number of apples a tree produced doesn’t affect
its health rating.
b)
Consider if Bob was to prune all of the diseased branches and separate
them from his crop. How would this affect his crop yield? Modify your
algorithm to consider this, giving Bob an idea of how much produce he can
expect to grow in the following year (assuming no new branches grow).
c)
Problem 3. (40 points)
Let T be a binary tree whose nodes store distinct numerical values. Consider the
following pair of operations on binary trees:
• Rotate an arbitrary node upward.
• Swap the left and right subtrees of an arbitrary node.
In both of these operations, some, all, or none of the subtrees A, B, and C
could be empty.
2
comp2123 Assignment 2 s1 2025
Figure 1: rotate 2, rotate 2, swap 3, rotate 3, rotate 4, swap 3, rotate 2, swap 4
Your task is to design an algorithm to transform an arbitrary n-node binary
tree with distinct node values into a binary search tree, using at most O(n
2
)
rotations and swaps.
Your algorithm is not allowed to directly modify parent or child pointers,
create new nodes, or delete old nodes; the only way to modify the tree is through
rotations and swaps.
On the other hand, you may compute anything you like for free, as long as
that computation does not modify the tree; the running time of your algorithm
is defined to be the number of rotations and swaps that it performs.
a) describe your algorithm in plain English,
b) prove it correctness, and
c) analyze its time complexity.
3
comp2123 Assignment 2 s1 2025
Written Assignment Guidelines
• Assignments should be typed and submitted as pdf (no pdf containing text
as images, no handwriting).
• Start by typing your student ID at the top of the first page of your submis sion. Do not type your name.
• Submit only your answers to the questions. Do not copy the questions.
• When asked to give a plain English description, describe your algorithm
as you would to a friend over the phone, such that you completely and
unambiguously describe your algorithm, including all the important (i.e.,
non-trivial) details. It often helps to give a very short (1-2 sentence) de scription of the overall idea, then to describe each step in detail. At the end
you can also include pseudocode, but this is optional.
• In particular, when designing an algorithm or data structure, it might help
you (and us) if you briefly describe your general idea, and after that you
might want to develop and elaborate on details. If we don’t see/under stand your general idea, we cannot give you marks for it.
• Be careful with giving multiple or alternative answers. If you give multiple
answers, then we will give you marks only for "your worst answer", as this
indicates how well you understood the question.
• Some of the questions are very easy (with the help of the slides or book).
You can use the material presented in the lecture or book without proving
it. You do not need to write more than necessary (see comment above).
• When giving answers to questions, always prove/explain/motivate your
answers.
• When giving an algorithm as an answer, the algorithm does not have to be
given as (pseudo-)code.
• If you do give (pseudo-)code, then you still have to explain your code and
your ideas in plain English.
• Unless otherwise stated, we always ask about worst-case analysis, worst case running times, etc.
• As done in the lecture, and as it is typical for an algorithms course, we
are interested in the most efficient algorithms and data structures, though
slower solutions may receive partial marks.
• If you use further resources (books, scientific papers, the internet,...) to
formulate your answers, then add references to your sources and explain it
in your own words. Only citing a source doesn’t show your understanding
and will thus get you very few (if any) marks. Copying from any source
without reference is considered plagiarism.
4
請(qǐng)加QQ：99515681 郵箱：
[email protected] WX：codinghelp
