COMP-251: Data structures and algorithms

Fall 2006

 

Time:

Tuesday and Thursday from 10:00am to 11:30am

Room:

ENGTR 0060 (Trottier building)

 

Instructor:

Prof. Patrick Hayden

Office:

108N McConnell

Phone:

398-5491

Office hours:

Wednesday from 8:30 to 10:30

Email:

patrick@cs.mcgill.ca

 

Teaching assistants:

Simon-Pierre Desrosiers (office hours: Mondays 10am-12pm in MC235)

Ethan Kim (office hours: Fridays 1pm-3pm in MC 305)


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

Further materials, including a course discussion area, can be accessed through the Web CT Vista system:

Visit http://www.mcgill.ca/webct and log in using your McGill ID.

 

Topics and readings lecture by lecture:

http://www.cs.mcgill.ca/~patrick/cs251/readings.html

 

In case you havenít heard:

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures. (See http://www.mcgill.ca/integrity for more information.)

 


Course textbook:

 

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, B-trees)

††††††††††††††††††††††† 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 depth-first 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, time-permitting:

††††††††††††††††††††††††††††††††††† Number theoretic algorithms

††††††††††††††††††††††††††††††††††† Intro to quantum algorithms