Hello, dear friend, you can consult us at any time if you have any questions, add  WeChat:  zz-x2580

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:

1. log log n =__(ln ln n)

Explain brieflfly:

1. 22n+1 =__(22n+1)

Explain brieflfly:

1. (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?

1. (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?

1. (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.

1. (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?

1. (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.

1. (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.

1. (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)

Part III

Challenge Problems (30pts)

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.