Recursion, Recurrence Relations and Divide & Conquer

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?