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