Mathematics for the Analysis of Algorithms
Winter 2002, Mathematics 70.497B/70.590Y
School of Mathematics and Statistics,
Carleton University
Instructor: Daniel Panario
Office: #4372 HP,
Tel: (613) 520 2600 (Ext. 2159)
Email: daniel@math.carleton.ca
Lectures: Mondays 11:00 - 12:30, Thursdays 13:00 - 14:30. Room: HP 4369
Office hours: TBA
Current announcements
This space will be used for announcements. Check it regularly.
- Change of room: lectures will be on HP 4369.
General Information
- The general information handout for the course is in
text format.
- You can check a list of sites
of interest for the course. It includes homepages of analysis of
algorithms and data structures courses, applets, homepages of
researchers, etc.
- The tentative lecture schedule per month, as of
November 2001 (before classes start) is below.
The actual material covered in each lecture will be
updated during the course.
- Prerequisites:
Mathematical maturity is required; courses in analysis, algebra,
discrete mathematics, combinatorics and data structures are useful.
Courses like 69.384 and 70.385 would be appropriate prerequisites.
- Classes begin: Monday January 7, 2002.
Classes end: Monday April 1, 2002.
No lecture: February 18 - 22, 2002 (Winter break).
Remark: lectures of Thursday January 3 and Monday
April 1 will be taught at a different date (during March).
- Term mark:
There will be three assignments. The tentative schedule
of assignments is:
| Assignment | Hand-out Date | Due Date | Worth
|
|---|
| 1 | January 24 | February 25 | 15%
|
| 2 | February 25 | March 18 | 15%
|
| 3 | March 18 | April 10 | 15%
|
In addition to the assignments, there is a minor
project (deadline: Thursday March 7, 2002) and a
major project (deadline: Friday April 12, 2002),
together with an oral presentation (Tuesday April 16, 2002).
The deadlines for assignments and minor project
are not firm. Work handed-in some days after
the deadline will carry no penalties. However,
the student must agree with the lecturer on a
new deadline for the work.
- Evaluation:
| Workload component | Percentage
|
|---|
| 3 Assignments at 15% each | 45%
|
|---|
| Participation in class | 5%
|
|---|
| 1 Minor project (abstract) | 5%
|
|---|
| 1 Major project (10 pages) | 35%
|
|---|
| 1 Oral presentation | 10%
|
|---|
- Withdrawal:
The last day for withdrawal from the course is
March 8, 2002.
- Students with Disabilities:
Students with Disabilities who require academic accommodations
please feel free to see me, and contact the Paul Menton Centre
to complete the required forms.
- Some files may be in postcript format. If you don't have
a software to view postscript files, you may download a
ghostview software.
Lecture notes
There is no textbook for the course. We will take
material from several papers, and from the books
below. We intend to distribute notes of the lectures.
Most material is ready and will be distributed before
we teach the lecture covering that material. For the
remaining lectures we will ask some students attending
the course to type notes in LaTeX. The lecture notes
do not substitute the reading of the textbooks that
we strongly encourage (at the beginning of each
lecture or section we indicate from which text or
paper the material is taken).
The introductory weeks of the course are mostly taken from
An Introduction to the Analysis of Algorithms by
Robert Sedgewick and
Philippe
Flajolet. We also use several books by
Don Knuth,
most notably the bibles
The Art of Computer Programming,
but also
Concrete Mathematics, and
Mathematics for the Analysis of Algorithms.
We will also consider the recent book by
Wojciech Szpankowski,
"Average-case analysis of algorithms on sequences",
Wiley Interscience Series in Discrete Mathematics, 2001
The remainder of the course is taken from several papers and books.
Our main reference is the future book ``Analytic Combinatorics''
(in preparation) by
Philippe
Flajolet and Robert
Sedgewick. Some chapters of this book are available as technical
reports from
INRIA:
In this course, we extensively use the first two technical reports
and ocassionally the others.
Lectures per month
Contact Information:
Office Hours: TBA.
e-mail: daniel@math.carleton.ca