What is "Analysis of Algorithms" ?

An Algorithm is a procedure for:

1. Computing something
2. Transforming a known input format in to an output with a known format

Note: An algorithm may proceed by a predetermined set of steps, or it may involve "random" steps such as a search.

So one tries to analyze via:

1. Worst-case
2. Average-case
3. Best-case

Why should I be interested in the material in this class?

1. It is required for graduation
2. What we learn is:
1. Algorithms
2. How to analyze them
   • running time
   • resource use (memory)

Examples:

I am working on a small database, but will soon use a much bigger database. How long will my queries take on this new system?

Disks, RAM, file systems, all storage is getting bigger! What is the best algorithm (or polyalgorithm) to do simple data access on these new large systems?

I am using RSA-based public-key cryptography. What key size will provide me with security for the next:

year?

5 years?

25 years?

250 years?

What tools do we need to analyze algorithms:

1. Notation for results "big oh", etc.
2. Price of operations: a model of computing, e.g. memory speed vs. computing speed?
3. Sophisticated ways to count the number of operations in an algorithm. These may be "exact' or "average" analysis.

Some definitions:

Algorithm: A well defined computational procedure that takes an input and produces an output.

Note: An algorithm is a specific way to solve a computational problem

Example:

This is a factoring of the integer n.

1. Sieve of Erestosthenes
2. Quadratic Sieve