Data Structures & Algorithms Lecture Notes

20 November 2008 • Assignment 1b Code Review

Outline

• The problem.

• Testing

• Coding observations.

The Problem

• Water flows downhill, filling up the vallies.

• Some volume of rain falls on the landscape.

  • What percentage of the vallies are underwater?

  • What's the water level?

Simple Examples

• When understanding a problem, consider the simple instances.

• A simple instance: 1 1 1 1.

  • 100 m² plot, 1 m³ of rain.

• And the answer is?

  • 100% of the squares underwater.

  • water level is 1 m³ rain/100 m² = 0.01 m + 1

Even Simpler

• An even simpler instance: 1 1 1 0.

  • No rain falls on a single square.

• Simple, right? But...

  *** 1 1 1 0 test.
  
  ??? Percentage underwater was 1.00, 
  ??? should have been 0.0.
  
  *** 1 1 1 0 test.
  
  ??? Output expected from std-out, 
  ??? none produced.

Further Examples

• Slightly more complicated: 1 2 1 2 1.

  • Two squares, one one meter higher than the other.

  • One cubic meter of rain.

• Same answer as before, except only 50% of the squares are underwater.

• What about 1 2 1 2 100?

  • 100 cubic meters of rain fall.

A Complicated Case

• 100 m³ fills a 100 m² square to one meter.

  • Water level is 1 + 1 = 2 m.

• How many squares are underwater?

  • The one meter square is, 1 m under.

  • The two meter square is at the water level, not under it.

  • 50% of the squares are underwater.

More Explorations

• Next up: 1 2 1 2 200; double the rain.

• 100 m³ of fills the 1-m square to 1 m.

  • The 2 m square is now at the water level.

• The remaining 100 m³ of rain falls on the two squares

  • 100 m³/200 m² = 0.5 m.

• Both squares are under water (100%), the water level is 1 + 1 + 0.5 = 2.5 m.

First Algorithm

• It seems the algorithm is at least

  1. Start at the lowest elevated square(s).

  2. Rain enough to raise the water level to the nearest higher elevation.

  3. Repeat 2 until the rain runs out or the squares do.

  4. Print the water level and the underwater percentage.

Extensions

• 1 × n regions seem to work; what about m × n regions?

  • Given the magically flowing water, does it matter?

  • Not really; the nearest higher elevation is the same no matter where it is.

• But for large regions, finding the nearest higher elevation could be expensive.

  • “Expensive” = O(n²).

Enter Sorting

• The magic flowing water allows us to re-arrange the squares to make finding the nearest higher elevation simple.

  • Sort the squares by increasing elevation.

  • This takes O(n) (worst case bucket sort) or O(n log n) (average case quicksort) work.

  • Finding the nearest higher elevation now takes O(n) work.

• Do a little work up front to save some work later.

Testing

• Three test sets:

  1. The Assignment 1a test set.

  2. My simple test set for Assignment 1b.

  3. Big tests for timing.

1A Tests

• The same tests as in Assignment 1a:

  1 1 1 1
  -1 1 1 1
  1 -1 1 1
  1 1 -1 1
  1 1 1 -1
  1 1 1
  1 1
  1
  30x100 region
  

• Nobody passed the Assigment 1a tests.

1B Tests

• Tests I created in understanding and writing my solution.

  1 1 1 0
  1 1 0 100
  1 2 0 2 100
  2 2 0 2 2 2 100
  2 2 0 2 2 0 100
  2 2 0 0 2 0 100
  2 2 2 2 2 2 100
  3 3 25 37 45 51 12 34 94 83 27 10000

• The last test is from the assignment page.

  • Almost everybody got it right.

Timing Tests

• A 500,000 square problem instance.

  • big.1 in the assignment directory.

• A 1,000,000 square problem instance.

  • big.2 in the assignment directory.

• Many programs did well on the timing, but produced incorrect results.

  • Fast wrong code is useless.

Don't Copy Code

I saw a lot of this:

int main()
  unsigned cnt, rainfall;
  int
   * elevations = 0,
     rv = EXIT_SUCCESS;

  try
    // blah blah
  catch (std::string emsg)
    std::cerr << "!!! " << emsg << ".\n";
    rv = EXIT_FAILURE;
    delete [] elevations;
    exit(rv);

  // compute_waterLevel(*elevations, cnt);

  return 0;

Write Your Own Code

• Cutting and pasting is not programming.

  • And will not be accepted as programming.

• Your code is talking about you.

  • Make sure it's complimentary.

Bubble Sorting

• Know your sorts.

  • Bubble sort isn't going to cut it on a 500,000 square region.

    *** 500,000 timing test test.
    
    ??? Unexpected output from std-err (between --):
    --
    ../../test-code: line 230:  5422 Killed  ./$pgm
    --
    

  • 60 cpu seconds should be more than enough to solve this problem.

Follow Directions

• You aren't going anywhere if you can't follow directions.

  *** 2 2 0 0 2 0 100 test.
  
  ??? Unexpected Percentage underwater format, expecting 0.33.
  ??? "0.333333"
  
  *** 2 2 2 2 2 2 100 test.
  
  ??? Unexpected Percentage underwater format, expecting 2.25.
  ??? "4.87394e-270"

• Testing programs are unforgiving.