COMP-252: Honours data structures and algorithms

Winter 2013

 

Time:

Tuesday and Thursday from 2:30pm-4:00pm

Room:

ENGTR 0070 (Trottier building)

Instructor:

Prof. Patrick Hayden

Office:

108N McConnell

Phone:

398-5491

Office hours:

Wednesday from 10:00 to 12:00

Email:

patrick@cs.mcgill.ca

 

Teaching assistants:

Omkar Deshmukh (omkar.deshmukh@mail.mcgill.ca)

Office hours Monday 2:00-4:00. Room TBA.


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/cs252/2013B

Further materials, including a course discussion area, can be accessed through myCourses.

 

Topics and readings lecture by lecture:

http://www.cs.mcgill.ca/~patrick/cs252.2013B/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 textbooks:

 

Required: Algorithm Design

         by Kleinberg and Tardos

            - A great book squarely focused on the course content. An amazing treasure trove of problems.

 

 

Recommended: Algorithms

by Dasgupta, Papadimitriou and Vazirani

- Beautifully concise introduction that quickly explains the core insights.

 

 

Recommended: The Nature of Computation

         by Moore and Mertens

            -  “900+ pages of awesome” – Scott Aaronson

 

Created with GIMP on a Mac

 

Recommended: Introduction to Algorithms, 2/e

by Cormen, Leiserson, Rivest and Stein

- Very dry but a good source for the material on data structures.

 

 

Available free online from McGill or using VPN. Free registration required.

http://library.books24x7.com/toc.asp?bookid=3444

 

 

Material you should already know:

Everything from Prof. Langer’s fall 2012 COMP-250 course:

                  Data structures:

                                    Arrays

Linked lists

                                    Stacks

                                    Queues

                                    Binary search trees

                                    Heaps

                                    Hash tables

                  Mathematical tools:

                                    Solving basic recurrences

                                    Asymptotic notation (big O and Omega, little o)

                  Algorithm design techniques:

                                    Divide and conquer

Sorting:

                                    Mergesort, quicksort, insertion sort, selection sort

                  Graphs:

                                    Adjacency matrix and adjacency list representations

                                    DFS and BFS traversal

 

 

Course content:

Data structures:

                                    Balanced search trees (treaps, 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)

                                                      Probabilistic analysis

                                                      Amortized analysis

                                    Design techniques:

                                                      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

                                                      Max-flow  / min-cut

                                    Other topics, time-permitting:

                                                      Approximation algorithm for the planar traveling salesman problem

                                                      Fast Fourier Transform and polynomials

                                                      Intro to quantum algorithms