COMP251: Data
structures and algorithms
Fall 2007
Time: 
Tuesday
and Thursday from 10:00am to 11:30am 
Room: 
ENGTR
0060 (Trottier building) 


Instructor: 

Office: 
108N
McConnell 
Phone: 
3985491 
Office hours: 
Wednesday
from 8:30 to 10:30 
Email: 
Teaching
assistants:
Nicolas
Dutil (ndutil@cs.mcgill.ca)
Office hours: Monday 10:3012:30 in
McConnell 110
Weihuan
Shu (weihuan.shu@mail.mcgill.ca)
Office hours: Tuesday 2:304:30 in
McConnell 102
Summary
:
Design
and analysis of algorithms. Complexity of algorithms. Data structures. Introduction
to graph algorithms and their analysis. (3 credits)
Grading:
~5 homework assignments: 
35% 

25% 
Midterm exam: 
15% 
or 
0% 
Final exam: 
50% 

75% 
Course web page: http://www.cs.mcgill.ca/~patrick/cs251/2007A
Further materials, including a course discussion
area, can be accessed through the Web CT Vista system:
Visit http://www.mcgill.ca/mycourses and log in using your
McGill ID.
Topics and
readings lecture by lecture:
http://www.cs.mcgill.ca/~patrick/cs251/2007A/readings.html
Other
resources:
The indispensable course wiki: http://csus.cs.mcgill.ca/wiki/COMP251
Course page from fall 2006: http://www.cs.mcgill.ca/~patrick/cs251/2006A/index.html
In case you haven’t
heard:
Course
textbooks:
Recommended:
Algorithms
by Dasgupta, Papadimitriou and Vazirani
Required:
Introduction to Algorithms, 2/e
by
Cormen, Leiserson, Rivest and Stein
Available
free online from McGill or using VPN. Free registration required.
http://library.books24x7.com/toc.asp?bookid=3444
Chapters
whose contents you should already know:
I’ll be assuming you have
already learned these topics, so if your memory is a bit hazy, you may wish to
reread these chapters and try some of the exercises.
Chapter 1: The Role of Algorithms in Computing
Chapter 2: Getting Started
Chapter 3: Growth of Functions
Chapter 6: Heapsort
Chapter 10: Elementary Data Structures
Chapter 12: Binary Search Trees
Chapter 22: Elementary Graph Algorithms
Course content:
Data structures:
Hash
tables
Balanced
search trees (red black trees, Btrees)
Mergeable
heaps (binomial heaps, Fibonacci heaps)
Data
structures for disjoint sets
Algorithm analysis and design:
Analysis
techniques:
Solving
recurrences (a refresher)
Proving
correctness using loop invariants
Probabilistic
analysis
Amortized
analysis
Design
techniques:
Divide
and conquer
Greedy
algorithms
Dynamic
programming
Sorting
and related issues:
Analysis
of quicksort
Lower
bound for comparison sorting
Sorting
in linear time
Medians
and order statistics
Graph
algorithms:
Applications
of depthfirst search
Minimum
spanning trees
Shortest
path problems
Other
examples and applications:
Fast
Fourier Transform and polynomials
Matrix
multiplication
Intersections
of line segments
Closest
pair of points
Approximation
algorithm for the planar traveling salesman problem
Other
topics, timepermitting:
Number
theoretic algorithms
Intro
to quantum algorithms