Lecture 07

Algorithm Design

What is an algorithm?:

Why is algorithm design important?:

fixing an algorithm is easier than fixing code
same reason why you make blueprints for a house before building it
by designing the entire algorithm before coding, you know ahead of time what to expect and can account for things that you wouldn't have though about
if you just start coding and find out later you needed to address new scenarios, then you have to go back to your code and put in "hacks", or quick changes that might not be the "correct" way of programming things
it is hard to think of every scenario beforehand, but thinking about the algorithm will at least flush out some things

How to design an algorithm?:

start from the top and then go down; top-down approach
- be generic
- fill in the details after all the major steps are laid out
- break the problem into smaller pieces
- tackle smaller pieces individually
start from the bottom and then go up; bottom-up approach
- start with a particular functionality
- code first and test code often
- add new functionality and code onto existing code
- grow the program to include more pieces and capabilities
in practice, it will be a mixture of these 2 approaches

An example algorithm for getting milk from the grocery store:

If you like to think in words:

start
  drive to the store
  buy the milk
  drive home
end

If you like to think in pictures:
The details that were left out:
- turn on the car
- take out your wallet
- etc.
The top-down approach would be to:
- break the task of "getting milk from the grocery store" into smaller pieces, like "drive to the store", etc.
The bottom-up approach would be to:
- develop the task of "drive to the store"
- after developing "drive to the store", "buy the milk" can be developed an added on