A Problem
- Given a set of points on a plain
find a largest subset of collinear points.
Big Ideas
- A big idea is an apparently important part of a problem or its
solution.
- "Apparently" because it might not be important.
- A problem's big ideas tend to lead to a solution's big ideas.
- But not always, particularly for hard problems.
Finding Big Ideas
- A big idea is a guess about what's important.
- Guesses can be wrong.
- Knowledge and experience make you a better guesser.
- A skilled professional is a good guesser.
Recognizing Big Ideas
- Big ideas are important, not trivialities.
- Letter case, white space, input format are not big ideas.
- They may be important details, however.
- Changing big ideas significantly changes the solution.
- If it can be easily changed, it's not a big idea.
- Thus do big ideas become trivialities.
- Letter case, white space, input format are not big ideas.
The Big Ideas
- What are this problem's big ideas?
- Collinearity? Planarity?
- There isn't much else.
- Which of these is important to the problem?
- Collinearity is what we want.
- Planarity is what we're given.
- Knowledge determines big ideas.
- Both long- and short- knowledge.
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.
- How many points?
- 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.
What's the 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.
Now what?
- Now what are the problems?
- 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.
The Next Problem
- What is
find_maximal_collinear_subset()?- This is a big problem; it has great influence on everything else.
- Time for another step. What's important?
- Maximality? Collinearity?
- Set cardinality is not important.
- Collinearity it is.
Collinearity
- What are the big ideas in collinearity?
- Any two points are collinear.
- Can we tell if a point's on a line?
- Make a wish.
bool collinear(pt, pt, pt)
- Make a wish.
The Next Solution
find maximal collinear subset(points)
max points = { }
for p1 in points
for p2 in points - p1
cpoints = { p1, p2 }
for p3 in points - cpoints
if collinear(p1, p2, p3)
cpoints += { p3 }
if #cpoints > #max points
max points = cpoints
return max points
Observations
- What remains is (should be) relatively simple.
- Hey! That's not C++!
- There's no reason to use C++ on paper.
- Pseudo-code's more productive than any language.
- It does have translation costs.
- O(n3) is expensive; can we do better?
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 frequency becomes the problem.
- Bottom-up design.
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.
| This page last modified on 31 January 2006. |
This work is covered by a |