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.

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)$ .
Give an algorithm to sort a list of numbers, where each number is $0, 1$ or $2$ .
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?
Given two positive integers $m$ and $n$ , give the fastest algorithm you can find to compute $m^n$ .

47 Comments

Farhan January 12, 2015 at 3:10 am

Should algorithms be written in pseudo-code?

Reply
svempala January 12, 2015 at 3:37 pm

Not necessary. But they should be clear, complete and readable.

Reply
William Agnew January 12, 2015 at 10:14 pm

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

Reply
Byung January 13, 2015 at 1:06 am

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?

Reply
aurkoroy January 13, 2015 at 4:30 pm

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.

Reply
P Eskind January 13, 2015 at 10:46 pm

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?

Reply
aurkoroy January 13, 2015 at 10:54 pm

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.

Reply
Michael Lane January 14, 2015 at 5:41 pm

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!

Reply
aurkoroy January 14, 2015 at 5:53 pm

Yes you have to state it for homework submissions as well. Check the Homework page for more details on the collaboration policy.

Reply
Ratchapong January 17, 2015 at 6:44 pm

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?

Reply
aurkoroy January 17, 2015 at 7:15 pm

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.

Reply
Ratchapong January 17, 2015 at 7:51 pm

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

Reply
Ratchapong January 17, 2015 at 8:49 pm

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?

Reply
1. Shawn Kim January 17, 2015 at 9:51 pm
  
  No it, on the second iteration you’ll end up with 2 big squares, 2 small rectangles, and 4 small squares.
  
  Reply
2. aurkoroy January 17, 2015 at 8:08 pm
  
  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.
  
  Reply
3. aurkoroy January 17, 2015 at 10:01 pm
  
  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.
  
  Reply
  1. Ratchapong January 17, 2015 at 7:55 pm
    
    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. Jing January 17, 2015 at 8:02 pm
    
    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.
aurkoroy January 17, 2015 at 8:12 pm

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.

Reply
Yongkoo January 18, 2015 at 6:15 pm

Where should we turn this homework in? T-square doesn’t have a submission area.

Reply
1. aurkoroy January 19, 2015 at 11:10 am
  
  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
  
  Reply
2. aurkoroy January 19, 2015 at 11:31 am
  
  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.
  
  Reply
Jing January 18, 2015 at 9:56 pm

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?

Reply
1. aurkoroy January 19, 2015 at 11:08 am
  
  It would be nice if you could solve the recurrence as well.
  
  Reply
  1. Ratchapong January 19, 2015 at 11:58 am
    
    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.
Shawn Kim January 18, 2015 at 10:03 pm

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

Reply
1. aurkoroy January 19, 2015 at 11:09 am
  
  Just at the end. Although if you counted the number of vertices in each step already, that is fine as well.
  
  Reply
Pranav January 19, 2015 at 1:42 pm

I had a question about 3b.
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.

Reply
1. aurkoroy January 20, 2015 at 9:39 am
  
  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.
  
  Reply
Dale Rivera January 19, 2015 at 10:52 pm

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?

Reply
1. aurkoroy January 20, 2015 at 9:37 am
  
  You just break up the shape of the largest perimeter in each iteration, hence your second interpretation is the correct one.
  
  Reply
Albert Shaw January 20, 2015 at 1:38 pm

In question 4, do we need to analyse the big O of the algorithm we make? If so can we assume multiply is O(1)?

Reply
1. aurkoroy January 20, 2015 at 3:39 pm
  
  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.
  
  Reply
2. aurkoroy January 20, 2015 at 3:41 pm
  
  Or if you can come up with a faster algorithm for multiplying two $d$ digit integers, you may use that as well.
  
  Reply
paideiaschool January 20, 2015 at 6:46 pm

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?

Reply
1. aurkoroy January 20, 2015 at 7:19 pm
  
  Yes a n by n square is always divided into 3 parts – 1 rectangle of size n by n/2 and 2 squares of size n/2 by n/2.
  
  Reply
Albert Shaw January 21, 2015 at 2:03 am

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?

Reply
1. aurkoroy January 21, 2015 at 10:24 am
  
  No, don’t double count any vertex.
  
  Reply
Albert Shaw January 21, 2015 at 3:37 am

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

Reply
1. P Eskind January 21, 2015 at 10:18 am
  
  Worst.
  
  Reply
2. aurkoroy January 21, 2015 at 10:23 am
  
  Unless stated explicitly, the complexity of an algorithm is usually measured in terms of its worst case behavior.
  
  Reply
Surya Bhamidipati January 21, 2015 at 10:37 am

Will you be posting the solutions to this HW before the midterm?

Reply
Jing January 21, 2015 at 6:14 pm

What will the test cover? will it cover today’s lecture?

Reply
1. aurkoroy January 21, 2015 at 6:43 pm
  
  No
  
  Reply
  1. Jing January 21, 2015 at 11:16 pm
    
    Are we allowed to bring cheatsheet?
  2. aurkoroy January 22, 2015 at 4:51 pm
    
    No, cheat sheets and calculators (or any other electronic devices) are not allowed.
2. P Eskind January 22, 2015 at 4:35 pm
  
  We probably won’t be allowed a cheat sheet, but it wouldn’t hurt to make one.
  
  Reply

CS3511 Algorithms Honors

HW 1

47 Comments

Leave a reply to P Eskind Cancel reply