Course: COMP 251B - Data Structures and Algorithms (3 credits, 3 hours)
Time & Place: Tuesday-Thursday 14:35-15:55 p.m. in Burnside Hall, Room 1B39
Instructor: Godfried Toussaint, Room 307, McConnell Hall, tel: 398-7077
Office hours: Tues & Thurs, 4:00-5:00
Teaching Assistants:

• Raphael Mannadiar, e-mail: raphael.mannadiar@mail.mcgill.ca; Office: McConnell, Room 202; Office Hours: Mondays 14:30 - 16:30.
• Robert West, e-mail: west@cs.mcgill.ca; tel: (514) 398-7071 ext: 00141; Office: McConnell, Room 111; Office Hours:  Thursdays 15:00 - 17:00.
• Dong Hyun (Ethan), e-mail: ethan@cs.mcgill.ca; tel: (514) 691-4973; Office: Duff (Bioinformatics), Room 332; Office Hours: Tuesdays 12:00 - 14:00.
• Omar Fawzi, e-mail: omar.fawzi@mail.mcgill.ca; tel: (514) 398-5485; Office: McConnell, Room 109; Office Hours: Wednesdays 09:00 - 11:00.

Method of evaluation:

• 2 in-class 75-minute exams counting 25% each for a total of 50%.
• 1 formal invigilated final exam counting 50%. If the final exam mark is higher than the mark of the in-class exams mark then the final course mark will be the final exam mark. Therefore the final exam may not only improve your mark but may do so considerably by erasing all your previous mistakes. Therefore, even if you fail the in-class-tests you can still obtain an A in the course by acing the final exam.
• There will be 6 homework practice assignments given during the term. The exams will contain problems similar to those in the practice assignments, and one problem on the exam will be exactly like one of the practice assignment problems. The TA's will give tutorial sessions on these assignments before each exam.
• All exams are closed-book. Overall numerical marks for the course will be scaled to obtain a reasonable distribution of A's and F's and converted to letter grades. There will be a supplemental exam counting 50%. Students with a mark of D, F, or J in the course will NOT be allowed to do additional work to upgrade their mark.

• Text Book: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
• In-class handouts (technical reports and reprints).
• Reading assignments of course material on the Course Web Page.

• Ancient and modern models of computation: rulers, compasses, toothpicks, Turing machines and random access machines. Proving the correctness of algorithms: induction proofs, direct proofs and proofs by contradiction. Fibonacci sequences and recursion. Solving recurrence relations. Computational complexity: big "O" notation, upper bounds, lower bounds, worst-case and expected complexity. Complexity classes. Linear data structures, trees and graphs. Binary search trees, maintaining balanced search trees and (2,4)-trees. Data compression, Huffman coding and Lempel-Ziv compression. Heaps and applications. Algorithms on strings and sequences. Dynamic programming. Linear assignment problems. Breadth-first search and depth-first search. Graph theory: minimum spanning trees, Voronoi diagrams, and other proximity graphs, graph coloring and the four-color theorem, planarity, isomorphism, Eulerian tours and Hamiltonian cycles. Tournaments. Data structures for graphs: adjacency matrices and adjacency lists. Selection and sorting algorithms. Heapsort, mergesort, quicksort and randomized quicksort. Bucket sorting. Linear-time median finding algorithm. Geometric searching methods: range search, nearest neighbor search, and closest-pair search. Algorithm design paradigms: divide and conquer, plane-sweep, greedy and prune-and-search. Geometric algorithms: point-location problems, polygon triangulation, convex hulls, diameter algorithms, and orthogonal line-segment intersection computation. Probabilistic algorithms. Approximation algorithms. The travelling salesman problem. The vertex-cover problem. The bin-packing problem. Applications to pattern recognition, bioinformatics, and music information retrieval.

• 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 www.mcgill.ca/integrity for more information).