Description

For each statement below explain if it is true or false and in a couple of sentences provide an explanation for your answer. Be as mathematically precise as you can in your explanation. The base of log is 2 unless stated otherwise.
2 √
1. 2n = Θ(3n+ n) 2. n! = ω(2n)
3. Let f be positive function. Then f(n) = O((f(n))2).
2 Problem 2 (50 points)
1. T(n) = T(n − 1) + 2T(n − 2)
2. T(n) = 7T(n/15) + n5
3 Problem 3 (50 points)
4 Problem 4 (50 points)
You are given n tasks for a machine. Task i is described by li = [ai,bi] on the real line, where ai,bi are real numbers, ai ≤ bi and 1 ≤ i ≤ n. Give an algorithm that computes the total times of this set of tasks, that is, the length of in O(nlogn) time.
For example, for the set of tasks {[1,3],[2,4.5],[6,9],[7,8]}, the total time is (4.5 − 1) + (9 − 6) = 6.5.
Make sure to prove the correctness and running time of your algorithm.
5 Problem 5 (50 points)
Suppose that you have a set of n integers, A = {a1,…,an}, each of them is between 0 and K (inclusive). Your goal is to find a partition of A into two sets S1 and S2 (so S1∪S2 = A and S1∩S2 = ∅) that minimizes |W(S1)−W(S2)| where W(S) denote the sum of integers in S. Your algorithm’s running time should be polynomial in n and K.
Make sure to prove the correctness (mainly the optimal substructure property) and running time.