SUNY Geneseo Department of Computer Science

Introduction

{Date}

CSci 240, Spring 2007
Prof. Doug Baldwin

(No Previous Lecture)

This is CSci 240, Foundations of Algorithms

Algorithms

What is an algorithm?

Process for solving some problem
- Specifiable in arbitrary detail
- Always produces a solution
Expressed as programs, English, electronics, etc.

Why study algorithms, by way of an example

Count the number of times each word appears in a document
n words in document
List: time to insert one word proportional to n
- Do this n times
- Total time proportional to n²
Tree: time to insert proportional to log₂n
- Do this n times
- Total time proportional to n logn
Theoretical difference in execution times turns in to 50 mS vs 100 for a short document, but 8 minutes vs 2.5 seconds for "War and Peace"

Some principles for designing algorithms

Read Section 2.2 and 2.3 up to but not including 2.3.2