introduction to algorithms and programing

introduction to algorithms and programing

1. Algorithms
an Introduction

2. History
•This course was first taught in the late 1960s
•The main principals that maintained the area
–Find algorithms that are fast for very large
inputs
–Assume a very simple model of a computer
–There are very fast and useful algorithms out
there for the finding.

3. Asymptotic Analysis
•We only care about the running time of our
algorithm as the size of the input goes to
infinity.

4. The RAM Computer Model
•The random-access-machine(RAM)
–Single processor
–Unit time addressable memory
–Unit time multiplication and addition of
numbers. ( log n bit numbers)

5. Amazing Algorithms
•Number Theory and cryptography
– Primes in P
•Linear programming and Business
•Computational Geometry and Graphic
•Graph Algorithms and
–Biology
–Internet
–Manufacturing

6. Skills Taught
•Proofs of Correctness
•Analysis of running times
•Decomposition of a larger problem
–E.g. using data structures
•Classifying different algorithms
•Abstract algorithm problem
•Search the literature
•Demonstrate negative answers