Data
Structures and Algorithms
COMP
251B
"Not everything that can be counted counts, and not everything
that counts can be counted."
Albert Einstein
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.
Course prerequisites: (1) COMP-250 or COMP 203.
Restrictions:
Not open to students who have taken or are taking COMP 252. For
students
in the B.Eng. Program, credit will be
given
for only one of: COMP 431, COMP 251, COMP 360.
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.
Course materials:
- 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.
Course Outline:
- 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.
Reminder:
- 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).