Introduction to Computer Algorithms

Fall 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

  See the compiled 100 pages of algorithms lecture notes.

Assignments

 
Date out Problem statement Due date
8/26/05 H01.pdf 9/2/05
9/17/05 H02.pdf 9/22/05
9/27/05 H03.pdf 10/03/05
10/7/05 01_midterm.pdf  
10/9/05 H04.pdf 10/14/05
10/26/05 H05.pdf 11/2/05
11/1/05 H06.pdf 11/9/05
11/13/05 H07.pdf 11/16/05
11/15/05 Project.pdf 12/1/05
11/18/05 02_midterm.pdf  
11/30/05 H08.pdf 12/4/05
12/12/05 01_final.pdf  

Competition results

Undergraduates implemented external memory algorithm for computing Google's PageRank. Students were given parts of real web graph resulting from crawls of the web, including graphs of the following domains:

and "artificial" graphs

Here are running times in seconds of 14 students' algorithms each iterating PageRank 10 times for the graph graph_0xfff.zip using at most 100KB of memory on a P1.8GHz processor. The file *.bin is an adjacency list representation of the graph; details on the format are here.