Structures and Algorithms
"Not everything that can be counted counts, and not everything
that counts can be counted."
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:
Office hours: Tues & Thurs, 4:00-5:00
Course prerequisites: (1) COMP-250 or COMP 203.
Not open to students who have taken or are taking COMP 252. For
in the B.Eng. Program, credit will be
for only one of: COMP 431, COMP 251, COMP 360.
- Raphael Mannadiar, e-mail: firstname.lastname@example.org; Office:
McConnell, Room 202; Office Hours: Mondays
14:30 - 16:30.
- Robert West, e-mail: email@example.com; tel: (514) 398-7071 ext:
McConnell, Room 111; Office Hours: Thursdays
15:00 - 17:00.
- Dong Hyun (Ethan), e-mail: firstname.lastname@example.org; tel: (514)
691-4973; Office: Duff
(Bioinformatics), Room 332; Office Hours: Tuesdays
12:00 - 14:00.
- Omar Fawzi, e-mail: email@example.com;
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
mark is higher than the mark of the in-class exams mark then
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
previous mistakes. Therefore, even if you fail the in-class-tests you
still obtain an A in the course by
acing the final exam.
- There will be 6 homework practice assignments given during the
exams will contain problems similar to those in the practice
and one problem on the exam will be exactly
like one of the practice assignment problems. The TA's will give
sessions on these assignments before each exam.
- All exams are closed-book.
marks for the course will be scaled to obtain a
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
- 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
- Ancient and modern models of computation: rulers, compasses,
Turing machines and random access machines. Proving the correctness of
algorithms: induction proofs, direct proofs and proofs by
Fibonacci sequences and recursion. Solving recurrence relations.
complexity: big "O" notation, upper bounds, lower bounds, worst-case
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
Heaps and applications. Algorithms on strings and sequences. Dynamic
Linear assignment problems. Breadth-first search and depth-first
Graph theory: minimum spanning trees, Voronoi diagrams, and other
graphs, graph coloring and the four-color theorem, planarity,
Eulerian tours and Hamiltonian cycles. Tournaments. Data structures for
graphs: adjacency matrices and adjacency lists. Selection and sorting
Heapsort, mergesort, quicksort and randomized quicksort. Bucket
Linear-time median finding algorithm. Geometric searching methods:
search, nearest neighbor search, and closest-pair search. Algorithm
paradigms: divide and conquer, plane-sweep, greedy and
Geometric algorithms: point-location problems, polygon triangulation,
hulls, diameter algorithms, and orthogonal line-segment intersection
Probabilistic algorithms. Approximation algorithms. The travelling
problem. The vertex-cover problem. The bin-packing problem.
to pattern recognition, bioinformatics, and music information retrieval.
- McGill University values academic
Therefore all students must understand the meaning and consequences of
cheating, plagiarism and other academic offences under the Code of
Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for