COM S 311 SPRING 2021 HOMEWORK 1
Due: February 19 11:59 p.m.
Early submission: February 18, 11:59 p.m., (5% bonus) Late Submission Due: February 20, 11:59 A.M. (25% penalty)
Guidelines
• For each problem, if you write the statement “I do not know how to solve this problem” (and nothing else), you will receive 20% credit for that problem. If you do write a solution, then your grade could be anywhere between 0% to 100%. To receive this 20% credit, you must explicitly state that you do not know how to solve the problem.
• You are allowed to discuss with classmates, but you must work on the homework problems on your own. You should write the final solutions alone, without consulting anyone. Your writing should demonstrate that you understand the proofs completely.
• When proofs are required, you should make them both clear and rigorous. Do not hand- waive.
• Please submit your assignment via Canvas.
– You must type your solutions. Please submit a PDF version.
– Please make sure that the file you submit is not corrupted and that its size is reasonable
(e.g., roughly at most 10-11 MB).
If we cannot open your file, your homework will not be graded.
• Any concerns about grading should be expressed within one week of returning the home- work.
Problems
(1) Prove or disprove the following statements. (a) n2 −10n+2=O(n2).
(b) 2n2 = O(22n).
(c) n log2(n) = O(n log10(n)).
(d) n log2(n) = O(n). (e) n2n = O(22n).
(2) Consider the following algorithms (written in pseudocode):
1
2 3 4 5 6 7
Alg1(A)
Input: Array of integers of length n constant number of operations
for i = 1 to n do
constant number of operations for j = n to 1 do
for k = j to 1 do
constant number of operations
1
1 Alg2(A)
Input: Array of integers of length n
2 3 4
for i = n to 1 do
constant number of operations i = i/2
Formally analyze the runtime of Alg1 and Alg2, and give the runtime of each in big oh notation. You must show your work – clearly and rigorously derive the runtime, do not just give the big oh bound.
(3) Given an array A of integers, we say that an integer k is the majority element of A if k occurs in A strictly more than A.length /2 times. Give a Divide and Conquer algorithm which, given an array A, determines if A contains a majority element. If A does contain a majority element k, it outputs k, otherwise, it outputs ”null“. Formally analyze the runtime of your algorithm, giving a recurrence relation and a big oh bound on the runtime of your algorithm. You must use a divide and conquer strategy. You do not have to prove correctness.
(4) Using the Master Theorem, bound the runtime T(n) of the following recurrence. T(n) = 3T(n/2) + n2, where T(1) = O(1).
You must state which case of the Master Theorem holds, and prove that it does apply.
(5) Using the recurrence tree method, solve the following recurrence:
T (n) = 2T (n/2) + n log2(n), where T (1) = O(1).
You do not have to draw the tree (you of course can, if you want). You can, instead, state clearly the sum of each level of the tree, and then rigorously bound the sum of each level using big oh notation.
(6) Professor Caesar wishes to develop an integer-multiplication algorithm that is asymptot- ically faster than Karatsuba’s O(nlog2(3)) algorithm. His algorithm will use the divide- and-conquer method, dividing each integer into pieces of size n/4, and the divide and combine steps together will take O(n) time. He needs to determine how many subproblems his algorithm has to create in order to beat Karatsuba’s algorithm. If his algorithm cre- ates a (an integer) subproblems, then the recurrence for the running time T(n) becomes T (n) = aT (n/4) + n. What is the largest integer value of a for which Professor Caesar’s algorithm would be asymptotically faster than O(nlog2(3))? Justify your answer.
2