LECTURE 20

Algorithm = Method, technique, paradigm to solve a problem.

Analysis of Algorithms

Measure

Performance

Speed

Space

Accuracy

-use Order Notation

O(n)	10 100 1E6
O(n log n)	~30
O(n2)	100 1E6 1E12

Classification of Algorithms

1. Numerical e.g. numerical integration
2. Non-Numerical e.g. sorting, searching
   

Types of Algorithms

1. Direct Computation (e.g. Income Tax)
2. Enumeration (e.g. Sequential Search)
3. Divide and Conquer (e.g. Binary Search)
4. Iteration (e.g. Series and Taylor Expansions)
5. Trial & Error (e.g. Newton Raphson)
6. Simulation (using Random Number Generators)
   
   

Problem:

Given 9 cookies

and 4 paper bags
Required to place an odd number of cookies in each bag.

Note: All cookies to be used (none eaten!)

1. Simulation

2. Enumeration - list all cases

3. Theoretical Approach

4. Creative Solution

Many more solutions…