CSCI0180 Integrated Intro to CS Cetintemel

TBA

11:59 PM, Mar 19, 2008

Contents

    1  Amortized analysis

    2  Change We Can Believe In

    3  Rendering aligned translucent rectangles
        3.1  Structures
        3.2  Algorithm

Collaboration Policy

The course collaboration policy regarding exams is different than for other assignments. Specifically,

• You must work alone on this exam. If you have any questions, ask the TAs or the professor, but do not discuss any aspect of the exam with anyone else. You may visit the TAs or the professor on hours, or email questions to cs018tas@cs.brown.edu.

• Your work should be based solely on the course materials (i.e., lecture notes, homeworks, labs, and projects). Do not consult any other sources. Among others, do not consult the Web.

To receive a grade above 0 on the exam, abide by and sign the following statement, and hand it in to a TA before the due date!

All work on this exam is my own. I have not discussed the problems or their solutions with anyone except the course staff. I have not consulted any sources other than the course materials.
Login:     X   
Signature:     X   

Instructions

This exam is due on 11:59 PM, Mar 19, 2008.

As always, you should hand in your answers electronically. All of your code should be in one or more Java files. For questions that require prose, hand in an ASCII text file or a PDF. (If you want, you can hand in your analysis on paper to the CSCI 180 handin bin.)

Tips:

• Where appropriate, support your answers with (brief) explanations.

• All of your files related to the exam must be in your
  "/u/"<yourname>"/course/cs018" directory. If you put any files in "/u/"<yourname>"/", they may be readable by other students, in which case you are in violation of the collaboration policy.

• If you are asked to both write and analyze a procedure in a single problem, write the code in one file, and do the analysis in another.

• You are welcome to define and use any helper procedures you want. You are also welcome to use anything that’s been defined in any previous lecture or assignment.

• You may assume your procedures will only be called with valid input.

• Simplify your code, and make it as clean and efficient as you can.

• Show all your work!

1  Amortized analysis

Integer Street is the main commercial street in Mathtown. Little Johnny Euclid lives in the apartment building at 0 Integer Street. The addresses increase as you travel north (1,2,3,...) and decrease as you travel south (-1, -2, -3, ...).

Johnny wants to visit a store he’s heard about. He doesn’t know the name (or doesn’t have access to a phone book), so he plans to walk along Integer Street until he sees the shop.

Let n be the address (unknown to Johnny) of this store. If Johnny knew the sign of n, he would only have to walk |n| distance units to reach his the destination. Instead, he comes up with the following strategy:

He starts by walking north to 1 Integer Street. Assuming he hasn’t yet found the store, he walks south to -1 Integer Street, then north to 2 Integer Street, then south to -2 Integer Street, then north to 3 Integer Street, then south to -3 Integer Street, then north to 4 Integer Street, and so on, until he arrives at his destination.

Part A:

Using the strategy outlined above, how many units of distance must he travel? Give your answer in big-O notation as a function of n. (Define your variables!)

Part B:

Suppose Johnny changes to a doubling strategy for his search. First he walks north to 1 Integer Street, then south to -1 Integer Street, then north to 2, then south to -2, then north to 4, then south to -4, then north to 8, then south to -8, and so on¹.

Use the accounting method of amortized analysis to show that the distance Johnny would travel using the doubling strategy is O(n), where n is the store’s address. Show the actual and virtual costs of your operations and the credit you accumulate over time.

Hint: Consider an operation of the form “moving one unit closer to n”, which has a different cost depending on the location: assuming n is positive, if Johnny is at 3, then he can move north to 4 with constant cost. If he is at 4, he can move to 5 only after he walks south to -4 and then north to 4.

2  Change We Can Believe In

The coin-changing problem is as follows: You have at your disposal n different types of coins of denominations {a₁, a₂, ... a_n }, where a₁ < a₂ < ... < a_n and all the a_i’s are natural numbers. You’re now asked to give change for the amount C using the coins that you have. You get to use as many coins of each denomination as you want.

For a given amount, there could be more than one way in which we could make change (or it might be impossible). For example, if you had at your disposal coins of 1, 3, 17, and 18 cents, you could change 51 cents using two 18-cent coins and five 3-cent coins, for a total of seven coins. Or you could do the same with three 17 cent coins, for a total of three coins. (Note that a greedy strategy – always taking the highest-valued coin that you can – is not always optimal.)

Task: Write a Java class ChangeWeCanBelieveIn that has a static method getChange(int[] denominations, int value) where denominations is an array of positive integers representing all the various coin denominations, and value is a non-negative integer representing the amount for which you are trying to make change. The method should return an int, the minimum number of coins required to make change for value. This method should use dynamic programming. If it is not possible to find coins which total to value, your method should return -1.

Task: How much time does your program take to run on an input with n types of coins and an amount of money C? How much space does it take (i.e. how big is the table)?

3  Rendering aligned translucent rectangles

3.1  Structures

An XYPoint has two methods, double x() and double y(), and a constructor, XYPoint(double x, double y).

An AxisParallelRectangle is defined by two XYPoints, an upper left and a lower right. The x and y coordinates of the upper left are less than the x and y coordinates of the lower right, respectively². It has a constructor, and it has getters for the two XYPoints:

• AxisParallelRectangle(XYPoint upperLeft, XYPoint lowerRight)

• XYPoint upperLeft()

• XYPoint lowerRight()

In this problem, we will work on a way of rendering translucent rectangular filters on a display. We will use a convenient (but made-up) way of measuring the translucency/opacity, called opacity index. The opacity index of a filter is a nonnegative integer (A filter with opacity index zero lets through all the light). When you overlap some filters, the opacity index of the region of overlap is the sum of the opacity indices of the overlapping filters.

A TranslucentRectangle is an AxisParallelRectangle with an additional field, opacityIndex_, a nonnegative integer, and with an appropriate getter method (int opacityIndex()) and appropriate constructor. The constructor should make use of the superclass’s constructor.

Task: Code the classes XYPoint, AxisParallelRectangle, and TranslucentRectangle. You can use subclassing where appropriate. Note: You are not allowed to use classes from the Java libraries.

3.2  Algorithm

Next, you will think up and code an algorithm for processing an array of possibly overlapping TranslucentRectangles. The algorithm should produce an array of nonoverlapping³ TranslucentRectangles that would “look the same” as the input. The idea is that the result of the algorithm will be fed to a procedure that displays rectangles on the screen. The display procedure simply uses the opacity index to select a gray level. (Zero opacity index is displayed as white, and a higher opacity index leads to a darker shade of gray.) The display procedure is not capable of combining overlapping rectangles, so your algorithm must do that.

To make the problem easier, you should assume that the upperLefts of all rectangles in the input have the same y coordinate, and that the lowerRights all have the same y coordinate. Thus the top sides of all rectangles are aligned, and the bottom sides of all rectangles are aligned.

The specification of the algorithm is as follows.

• input: an array of TranslucentRectangles that differ only in the x coordinates of their upperLefts and lowerRights.

• output: an array of TranslucentRectangles that don’t overlap, except possibly at their boundaries, with the following property:

  The output rectangles correspond to regions where specific sets of input rectangles overlap, and the opacity index for each output rectangle is is the sum of the opacity indices of the input rectangles that overlap at that region.

Task: Develop and code an algorithm for the above problem. Your algorithm should ideally take time , where n is the number of rectangles.

We have supplied you with skeleton code for writing this algorithm in /course/cs018/src/midterm. Please feel free to add whatever code you like, but don’t modify the code we’ve already written for you and make sure the code you hand exactly matches the specifications we gave you at the beginning of this problem. You will lose points if you violate our specs.

We have also supplied you with a rectangle generator class, which you can use to test your algorithm. Your algorithm should be able to process a hundred thousand input rectangles within a short time.