Introduction to Computer Algorithms

Spring 2005

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).

Course syllabus
Topics covered
Assignments

Course content

  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

topic location in CLRS read by
introduction [1] 1/18
insertion sort and loop invariant [2.1] 1/18
analysis of running time of insertion sort [2.2] 2/8
asymptotic notation and some math background [3] 2/8
mergesort; proof of correctness of the merge procedure using loop invariant; proof of correctness of mergesort using induction; analysis of O(n log n) worst-case running time of mergesort using recurrence [2.3] 2/10
recursive equations arising in analysis of divide and conquer algorithms and methods for solving them: substitution, recursion-tree and master method. [4.1,4.2,4.3] 2/22
quicksort; poof of correctness of partition function; proof of O(n2) running time of quicksort, and intuition for average case O(n log n); randomized quicksort [7 except for 7.4.2] 3/1
counting sort and radix sort [8.2, 8.3] 3/1
proof that any comparison sort has running time Omega(n log n) in the worst-case [8.1] 3/12
bucket sort and proof that its expected running time is O(n) when each element is equally likely to land into each bucket independently of other elements; use of indicator random variables in algorithm analysis [8.4] 3/12
dynamic programming technique for solving optimization problems and assembly-line scheduling as an example of the technique [15.1] 3/23
matrix chain multiplication [15.2] 4/4
longest common subsequence [15.4] 4/4
graph representation [22.1] 4/19
breadth-first search [22.2] 4/19
depth-first search [22.3] 4/22
topological sort [22.4] 4/30
minimum spanning tree algorithm of Kruskal [23] 4/30
Dijkstra's single source shortest path algorithm [24.2. 24.3] 4/30

Assignments

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  

Student project

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.