The actual dates for tutorials will be
announced in class and under the "announcements" menu on the course web
page. Generally, these will be held every other week. (That
is, homeworks will typically be due on Fridays at noon, and there will
typically be tutorials on Tuesday and Wednesday of the weeks for
which homework is due on Friday.) The location
for the tutorials is: Stuart Biology Building, room S3/3 (S313). The
time is 6:05-7:25pm.
This course continues the work of COMP250 and COMP251.
It presents a number of fundamental algorithms, their applications,
and techniques for designing and evaluating them.
It also studies the issue of recognizing and dealing
with those problems that do not appear to have any efficient algorithmic
solution.
The approximate course contents are as follows: dynamic programming,
greedy algorithms, a review of elementary graph
algorithms including depth-first search and breadth-first
search (it is assumed this is familiar material for COMP 360 students),
the shortest path algorithms of Dijkstra, Bellman-Ford, and
Floyd-Warshall, network flows and the Ford-Fulkerson
method, a brief introduction to linear programming, problem
formulation and transformation, an introduction to
problems that appear to be computationally hard and
how to recognize them
(i.e., NP-completeness), and an introduction to
dealing with such problems (e.g., randomized algorithms,
fixed parameter tractability approaches,
approximation algorithms).
a grade of C or higher in course COMP-251;
Also, since COMP-251 has MATH-240 as a prerequsite, it
is expected that students will have already completed MATH-240
with a grade of C or higher.
There will be two mid-term exams (Oct. 7 and Nov. 4) and a final exam.
Your grade will be based on the following weighting of course work:
Homework 10% total for approximately 6 assignments,
Mid-terms 20% each, Final exam 50%
OR
Final exam 100%.
The higher of the two resulting marks will be taken as your final mark.
Homework assignments will count only minimally to the final grade. However, questions
very similar to assignment questions will appear on the mid-term and final exams.
Note: There will be no make-up midterms. The corresponding part
of the final exam will be weighted more to compensate for any missing
midterm mark (OR the final exam will count 100%, whichever gives the
better grade).
A detailed account of the process of converting a numerical mark to
a McGill letter grade can be found here.
As members of the McGill community, we value
the ideal of academic integrity, which basically
means that we respect ourselves and each other
as we go about our learning, teaching, and research.
In particular, this means understanding what
the rules for fair play in written work. In COMP-360,
you are encouraged to learn from each other,
to work on homework together, to consult the web if
your curiosity leads you there. What is not ok is
to present someone else's work as your own, to copy
something from another person or another source without
making it your own by understanding it and reformulating it
in your own terms. Midterm and Final exams are
closed book, closed notes, and consultation is
not permitted. Your mind is your only
resource. Make it a valuable one.
For CS majors, COMP-360 is required for
graduation and must passed with a C or better. If
you are planning to graduate in 2003-04, please
plan on satisfying this requirement the first
time around.
The course grade is based entirely on
actual achievement as measured on course
work. Personal situations such
as job offers, desire to graduate earlier,
avoid paying tuition an additional term,
etc., are not taken into account in arriving
at the course grade.
There is no extra work
that can be done to make up for a low mark. The
course can be retaken in Winter term, 2003-04, when
it will be offered again.
A supplemental exam will be given in May 2004.
The mark on the supplemental exam
replaces the entire course grade. However, there are
conditions (e.g., your course grade is below a C)
for taking this exam, a sign-up
procedure, and deadlines for signing up. See the
Calendar 2003-2004 for details.
Introduction
to Algorithms by Cormen, Leiserson, Rivest and Stein (2nd edition)
The first edition should also be okay to use, but chapter numbers and
page numbers will be different,
and some material covered in lecture may be missing. Guidance
will be given for cross-referencing the two editions.
Note that this is the same text that some sections of COMP-251 have used.
From McGill machines, the textbook can be accessed online. It is
one of the electronic books available in McGill's electronic library.
See the
list of available electronic books . In particular, see
the text
.
You are expected to attend class. Information
may be made available on the web for your convenience, but
is not a substitute
for class attendance. Should you miss a class, you are responsible for
finding out what material or announcements you may have missed.
The course is not structured for distance learning.