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.
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.
• (c) T(n) =
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!
Consider an array A of n numbers with the assurance that n > 2, A1 ≥ A2 andAn ≥An−1. AnindexiissaidtobealocalminimumofthearrayAifit satisfies1<i<n,Ai−1 ≥Ai andAi+1 ≥Ai.
(a) Prove that there always exists a local minimum for A.
(b) Design an algorithm to compute a local minimum of A.
Your algorithm is allowed to make at most O(logn) pairwise comparisons be- tween elements of A.
There are n cities where for each i < j, there is a road from city i to city j which takes Ti,j time to travel. Two travelers Marco and Polo want to pass through all the cities, in the shortest time possible. In the other words, we want to divide the cities into two sets and assign one set to Marco and assign the other one to Polo such that the sum of the travel time by them is minimized. You can assume they start their travel from the city with smallest index from their set, and they travel cities in the ascending order of index (from smallest index to largest). The time complexity of your algorithm should be O(n2). Prove your algorithm finds the best answer.
Erica is an undergraduate student at USC, and she is preparing for a very important exam. There are n days left for her to review all the lectures. To make sure she can finish all the materials, in every two consecutive days she must go through at least k lectures. For example, if k = 5 and she learned 2 lectures yesterday, then she must learn at least 3 today. Also, Erica’s attention and stamina for each day is limited, so for i’th day if Erica learns more than ai lectures, she will be exhausted that day.
You are asked to help her to make a plan. Design an Dynamic Programming algorithm that output the lectures she should learn each day (lets say bi), so that she can finish the lectures and being as less exhausted as possible(Specifically, minimize the sum of max(0,bi −ai)). Explain your algorithm and analyze it’s complexity.
hint: k is O(n). 5
Due to the pandemic, You decide to stay at home and play a new board game alone. The game consists an array a of n positive integers and a chessman. To begin with, you should put your character in an arbitrary position. In each steps, you gain ai points, then move your chessman at least ai positions to the right (that is, i′ >= i + ai). The game ends when your chessman moves out of the array.
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.
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).
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
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.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx