Intro to 320

Intro

An algorithm is ...   a procedure (steps) to accomplish a task
  • It's the idea behind any program.
To be interesting (and worth developing) it should
Enjoy long(er)-term usage/reusage
that is, solve a well-specified PROBLEM versus a particular instance
What do we mean by "PROBLEM" versus instance? Consider our old friend sorting...
    Solving the well-specifed PROBLEM expressed as
    • Input: sequence of n keys a0, a1, a2, ... , an-1
    • Output: permutation of input sequence s.t. a'0 ≤ a'1 ≤ a'2 ... ≤ a'n-1

    Versus solving an instance of it, expressed as
    • Reverse alphabetize the students currently enrolled in 157 by their middle names, using "Fred" for those students without middle names. YUCK!
Algorithms developed to solve the sorting problem
Insertion,   Bubble,   Radix,   Quick,
Merge,   Bucket,   Heap,   Column,   ????      
How many are there?
How do you choose?
What are desirable properties?
How should we compare algorithms?
    Theoreticians tend to ignore implementation concerns...
    how "general" the problem instances are going to be
    how complex it is to write up the algm as code etc.
    SMOP, (-:

    Industry tends to ignore theory -- until things go very wrong.

    How could you not KNOW your code would break on really large problem sets with this set of characteristics? Did you TEST on TOY data sets ?!?

Take Home Lessons

  • Reasonable looking algorithms can easily be incorrect.

      Can often be dead wrong.

      Correctness is a property that must be demonstrated/proven.

        "It's obvious" never suffices.
        Neither does a demo on an instance.
      These were the naive 157 ways...but won't fly for the more sophisticated 320 student!

      We will differentiate between a good "heuristic" and a good "algorithm".

  • Algms can and should be understood & studied in a machine-independent way.

  • "big-Oh" notation & worst-case analysis simplify our ability to compare.

  • Holy Grail are algms w/ running times which grow logarithmically WRT input size.

      logB(n)  grows very slowly with increasing n
  • SINGLE MOST IMPORTANT STEP towards writing good algorithms is ...
          thinking in terms of well-defined DATA structures and (sub)algms (ie, methods/procedures).