# Fundamental Algorithms

## Description

### Summary

CS 231 is an introduction to the design and analysis of fundamental algorithms.

General techniques covered:

- Divide-and-conquer algorithms
- Dynamic programming
- Greediness
- Probabilistic algorithms

Topics include:

- Sorting
- Searching
- Graph algorithms
- File compression
- NP-completeness

### Distributions

MM - Mathematical Modeling

### Prerequisits

CS 230 and either MATH 225 or permission of the instructor.

## Course Overview

The language of computer science is to a great extent the language of algorithms. Although there are many thousands of algorithms, there are relative few basic design techniques. These include: divide-and-conquer, greedy, dynamic programming, and backtracking. We will illustrate these techniques by studying a few fundamental algorithms of each type. In addition to helping us understand classic solution techniques, these algorithms have proven very useful in practice. Their names and the names of the problems they solve have become a standard part of the language of computer science.

Unfortunately, there is rarely a best algorithm to solve a given problem. Each approach involves a series of tradeoffs. Therefore, we will also study methods for evaluating the usefulness of an algorithm in a given situation. Among the various competing measures, we will focus primarily on the analysis of time and space complexity. However, a number of other issues will also be discussed.

## Required Textbook

Introduction to Algorithms (3rd Edition) by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein

Copies of the text are available in the college bookstore. This course is based on the 3rd edition of the book, but problems from the book will be written out on homeworks. You can choose to use the 2nd edition, but you do so at your own risk. If there is something in the 3rd edition that is not in the 2nd, you are expected to know it.