Lesson 20 - Learning Goals

20.1 Introduction to Algorithms

20.2 Different types of algorithms

20.3 Metrics to measure algorithmic performance

20.4 Learn about the Big-O notation

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:

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…

Algorithm Programs and Examples

There are several program examples for each type of algorithm discussed in lectures, including output and input files, in FORTRAN 90, PASCAL and C. These are found on:

The disk which accompanies the FORTRAN 90 book

This INTERNET web site - Link to Program selection page