data编程设计代写、代做Python、Python程序调试

日期：2021-04-11 10:31

Assignment: Recursion, Recurrence Relations and Divide & Conquer

1. Implement algorithm: There are two 2D-boxes that can placed on the coordinate system. A

box can be represented by the position of the coordinates where it is placed. This can be

listed as [x1, y1, x2, y2], where the first pair of coordinates correspond to the location of the

bottom-left corner, and second pair of coordinates correspond to the top right corner.

Given coordinates of two boxes, identify if they overlap. If they overlap return true else

return false.

Note: If the boxed that touch each other at the corner or edges should return false.

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its

bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two

rectangles that only touch at the corner or edges do not overlap.

Think if you can come up with recursive function to solve this problem, if yes write it, if not

explain why.

Write a function doBoxesOverlap(box1, box2) that take the coordinate positions of each box

as input and return whether they overlap or not. Name your file BoxAlgorithm.py

Example 1:

Input: box1 = [0,0,2,2], box2 = [1,1,3,3]

Output: true

Example 2:

Input: box1 = [0,0,1,1], box2 = [1,0,2,1]

Output: false

2. Solve recurrence relation using three methods:

a. Write recurrence relation of below pseudocode that calculates ??

??

, and solve the

recurrence relation using three methods that we have seen in the explorations.

power2(x,n):

if n==0:

return 1

if n==1:

return x

if (n%2)==0:

return power2(x, n//2) * power2(x,n//2)

else:

return power2(x, n//2) * power2(x,n//2) * x

b. Give the asymptotic bounds for T(n) in each of the following recurrences. Make your

bounds as tight as possible and justify your answers. Assume the base cases T(0)=1

and/or T(1) = 1.

a) ??(??) = 4?? ( ??/2 )+ ??

b) ??(??) = 2?? ( ??/4 ) + ??2

3. Implement an algorithm using divide and conquer technique [includes proving

correctness]:

A group of friends want to find out which day of the week majority of them share their

birthday’s on. They count week from Monday through Sunday. Monday:1, Tuesday:2…

Sunday:7. If a person is born on Wednesday his birthday is said to fall on number 3. Write

a function that would take these days as input and return the day of week on which most

of them share their birthday’s on.

Example 1:

Input: [3,2,3]

Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]

Output: 2

a. Write a pseudocode for a function MajorityBirthdays(days) that uses divide and

conquer technique. The function would take these days as input (in the form of an

array) and return the day of week on which most of them share their birthday’s on

b. Prove the correctness of your pseudocode that you wrote in part a of this question.

c. Implement the function MajorityBirthdays(days) that was written in part a. Name

your file DACAlgorithm.py

Debriefing (required!): --------------------------

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?

4. Any other comments?