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 be an two-dimensional array of integers. is sorted if each row is sorted and each column is sorted (in increasing order). Give an algorithm for sorting the entries of by swapping pairs of entries that runs in time .
- Give an algorithm to sort a list of numbers, where each number is or .
- Squarezo is a square-shaped city with perimeter kilometers. The city is divided into 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 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 apply this division procedure to this shape; if the largest perimeter is less than or equal to 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 and , give the fastest algorithm you can find to compute .