CSC 108H - Assignment 8

University of Toronto - Fall 2001
Department of Computer Science

Assignment 8

Due: Friday December 7 at 9:00 a.m.

You will be handing this assignment in on paper. St.George students will put their assignments in the drop box marked "CSC108" which is located on the second floor of the Sandford Fleming Building just inside the entry to the bridge across to the Pratt building. The bridge entry is beside the elevators in the south-east corner of the building. The drop box will not be available until Monday Dec. 3.

The drop boxes are now available. There are two drop boxes in the bottom row labelled CSC108.

Mississauga students will put their assignments in the drop boxes marked "CSC108" which are located on the north wall of the South Building Computer Centre in room 2045. These boxes are accessible 24 hours per day.

Part 1: Inheritance

You will demonstrate your understanding of inheritance by adding comments after each line of the main method of class IE. Your comments will describe the sequence of events that takes place as a result of executing the line.

You must either print the file IE.java and add your comments in pen or if you wish to add comments at the computer before printing, you must 1) not change anything in the code of IE.java and 2) highlight the comments you add using a highlighter. If your comments are not distinguishable from the program, they will not be marked.

For each method call (including constructors) in the main method of IE
- If the method call will not cause an error then
  1. list sequence of method calls that results, explaining why each occurs by referring to the rules
  2. list any changes to any instances that result from the method call.
  3. describe anything that is printed as a result of the method call.
- If the method call would cause an error (either at compile time or at runtime)
  1. comment out the line.
  2. explain when (at compile time or runtime) and why (making reference to the rules) the error would occur.
For each assignment statement in the main method of IE
- If the assignment statement will not cause an error
  1. explain why the assignment is allowed (make reference to the rules)
- If the assignment statement will cause an error
  1. comment out the line
  2. explain when (compile time or runtime) and why (again making reference to the rules) the error would occur.

Corrected line numbers Please fill in the comments for lines 3,8,10,12,13,14,18,20,24,26,

Part 2: Running Times

This exercise will give you some experience with estimating the running time for an algorithm as well as a feel for the time implications of algorithms of different complexities. In each of the algorithms implemented in Q.java the parameter n represents the size of the input to the algorithm. You can also think of n as the size of the problem to be solved by the algorithm. An algorithm A has a lower complexity than algorithm B if A can solve a bigger problem than B in the same amount of time.

You will modify the main method of Q.java to create objects of each of the classes Linear, Quadratic, NlogNTime in Q.java, and run the testIt method for each object with different arguments. You will not hand in your modified Q.java program.

Find values for n such that the average running time is approximately 100ms, 250ms, 500ms, and 1000 ms respectively. You should be able to narrow down these values quite quickly. Do not run anything else on your computer while doing the timings. Also run all tests on the same computer. The actual times measured should be within 10% of the approximate times given above. I.e., if you find a value for n that leads to a running time for one of the methods of 940ms, that is close enough to 1000 ms.
List your results in a table consisting of the input and the amount of time taken by the method on that input. An example table shows the format your table should have.
Now that we have measured the running time for a small set of input sizes, we can estimate how long it would take to run each method given much larger input values. The running times for each of the methods can be characterized by the equations given in the methods comment.
1. For method linearTime, choose 2 points from your table, and substitute them into the general equation An+B=runningTime. You will end up with 2 equations in 2 unknowns. Solve for A and B. Show your work.
2. Do the same for method nlognTime, but this time you need only pick 1 point giving rise to only 1 equation in 1 unknown. Show your work
3. Finally do the same for the method quadraticTime. This time you will need 3 points, giving rise to 3 equations in 3 unknowns. Show your work
Use the equations you arrived at in the previous part to estimate the running time in days for each of the methods when n=98000. Show your work.

To help you along with this assignment, I have done the cubicTime method myself, though I have not shown all my work.

Note: You can't really compare my results for cubicTime with yours since I ran this on an Pentium III 860MHz (probably not the same computer you are going to be working on).

What to hand in

Cover page
A completed cover page
Inheritance
Hand in your commented copy of class IE (make sure you commented lines 3,8,10,12,13,14,18,20,24,26 .)
Note: Your comments must be easy to read and distinguishable from the original program. Comments must either be written in pen or if they are written at the the computer they must be hightlighted. If you don't do this, the TAs can refuse to mark your assignment.
Running times
1. A table showing the times for each of the methods linearTime, quadraticTime, nlognTime
2. 3 equations, 1 for each of the methods (make sure you include your work)
3. Estimates of the running times for the methods when given input n=98000 (again make sure you include your work)

What we will mark

We may choose to mark a subset of what you hand in. We won't say which questions or parts of questions we will mark. For full credit you should do all parts correctly.