# HW 1

Due date: Wed, Jan 21, at the start of class.

Submissions: Please submit your printed or hand written solutions in class. If you have a compelling reason for not being able to attend that particular class, please email your submissions to the instructor or the TA.

Policy: Write your own solutions independently; include the names of anyone you discussed the problems with.

1. Let $A$ be an $n \times n$ two-dimensional array of integers. $A$ is sorted if each row is sorted and each column is sorted (in increasing order). Give an algorithm for sorting the entries of $A$ by swapping pairs of entries that runs in time $O(n^2\log n)$.
2. Give an algorithm to sort a list of numbers, where each number is $0, 1$ or $2$.
3. Squarezo is a square-shaped city with perimeter $N$ kilometers. The city is divided into $3$ sectors, one is a rectangle and two are equal sized squares, each of half the area of the rectangle. A rectangle is divided into two equal squares. A square is divided into $3$ parts — one rectangle of half the area and two equal sized squares. Consider the following iteration: take the shape of largest perimeter (rectangle or square) and if this perimeter is larger than $1$ apply this division procedure to this shape; if the largest perimeter is less than or equal to $1$ then stop.
(a) What is the total perimeter of all shapes obtained during this subdivision (including all intermediate shapes)? Write a recurrence for it.
(b) What is the total area of all rectangles obtained in the process?
(c) What is the total number of points that are vertices (corners) of some square or rectangle obtained during the process?
4. Given two positive integers $m$ and $n$, give the fastest algorithm you can find to compute $m^n$.

1. On problem #3, is a shape divided if it still has a perimeter > 1, or if any shape still has a perimeter > 1?

2. For #2,

Can list be {0,1,1,0,2,1} and algorithm that we give should sort that list to {0,0,1,1,1,2} ?
Also do we have any other constraints?

3. Byung: Yes the list might (and will in general) have repeated numbers but each number is from the set {0,1,2}. That is the only constraint in the problem.

William: I think Santosh meant that a shape is divided if it still has perimeter > 1, but I’ll draw his attention to it just in case.

4. For number 1, if an element is starts matrix[0][0] is it allowed to end up at matrix[n][n]?
More specifically, must elements stay in the same row or column they started in?

5. No it is not necessary that the elements must stay in the same row or column. If elements have to stay in the same row and column then the only possible answer is the matrix itself. If elements have to stay in the same row then I could give you in the first row an entry M where M is the global maximum. Then you couldn’t possibly “sort” this matrix. Similarly for columns.

6. I remember Santosh mentioned something about listing the people you collaborate with, but I can’t remember if this was in reference to the project or the homeworks, or both. Do we have to make this list for the homeworks? Thanks!

7. For #3
Lets say we started with 10 by 10 square. The initial perimeter is 40. The first iteration takes place and we will have 3 sections:
1) 10 by 5 rectangle (30 perimeter)
2) 5 by 5 square (20 perimeter)
3) 5 by 5 square (20 perimeter)

The total perimeter of the 3 sections will be 30 + 20 + 20 which is 70.

The question asked (a) What is the total perimeter of all shapes obtained during this subdivision (including all intermediate shapes)?

Let’s say we stop at first iteration. Will the answer be 70 or 70 + 40?

8. In the second iteration the perimeter should be 55 not 70. This is because the boundary of the rectangle and squares overlap. Think of it is as fences being built and we wish to estimate the total length of the fences. Then if you stop at the second iteration the answer should be 55. I realize the question is a little vague about which perimeter to estimate, I’ll edit it and try to make it clearer.

9. Thank you for making it clearer. I was confused about (including all intermediate shapes). I thought there will be overlapping of perimeter.

10. Another question for #3.

I am just trying to see if I understand the question right

First we have a square
First iteration will end up with a rectangle and 2 squares
Next iteration will end up with 4 squares
Next iteration will end up with 4 rectangle and 8 squares.

Is this right?

1. No it, on the second iteration you’ll end up with 2 big squares, 2 small rectangles, and 4 small squares.

2. Ratchapong: You are right, I had forgotten that I had edited the question a couple of days back. In the old question all shapes with perimeter bigger than 1 were being subdivided at once. Some students were confused about the stopping condition as they thought that ALL shapes would be subdivided if ANY shape had perimeter bigger than 1. However the question was intended as: in a particular iteration subdivide only those shapes whose perimeter is bigger than 1. Thus the process stops when all shapes have perimeter < 1. To avoid this confusion we modified the process to subdivide only the shape with the largest perimeter in a particular iteration. However this does not change the answer – you are free to use either process. Let me know if you have more questions regarding this.

3. Yes it is just like Shawn Kim said. If you start with a 10 by 10 rectangle then you end up with two 5 by 5 squares, four 2.5 by 2.5 squares and two 2.5 by 5 rectangles.

Edit: I had forgotten that I had modified the procedure to subdivide the shape with the largest perimeter in each iteration. The final answer will be the same as the earlier procedure where we simultaneously subdivided all the shapes with perimeter larger than 1. However, in light of this Ratchapong’s comment is the correct one, not Shawn Kim’s. Either processes are fine to use.

1. But I thought the question said “take the shape of largest perimeter (rectangle or square) and if this perimeter is larger than 1 apply this division procedure to this shape”. Doesn’t this mean that for each iteration there should be at most on division taking place? Your answer seem to suggest that the division take place for rectangle and 2 square at once. I’m just confuse with the word “largest”. Please clarify thank you!

2. I am also confuse about this. “take the shape of largest perimeter (rectangle or square) and if this perimeter is larger than 1 apply this division procedure to this shape; if the largest perimeter is less than or equal to 1 then stop”

The sentence apply THIS division procedure to THIS shape. Can you clarify on “THIS”. What I understood it be to is that.

If the largest perimeter happen to be the RECTANGLE then divide the RECTANGLE into 2 squares.

If the largest perimeter happen to be the SQUARE(S) then divide the SQUARE(S) into 3 parts.

Another interpretation is that

If there exist a largest perimeter, apply the division to ALL the shapes in the squarezo.

11. Jing: Your first interpretation was the correct one. A shape is subdivided only if its perimeter is bigger than 1. If it’s perimeter is smaller than 1 it is not subdivided again even though its neighbors might have perimeter larger than 1.

1. I’m working on it – I informed the Professor and there should be a submission area available shortly.

Edit: No submissions on T-Square, submit your solutions in class

2. I talked to Santosh, and the preferred way of submission is to submit printed copies in class. In case you have a compelling reason for why you cannot attend that particular class, you can email your submissions before the due date to either Santosh or me.

12. For 3(a):
(a) What is the total perimeter of all shapes obtained during this subdivision (including all intermediate shapes)? Write a recurrence for it.

Is it fine that I just get the recurrence? Do I need to solve the recurrence and get total perimeter in terms of N?

1. Is the function suppose to be very complicated? I am getting a very complicated function with MOD and ceiling function but it works for any input perimeter.

13. Hey, for number 3.c, are we supposed to coung the number of vertices in each recursive step or just at the end?

Does the area refer to the area of all rectangles within 1 iteration, or does it refer to the sum of all rectangles every produced from the beginning.

In the second scenario, a lot of area would be double counted. For example, a 1×1 city would be divided into 16 .25x.25 squares. Calculating the total area from the beginning yields an area of: 1. Or else, the area there would be 0 rectangles at the end.

1. 3b asks for the total area of all the rectangles in the final shape obtained after the procedure stops. However if you have already worked out the total area of all rectangles counted over all iterations, then that is fine as well.

15. The procedure for question 3 is a bit unclear to me. Do you divide all of the squares and rectangles and the order in which you do so is based on largest perimeter? Or do you only break up the shape of largest perimeter on every recurrence step?

1. Yes you need to analyze the running time of your algorithm. In general you cannot assume multiplying two $d$ digit numbers can be done in $O(1)$ time. You may assume either $\Theta(d^2)$ or $\Theta(d^{1.59})$ using the divide and conquer algorithm you saw in class.

2. Or if you can come up with a faster algorithm for multiplying two $d$ digit integers, you may use that as well.

16. So if we have a square with sides 1/3, when we divide it we get two smaller squares, and a rectangle. It is not a thing where if we have square and divide it in half, and both rectangles are equal to perimeter of 1 we stop, rather if it is square it always divides into 3 parts?

17. For 3c. Are suppose to be not double count the vertices the way we’re doing for the length? If a vertices is shared by multiple squares or rectangles should it only be counted once? Or is it just the number of shapes times 4?

18. For 1, does the worst case have to have O(n^2logn) or does just the average case have to be n^2logn?