COMP271 Design and Analysis of Algorithms
Fall 2004, Section L1
Announcement: (Previous announcements )
The final exam will be held on 20 December 2004, 8:30-11:30am, at LT B.
Course Overview:
This course presents the fundamental techniques for designing
efficient computer algorithms, proving their correctness, and
analyzing their running times. General topics include review of
asymptotics, mathematical analysis of algorithms (summations and
recurrences), algorithm design techniques (such as
divide-and-conquer, depth-first search, dynamic programming, and
greedy algorithms), graph algorithms (breadth-first and depth first
search, biconnectivity, minimum spanning trees, shortest paths),
NP-completeness and approximation algorithms.
Textbook
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to
Algorithms, Second Edition, McGraw Hill and MIT Press, 2001.
References
(1) Jon Bentley: Programming Pearls (2nd ed).
Addison-Wesley, 2000.
(2) Michael R. Garey & David S. Johnson:
Computers and intractability: a guide to the theory of NP-completeness.
W. H. Freeman, 1979.
(3) Robert Sedgewick, Algorithms in C / Algorithms in C++ (3rd ed).
Addison-Wesley.
Course Work:
Course work will consist of 4 homework assignments,
a midterm and a comprehensive final. Homeworks are to be
turned in by the start of class on the due date. No late
homeworks will be accepted. (So turn in what you have by
the start of class.) In exceptional circumstances (illness, university
business, or religious observances) extensions may be granted.
However, all extensions must be approved by me
before the due date.
You must solve all the problems on the written assignments; however,
only a few of the assigned problems (the same for everyone) will
actually be graded by the TAs.
The primary benefit to working on homeworks is in preparation for
the exams, because exam questions are often variants of homework
problems. For this reason I encourage you to spend time alone
thinking about each problem and your approach in solving it. You
are allowed to and encouraged to discuss homework
problems with your classmates. However, you must write
up the solutions on your own. In particular:
- Homework solutions must be written in your own words (not
copied or modified from someone else's write-up).
- You must understand your solution and its derivation. (I
may ask you to explain your solution to me.)
- You must acknowledge your collaborators (whether or not they
are classmates) or any other outside sources on each homework.
Failing to do any of these will be considered plagiarism, and may
result in a failing grade in the course and notification for
appropriate disciplinary action.
As a courtesy to the graders, homeworks should be written
neatly. Poorly written work will not be graded.
When writing algorithms be sure not only that your solution is
correct, but also that it is easy for the grader to understand why
your solution is correct. Part of your grade will be based not only
on correctness, but also on the clarity, simplicity, and
elegance of your solution.
Classroom conduct
Assignment/Midterm Schedule:
|
Assignment 1 | Out on Sep , 2004
| Due on Oct , 2004 |
|
Assignment 2 | Out on Oct , 2004 | Due on Oct , 2004 |
|
Midterm | | Sat, 30 Oct 2004, 2-4 pm |
|
Assignment 3 | Out on Nov , 2004 | Due on Nov , 2004 |
|
Assignment 4 | Out on Nov , 2004 | Due on Dec , 2004
|
Grading
|
4 assignments | 5% each |
|
Midterm | 35% |
|
Final | 45% |
No make-ups will be given for midterm and final unless prior approval
is granted by the instructor, or you are in unfavorable medical condition
with physician's documentation on the day of the examination. In
addition, being absent at the final examination results in automatic failure
of the course according to university regulations, unless prior approval
is obtained from the department head.
Lectures
|
| Days |
Time |
Room |
| Tue & Thu |
10:30 - 11:50 |
Room 2465 |
|
Tutorials
|
| Section |
Day |
Time |
Room |
TA |
| 1A |
Fri |
14:00 - 14:50 |
1511 |
Oscar Au |
| 1B |
Fri |
15:00 - 15:50 |
1511 |
Desmond Tsoi |
| 1C |
Fri |
16:00 - 16:50 |
1511 |
Kimo Lai |
|