Department of EECS Fall 2020 York University Instructor: Andy Mirzaian
EECS3101E: Design and Analysis of Algorithms Assignment 3
1. [25%] Small Decision Tree:
Lecture Slide 5, Exercise 11.
2. [22%] Lower Bound on BST Construction: Lecture Slide 5, Exercise 28.
3. [23%] Coin Change Making:
Lecture Slide 6, Exercise 2
4. [30%] Balls and Boxes:
We have 𝑛 balls, each with weight at most 1. More specifically, the input is an array of weights 𝑊 1. . 𝑛 , where 𝑊[𝑖] is the weight of the 𝑖thball,0≤𝑊𝑖 ≤1, 𝑖=1..𝑛.
The problem is to put these balls in a minimum number of boxes so that:
i. each box contains no more than two balls, and
ii. the total weight of the balls placed in each box is ≤ 1.
a) [5%] Show an optimum solution for the following instance: W = [0.36, 0.45, 0.91, 0.62, 0.53, 0.05, 0.82, 0.35].
b) [25%] Design and analyze an efficient greedy algorithm for this problem.
[Prove the correctness of your algorithm by the greedy loop invariant method, and analyze its worst-case running time.]