COMP-252: Honours data structures and algorithms

Winter 2013

 Time: Tuesday and Thursday from 2:30pm-4:00pm Room: ENGTR 0070 (Trottier building) Instructor: Office: 108N McConnell Phone: 398-5491 Office hours: Wednesday from 10:00 to 12:00 Email:

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)

 ~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:

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

- Beautifully concise introduction that quickly explains the core insights.

Recommended: The Nature of Computation

by Moore and Mertens

-  “900+ pages of awesome” – Scott Aaronson

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.

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

Data structures:

Arrays

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:

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