代写comp2123、代做Java/C++程序语言

日期：2025-03-28 10:49

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