need help with problem 2  plz see attach file....................................

 

 

Data Structures and Algorithms
Pennsylvania State University
Professors Adam Smith & Piotr Berman January 28, 2017
CMPSC 465
Spring 2017 Homework 3 – Due Friday, February 3, 2017
Reminders
• Collaboration is permitted, but you must write the solutions by yourself without assistance,
and be ready to explain them orally to a member of the course staff if asked. You must
also identify your collaborators. If you worked alone, write “Collaborators: None.” Getting
solutions from outside sources such as the Web or students not enrolled in the class is strictly
forbidden.
Problems to be handed in
1. (Carpets) You finally graduated from Penn State and took a job that allowed you to afford
your very own apartment. Congratulations!
The living space in your new apartment is a 2k × 2k -foot square (which you mentally divide
into 22k cells, each 1 foot square). Bizarrely, exactly one cell of the floor is covered by carpet,
and the rest is bare cement (Figure 1 (b)).
2k Fortunately, a friend has given you a pile of 2 3−1 carpet pieces. Each carpet piece is Lshaped, formed by three 1-by-1 adjacent squares (Figure 1(a)). Each piece covers 3 cells, so
you have just enough carpet to cover the whole cement part of the floor, if the pieces can fit.
Your job is to find a way to lay the pieces so they cover the cement. The carpet should cover
all cells except the covered one with no overlaps. You may not cut the carpet pieces—you
have to use them as they are—but it is fine to rotate them. (a) (b) Figure 1: (a) A carpet piece in one of its 4 possible orientations. (b) A 16 × 16 floor with one
covered cell. 1 Submit your solution to parts (a)-(c) as a PDF on Canvas, and your solution to
(d) on Vocareum.
(a) Design a divide-and-conquer algorithm for this problem. The inputs are n = 2k (which
determines the size of the room) and the coordinates (x, y) ∈ {1, ..., n} × {1, ..., n} of the
missing square. You may assume n is an integer power of 2. The output should be a list
of triples, where each triple describes the position of one of the carpet pieces you will
put down.
First, explain your algorithm concisely in English (feel free to use pictures). Second,
specify your algorithm using clear pseudocode or readable Python code.
(b) Prove that your algorithm is correct.
(c) Give a recurrence for the worst case running time of your algorithm in terms of n and
solve it. How long does your algorithm take as a function of n?
(d) Implement your algorithm on Vocareum. 2. (Recurrences) [Submit your answers as PDF on Canvas.]
(a) For each of the following algorithms, write a recurrence relation that best describes the
running time of the algorithm. You don’t need to prove the algorithm is correct or solve
the recurrence; just write it down.
Algorithm 1: FindMax(A, `, r)
Input: A is an array of real numbers, indexed from 1 to n; `, r ∈ {1, ..., n} satisfy ` ≤ r
1 if ` = r then
2
return A[`]
3
4
5
6
7 else if r − ` = 1 then
return max(A[`], A[r])
else
mid = `+r
2 ;
return max(FindMax(`, mid),FindMax(mid + 1, r)) To write a recurrence analyze the next algorithm, it is helpful to know that one can add
and subtract two matrices (of the same dimensions) in time proportional to the number
of entries in each of the matrices. 2 Algorithm 2: MatrixMultiply(A,B)
Input: A, B are n × n square matrices
1 if n = 1 then
2
return A × B
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 else
Partition A into A11 , A12 , A21 , A22
Partition B into B 11 , B 12 , B 21 , B 22
// Where each is a quarter of the original matrices (m × m where m = n/2)
P1 ← MatrixMultiply(A11 , B 12 − B 22 )
P2 ← MatrixMultiply(A11 + A12 , B 22 )
P3 ← MatrixMultiply(A21 + A22 , B 22 )
P4 ← MatrixMultiply(A22 , B 21 − B 11 )
P5 ← MatrixMultiply(A11 + A22 , B 11 + B 22 )
P6 ← MatrixMultiply(A12 − A22 , B 21 + B 22 )
P7 ← MatrixMultiply(A11 − A21 , B 11 − B 12 )
C 11 ← P5 + P4 − P2 + P6
C 12 ← P1 + P2
C 21 ← P3 + P4
C 22 ← P1 + P5 − P3 − P7
Combine C 11 , C 12 , C 21 , and C 22 into n × n matrix C
return C (b) For each of the following recurrences, give a one-line answer to the following questions:
When you construct a recursion tree of the recurrence relation,
A. how many leaves does it have?
B. what is the height of the tree?
C. how many nodes does it have?
i. T (n) = 4T n2 + n2
ii. T (n) = T (n − 1) + n


iii. T (n) = 3T n5 + n3

iv. T (n) = T n
3
+T  2n
3  + √ n You may assume that T (n) = 1 for n ≤ 1   √


+ n), use the substitution
(c) For the last recurrence (that is, T (n) = T n3 + T 2n
3
method to prove that T (n) = O(n). You may again assume that T (n) = 1 for n ≤ 1. 3

Attachments:

• 1493867274-CMPSC465-S17-hw3.pdf