• Top-Down design and stepwise refinement

• What's the Problem?

• What's the Solution?

A Problem

• Given a set of points on a plain

  

  find a largest subset of collinear points.

What's a Solution?

• Writing down the problem practically describes the solution.

  int main()
  
    cout << 
      find-maximal-collinear-subset(
        read_points(std::cin))
  

• This is design by wishful thinking.

  • But you're your own genii.

Are We Done?

• Are we done? Have we solved the problem?

• It depends: where are read_points() and find-maximal-collinear-subset()?

  • Oh, darn.

  • But if they did exist, the problem's solved.

The Next Step

• There are now two problems to solve:

  1. find-maximal-collinear-subset()

  2. read_points()

• There are more of them, but they're each simpler than the original problem.

Make A Wish

• Let's look at find-maximal-collinear-subset().

• What's the problem?

  • Given a set of planar points, find a largest collinear subset.

  find-maximal-collinear-subset(pts)
    lcs = { }
    for each subset ss in pts
      if collinear(ss)  and  #ss > #lcs
        lcs = ss
    return lcs
  

Are We Done Now?

find-maximal-collinear-subset(pts)
  lcs = { }
  for each subset ss in pts
    if collinear(ss)  and  #ss > #lcs
      lcs = ss
  return lcs

• collinear() is a problem, as is generating subsets.

  • collinear() is a solved math problem.

  • Generating subsets is an unsolved problem.

Subsets

• What do we know about subsets?

  • S is a subset of S.

  • { } is a subset of S.

  • if S = {s} ∪ S', S' is a subset of S.

    • {1, 2, 3} = {1} ∪ {2, 3}

    • #S' < #S

Generating Subsets

generate-subsets(s)
  if s ≠ {}
    for each e in s
      s' = s - {e}
      generate-subsets(s')    

• But find-maximal-collinear-subset() used a for loop.

Revising The Design

find-maximal-collinear-subset(pts, lcs)
  if collinear(pts)
    lcs = pts
  else 
    for each e in pts
      pts' = pts - {e}
      generate-subsets(pts', lcs)    

• This seems to be the end of our design.

  • There are a few improvements available.

Pseudocode Design

• Hey! That's not C++!

  • There's no reason to use C++ on paper.

  • Pseudo-code's more productive.

    • It does have translation costs.

• Make up your own language as you go along.

  • Just remember you have to translate it.

• Too much freedom? Stick with simple subsets of a langauge you know.

Design

• Two main design problems: how to start, how to keep going.

• How to start - top-down design.

  • Start from the problem, work towards a solution.

  • You'll always have a problem to work on.

  • Why bother if you're not going to pay attention to the problem?

Stepwise Refinement

• Stepwise refinement is how to keep going.

  • Start with an abstract problem, end with a concrete problem.

  • Each step adds detail to the problem.

  • Solve the problem at each step.

  • The step-to-step solution changes should be small.

Design via Refinement

• Top-down design starts with the problem.

  • You'll always have a problem.

  • The problem can provide a lot of guidance.

• Start small, step small.

  • Abstract away almost all problem details.

  • Re-introduce abstracted details one at a time.

  • The solution changes in small, manageable steps.

Top-Down Design Advantages

• You always have a working system.

  • The initial solution works, but isn't useful.

  • Each step keeps a working solution, improves usefulness.

  • Test each step, add tests between steps.

Top-Down Design Problems

• Abstraction is hard; some people don't get it.

  • Usually your bosses, their bosses, and so on.

• Lots of decisions to make all the time.

  • And you have to remember them. And you have to fix them.

• Sometimes it seems like it never ends.

  • But, suddenly, it does.

• All of these things are skills you have to learn

What's the Problem?

• Input a point set,
  output a maximal collinear subset.

• That's it; that's the problem.

  • How many points?

    • Who cares? Worry about it later.

  • What happens if the points aren't coplanar?

    • Who cares? Worry about it later.

• Find and work on the essential details.

Abstraction

• Abstracting away almost all details leaves a simpler problem.

  • "Abstracting" means "delaying", not "forgetting".

  • The abstracted details are reintroduced one at a time.

Details

• What's a point set?

  • I dunno. A data structure. An object. Whatever.

  • It depends on what you want to do with it.

• How do I do point-set I-O?

  • This is not - should not be - a big problem.

• These questions have to be answered.

  • Just not right now; later.

Testing

• Your program should start out correct, and keep correct.

• Testing helps make sure that's the case.

• Develop a small set of tests along with your program.

  • Test your program after every step.

  • Shell programming or scripting languages and make are helpful.

Test Cases

• Simple tests do the trick.

  • Start off with the empty test.

• As you fill in details, add more tests relevent to the details.

  • Added point-set I-O? Add a test case consisting of one point.

  • Added collinearity? Add a test case consisting of two points.

• When you discover an error, always add a test case exposing the error.

Collinearity Revisited

• Points are collinear when

  • They lie on the same line, or

  • They all have the same angular measure from the same axis.

    

The Next Solution

find maximal collinear subset(points)
  max points = { }
  for p1 in points
    order points by increasing angle
    scan for similar angles
      similar angles mean collinear points
      remember the biggest set
  return max points

Other Design Techniques

• There are other approaches.

  • Bottom-up design.

    • Requires immense (or cliched) experience.

    • Easy to be led astray.

  • Object-oriented analysis.

    • Enormous overhead.

    • The design frequently becomes the problem.

Points to Remember

• Understand the problem.

• Consentrate on the most important parts of the problem.

• Once solved, move on to the next most important parts.

• Test every step of the way.