Group Assignment (Practical)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Group Assignment (Practical)
Part I
Required Written Homework (60pts)
1 A Complex Complexity Problem (16pts)
Yihan recently learned the asymptotical analysis. The key
idea is to evaluate the growth of a function. For example,
she now knows that n2 grows faster than n, but for more
complicated functions, she feels confused.
Can you help Yihan compare the functions below? We use
log n to denote log2 n. Explain each of your answer
brieflfly.
For the following questions, use o, Θ or ω to fifill in the
blanks.
Questions:
1. (√ 2)log n = __(3√n)
Explain brieflfly:
2. log log n =__(ln ln n)
Explain brieflfly:
3. 22n+1 =__(22n+1)
Explain brieflfly:
4. (n + 1)! =__(n!)
Explain brieflfly:
2 Solve Recurrences (16pts)
For all of them, you can assume the base case is when n <
2, T(n) is also a constant. Use Θ(·) to present your answer.
Show your steps.
Questions:
(1) T(n) = T(n/2) + Θ(n2)
(2) T(n) = 2T(n/4) + Θ(√n log n)
(3) T(n) = 4T(n/4) + Θ(log log n)
(4) T(n) = T(√n) + 1
3 Test the candies (28pts)
You got job at a candy factory. It’s not always the case that
all the candies produced are perfect. There will be some
bad ones. Your task is to identify these bad candies from
n candies and discard them. However,you can not tell
which ones are bad directly: they look exactly the same.
The only thing you know is that,a bad candy has lighter
weight than standard (good) candies. More precisely, all
the good (standard) candies have the same weight wg,
and all the bad candies have the same weight wb < wg.
The only device you have is a balance scale, and you
don’t have any weights (so you cannot really know the
weight of each candy). As a result, the only thing you can
do is to put some candies on the left and some on the
right, and the balance will tell you if the left one is heavier,
the right one is heavier, or they balance.
Every time you use the balance, you have to pay 1 dollar.
All the other cost is free. Your task is to fifind all bad
candies using the lowest cost.
Questions:
For all questions below, please describe your algorithm
and brieflfly explain the cost.
1. (3pts) Your boss told you that there is only one bad
candy. In that case, can you show an algorithm that
uses d log2 ne (note: this is not in big-O!) dollars to
fifind this bad candy?
2. (5pts) Your boss told you that there is only one bad
candy. Now let’s improve the previous cost by a little
bit. Can you show an algorithm that uses d log3 ne
(again, not in big-O!) dollars to fifind this bad candy?
3. (5pts) Prove that d log3 ne dollars is the lower-bound
of the candy-testing problem in 3.2. In other words,
you cannot use fewer than d log3 ne dollars to
guarantee to fifind the bad candy.
4. (5pts) Your boss told you that there are only two bad
candies. Can you show an algorithm that uses O(log
n) dollars to fifind the two bad candies?
5. (5pts) If you already know that there are only k bad
candies, where k is a known constant, can you show
an algorithm that uses O(log n) dollars to fifind the k
bad candies? You could assume that k is a known
value and it could appear in your algorithm.
6. (5pts) In all above questions, we assume you know the
bad candy is lighter than standard. A more
diffiffifficult cases is where you only know that the bad
candy is of a difffferent weight, but you do not know if
it is lighter or heavier. Again assume there is only one
bad candy. Prove that, in this case, you need at least d
log3 2ne dollars to fifind the bad candy, and also tell
whether it is lighter or heavier.
7. (bonus, 4pts and 1 candy) Now let’s consider the
challenging setting where there is only one bad
candy,but you don’t know if the bad candy is lighter
or heavier. Luckily, your boss also gave you one good
candy as a reference (you’ll fifind this useful). Now
you have n = 13 candies, and one of them is bad
(either lighter or heavier). Plugging this into the lower
bound above gives d log3 (2 × 13)e = 3 dollars.
Now, show a solution for n = 13 for this case using 3
dollars.
Hint
Maybe divide-and-conquer is a good idea.
Part II
Basic Programming Problems (20pts)
See all problems at
https://codeforces.com/group/VVz3kLaLS7/contest/373905.
Part III
Challenge Problems (30pts)
4 Sort the Train
The programming problem can be found at:
https://codeforces.com/group/VVz3kLaLS7/contest/373905/problem/B.
Hints
You will fifind out that, if you run a bubble sort (where you
are only allowed to do “adjacent swaps”), and record the
number of swaps, that is always the optimal answer
(lowest number of swaps).
However, simulating bubble sort takes O(n2 ) time. Can
you come up with a better algorithm for that?
In particular, if you have an algorithm with complexity O(n
log n), you can pass all the test cases.
5 Sort the Train – Let’s prove it!
Well, now, let’s prove that your algorithm for the previous
question is correct and effiffifficient.
Questions:
1. (5pts) Show that, the number of swaps in the bubble
sort algorithm will give you the optimal solution.
2. (5pts) Design an algorithm with O(n log n) running
time to compute the number of fewest adjacent swaps
you need. You need to prove the complexity of your
algorithm.
6 Upper Bound Meets Lower Bound (20pts)
In this question, we’ll see an interesting proof for
upper/lower bound.
To fifind the maximum element of an array of size n, it is
clear that we need to do at least n−1 comparisons.
It is the same if you just want the minimum element. Then
what happens if we want to fifind both?
Consider the problem of fifinding both the maximum
element and the minimum element of an arbitrary set of n
distinct numbers, where n is even.
It turns out that 3/2n − 2 comparisons are required in the
worst case to do this. That is, 3/2n − 2 is a lower bound on
the number of comparisions needed (if you use fewer than
this number of comparisons, you cannot guarantee to
fifind the correct answer).
There’s also an algorithm that achieves exactly this bound.
That is, 3/2n − 2 is an upper bound on the number of
comparisons needed.
Since these bounds are equal, they are optimal.
(a) (7pts) Your task is to prove the following theorem:
Theorem: Consider a deterministic comparison based
algorithm A which does the following: given a set S of n
numbers as input, A returns the largest and the smallest
element of S. Prove that there is an input on which A must
perform at least 3/2n − 2 comparisons (i.e., this is a lower
bound for a comparison-based algorithm).
(b) (3pts) The proof above may directly leads to an optimal
deterministic algorithm (in terms of the number of
comparisons). Describe one such algorithm.
2025-12-25