CSCI 570 – Spring 2021 – HW 3
Due Sunday March 07 (by 4:00 AM)
For all divide-and-conquer algorithms follow these steps:
1. Describe the steps of your algorithm in plain English. 2. Write a recurrence equation for the runtime complexity. 3. Solve the equation by the master theorem.
For all dynamic programming algorithms follow these steps: 1. Define (in plain English) subproblems to be solved.
2. Write the recurrence relation for subproblems.
3. Write pseudo-code to compute the optimal value
4. Compute its runtime complexity in terms of the input size.
1
Solve the following recurrences by giving tight Θ-notation bounds in terms of n for sufficiently large n. Assume that T(·) represents the running time of an algorithm, i.e. T(n) is positive and non-decreasing function of n and for small constants c independent of n, T(c) is also a constant independent of n. Note that some of these recurrences might be a little challenging to think about at first. Each question has 4 points. For each question, you need to explain how the Master Theorem is applied (2 points) and state your answer (2 points).
• (a)T(n)=4T(n/2)+n2logn. • (b)T(n)=8T(n/6)+nlogn.
√
√6006
1
• (c) T(n) =
• (e)T(n)=2T(√n)+log2n.
.
6006T(n/2) + n • (d) T(n) = 10T(n/2) + 2n.
• T(n)=T(n/2)−n+10 • T(n) = 2nT(n/2) + n
• T(n) = 2T(n/4) + n0.51 • T(n) = 0.5T(n/2) + 1/n • T(n) = 16T(n/4) + n!
2
Consider an array A of n numbers with the assurance that n > 2, A1 ≥ A2 andAn ≥An−1. AnindexiissaidtobealocalminimumofthearrayAifit satisfies1
Design an algorithm that cost at most O(n) time to find the maximum points you can get. Explain your algorithm and analyze its complexity.
6
Joseph recently received some strings as his birthday gift from Chris. He is interested in the similarity between those strings. He thinks that two strings a and b are considered J-similar to each other in one of these two cases:
1. a is equal to b.
2. he can cut a into two substrings a1,a2 of the same length, and cut b in
the same way, then one of following is correct:
(a) a1 is J-similar to b1, and a2 is J-similar to b2.
(b) a2 is J-similar to b1, and a1 is J-similar to b2.
Caution: the second case is not applied to strings of odd length.
He ask you to help him sort this out. Please prove that only strings having the same length can be J-similar to each other, then design an algorithm to determine if two strings are J-similar within O(nlogn) time (where n is the length of strings).
7
Chris recently received an array p as his birthday gift from Joseph, whose ele- ments are either 0 or 1. He wants to use it to generate an infinite long super- array. Here is his strategy: each time, he inverts his array by bits, changing all 0 to 1 and all 1 to 0 to get another array, then concatenate the original array and the inverted array together. For example, if the original array is [0, 1, 1, 0], then the inverted array will be [1, 0, 0, 1] and the new array will be [0, 1, 1, 0, 1, 0, 0, 1]. He wonders what the array will look like after he repeat this many many times.
He ask you to help him sort this out. Given the original array p of length n and two indices a, b (n ≪ a ≪ b, ≪ means much less than) Design an algorithm to
3
calculate the sum of elements between a and b of the generated infinite array pˆ, specifically, a≤i≤b pˆi. He also wants you to do it real fast, so make sure your algorithm runs less than O(b) time. Explain your algorithm and analyze its complexity.
4