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






-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)


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…

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

Go back to lecture menu

Go back to main page

Copyright © 1996 McGill University. All rights reserved.