Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 3511: Algorithms Honors Homework 1
Instructions:
- Upload your solutions to as a single PDF on Gradescope. Please anonymize all your submissions (i.e., do not list your name in the PDF), but if you forget, it’s OK.
- You may collaborate with any classmates, textbooks, any resource on the internet (but don’t search for the problem solution), etc. Please upload a brief “collaboration statement” listing any collaborators as the last page of your solutions PDF on Gradescope. But after the collaboration, always write your solutions individually.
- For each problem, you should aim to keep your writeup below one page. For some problems, this may be infeasible, and for some problems you may write significantly less than a page. This is not a hard constraint, but part of the assignment is figuring out how to easily convince the grader of correctness, and to do so concisely. “One page” is just a guideline: if your solution is longer because you chose to use figures (or large margins, display math, etc.) that’s fine.
- Each problem is worth ten points (even those with multiple subparts).
Problems:
(a) Solve the recurrence T(n) = 4 · T(n/2) + O(n 2 ). Provide a complete proof by induction, i.e., you cannot use the Master Theorem.
(b) Suppose you have two non-decreasing functions f(n) and g(n) such that f(n) = O(g(n)). Does this always imply 2f(n) = O(2g(n) )? Prove or provide a counter example.
§2 (Simple Algorithms)
(a) Give an O(n) algorithm to sort a list of n numbers, where each number is 0, 1, or 2.
(b) Suppose there are n workers, where worker i has skill si ≥ 0. Given a target T ≥ 0, you need to divide the workers into teams of two workers each (assume /n is even, so there will be n/2 teams). A team consisting of workers i and j is said to be good if si + sj ≥ T. Give an O(n log n) time algorithm to divide the workers into teams of two workers each such that the number of good teams is maximized.
(Hint: Use O(n) pairwise comparisons to reduce the n-by-n grid problem to n/2-by-n/2 grid problem.)
§4 (Median) In the median-of-medians algorithm from class, suppose we make groups of 7 elements, instead of groups of 5 elements.
(a) What fraction of the elements are we guaranteed to remove after the recursive call?(b) Which of the following is true, and why, about the running time of this algorithm: (i) running time improves to o(n), (ii) running time stays Θ(n), or (iii) running time worsens to ω(n)?