taught by Grzegorz Malewicz
How to design an algorithm that solves a computational problem? What techniques can help you discover an efficient solution? The Introduction to Computer Algorithms course will present a range of techniques that algorithm designers can use when trying to develop an efficient algorithm for a computational problem. The techniques will be exemplified on many common computational problems. You will improve your understanding of course material by solving theoretical problems and implementing algorithms on a computer. The course will be fairly rigorous (i.e., theorems will be proven).
The text in square brackets refers to chapters and sections of the required textbook Cormen,
T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms (2nd
Edition). MIT Press (2001) book web
page Reading list

Date out  Problem statement  Due date 
1/18/05  H01.pdf  1/21/05 
2/3/05  H02.pdf  2/12/05 
2/17/05  H03.pdf  2/24/05 
2/26/05  H04.pdf  3/1/05 
3/3/05  01_midterm.pdf  
3/8/05  H05.pdf  3/14/05 
3/18/05  H06.pdf  3/23/05 
3/24/05  H07.pdf  4/4/05 
4/7/05  02_midterm.pdf  
4/7/05  H08.pdf  4/14/05 
4/18/05  H08_supplement.pdf  4/24/05 
4/19/05  H09.pdf  4/24/05 
5/2/05  01_final.pdf 
Each student was to implement five algorithms, evaluate their running time on inputs of different sizes and characteristics, and interpret the results of evaluation.
Here are results of one evaluation: average running time when sorting files each containing 100,000 numbers, when the number of inversions in a file grows as we proceed from left to right in the figures (files of type S* described here).
mergesort  randomized quicksort  insertionsort  bucketsort  radixsort 
Here is a student interpretation of results: interpretation.