Advanced Programming I Lecture Notes

7 February 2006 • Assignment 1 Code Review

Outline

• The problem.

• Some solutions.

• Testing

• Results

• Observations

The Problem

• Non-big ideas.

  • The obstacle guard band.

    • Just expand the obstacle.

  • Overlapping obstacles.

    • Not an issue when using boolean matrices.

• Finding large rectangles seems to be a big idea.

Growing Rectangles

• Pick a square, grow a rectangle.

  

  • Do that for every unobstructed square.

• Remember the largest rectangle.

Obstacles to Growing

• A growing square splits into two rectangles when it hits an obstacle.

  

• Each rectangle grows in only one dimension.

Growing Pains

• Growing rectangles is moderately tricky.

  • The number of growing rectangles changes.

  • Introduces several special cases.

• Growing rectangles is expensive.

  • Worst case O(n⁴).

  • Exploiting knowledge is difficult.

Divide and Conquer

• A 1×1 yard is easy to solve.

• You can get 1×1 yard by repeatedly dividing larger yards.

  

Merging Yards

• Each rectangle in a divided yard is one of three types:

  No edge rectangles. Won't grow larger. One-edge rectangles. Two-edge rectangles.

• Divided edge rectangles have to be merged (maybe).

Divide and Conquer Problems

• Merging edge rectangles is complicated.

  • Much more complicated than growing rectangles.

• Yards may not divide nicely.

  • Pad to size with obstacles.

Rectangle Strips

• Rather than divide a yard into quarters, divide into halves.

  

• Merging strip by strip simplifies further.

  

Implementation

• Implementation is relatively simple.

  • A yard is an array of arrays (strips).

  • Simpler than a (dynamically-sized) matrix.

Testing

• Always test your code.

  • I'm going to.

• Tests don't have to be complicated.

Generic Tests

• Every assignment should pass these two tests:

  1. The empty-input test.

     $ ./pgm < /dev/null
     

     Programs should handle empty input.

  2. The garbage-input test.

     $ ./pgm < pgm
     

     Programs should handle garbage input.

• "Handle" means "not coredump."

Assignment Tests

• Two of the simplest: no obstacles and one big obstacle.

• Four of the next simplest: one 1×1 obstacle along each edge.

• Effective tests don't have to be complicated.

Test Results

	1	2	3	4	5	6	7	8
1
2
3
4
5
6

Coding

• Follow directions.

• Program Defensively.

• No coredumping.

Follow Directions

• Testing is automated; if you don't follow intput and output formats, the testing software gets confused.

  • And confused testing sofware doesn't grade well.

Follow Formats

• Assignment 1 output should not look like this:

  0 0 10 10
  

  not like this:

  
  Yard with obstructions marked.
   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 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 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 1 1
   1 1 1 1 1 1 1 1 1 1
   1 1 1 1 1 1 1 1 1 1
  Pool Size.
  0 0 1 1
  

Program Defensively

• Every program will be tested against garbage input.

  $ ./pgm < pgm
  

• Make sure your code can handle it.

  • "Handle" means "not coredumping."

• The answer to the question
  "Can input be like this...?"

  is "Yes."

No Coredumping

• A coredump is an unexpected, abnormal termination.

• Coredumping looks like this:

  
  ../../test-code: line 165: 10192 Segmentation fault ...
  
  ../../test-code: line 133: 10060 Killed ...
  

• It is easy to coredump programs in C++.

  • Particularaly when pointers are involved.

• It's your responsibility to make sure coredumps don't happen.

This page last modified on 8 February 2006.

This work is covered by a Creative Commons License.