Analysis and design of algorithms: an overview

• the study of algorithms = Algorithmics
• Problem
• Six categories of problem
• Model
• Algorithm
• History
• Examples

the study of algorithms = Algorithmics

software   hardware
==============
algorithmics

We didn't yet define what is algorithm.  We begin with equating "program" with "algorithm" and ask "how to predict how long it take a program to run?".  This question is the essence of analysis in algorithmics.

problem size vs effort to get a solution

Now we will define algorithms informally "algorithms":  step-by-step procedure for solving a problem.  According to Oxford dictionary "algorithm": a process or set of rules used for calculation or problem-solving, esp. with a computer.

Plan:
1 build abstract model (model talks about problem, decide different soln)
2 design algorithm within model
3 analyse
    algorithm  for -> upper bound
    problem for ->  lower bound

upper bound:  the work sufficient to solve problem within model
lower bound:  the work necessary to solve problem within model

4 compare upper/lower bound
4.1  change algorithm
4.2  find better lower bound
4.3  change model
4.4  change problem
 

Problem

2)  characterization of desired outputs as a function of inputs

1 + 2 is Problem
 

any legal input
    |
    v
algorithm A
    |
    v
desired output

is solution

analysis needs mathematics
mathematics needs critical thinking

Mathematics forces us to identify our assumptions and so deal with the unusual.  As a collorary, we shouldn't be surprised if we derive counter intuitive results using mathematics; in a way, that's what it's for.

Obviousness is always the enemy of correctness, B. Russell

Six categories of problem  :

1  search problem: find X in an input satisfying P
2  structuring problem : transform input to satisfy P
3  construction problem:  build X satisfying P
4  optimization problem: find the best X satisfying P
5  decision problem: decide whether the input satisfies P
6  adaptive problem: maintain P over time (OS, control, server...)

Problem categorizes by difficulty
1  conceptually hard
2  analytically hard
3  computationally hard
4  computationally unsolvable

Artificial Intelligence studies   1,2
the field of complexity studies  2,3
the field of computability  studies 3,4

Model

Algorithm:

Algorithm for algorithm design :-)

if the upper bound and lower bounds match
then stop
else if they are close enough of the problem is not that important
  then stop
  else if the model focuses on the wrong thing
    then restate it
    else if the algorithm is too fat
      then generate a slimmer algorithm
      else if the lower bound is too weak
        then generate a stronger lower bound
repeat to perfection or exhaustion

Good judgment comes from experience,
and experience comes from bad judgment.
      Barry LePatner

History

9th century Persian, Mohammed al-Khowarizmi, rules for + - * /
written in latin becomes  "Algorismus"  -> Algorithm

1801  Josep Jacquard, machines
1833  Charles Babbage, difference engine, analytical engine
1890  Herman Hollerith, tabulating machine for US national cencus
1940  general purpose computer
1920  IBM
1940  Association of Computing Machinery ACM
1968  ACM curriculum on computer science
 

Examples of problem

PUZZLE(x)

while x != 1
    if x is even
     then  x = x / 2
     else x = 3x + 1

Sample run:  7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

2) Four-color problem

formulate 1852 solved in 1976 by
K.I. Appel and W. Haken, "Every planar map is four colorable", Bull. Amer. Math. Soc. 82(1976) pp.711-712.

Two parts of the proof:
1) use mathematical reasoning to reduce the general problem into a finite set of special cases (approx. 1700 cases)
2) write computer program to find 4-color for all of those special cases.

QED (quod erat demonstrandum)

Philosophical question:  Can mathematical truth be relied on the correctness of software?

A detailed story of solving four-color problem can be found in :  T. Saaty and P. Kainen, "the four color problem: Assualts and conquest", Dover pub. NY, 1986.
(I remember there is one in the library of our department of mathematics)

Bibliography

last update 5 June 2002