Mathematics for the Analysis of Algorithms
Fall 2003, Mathematics 5805
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: Tuesdays and Thursdays 2:30 - 4:00. Room: HP 4369
Office hours: Tuesdays and Thursdays 1:30 - 2:30.
Current announcements
This space will be used for announcements. Check it regularly.
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
August 2003 (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: Thursday September 4, 2003.
Classes end: Monday December 1, 2003.
- Term mark:
There will be four assignments. The tentative schedule
of assignments is:
| Assignment | Hand-out Date | Due Date | Worth
|
|---|
| 1 | September 23 | October 9 | 12.5%
|
| 2 | October 9 | October 28 | 12.5%
|
| 3 | October 28 | November 13 | 12.5%
|
| 4 | November 13 | November 27 | 12.5%
|
In addition to the assignments, there is a minor
project (deadline: Tuesday November 4, 2003) and a
major project (deadline: Friday December 12, 2003),
together with an oral presentation (on the week
of December 15-19, 2003).
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
|
|---|
| 4 Assignments at 15% each | 50%
|
|---|
| 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
November 7, 2003.
- 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.
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 book by
Wojciech Szpankowski,
"Average-case analysis of algorithms on sequences".
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: Tuesdays and Thursdays 1:30 - 2:30.
e-mail: daniel@math.carleton.ca