Computer Science 3711:
Algorithms and Complexity
(Fall 2005)

http://www.cs.mun.ca/~harold/Courses/CS3711

Instructor	Office	Office Hours	Lectures
Todd Wareham harold@cs.mun.ca	EN-2034 737-4601	TBA	MWF, 4:00-4:50 pm, EN-1051

Prerequisites

CS 2711 and CS 2741

Lecture Outline (Tentative)

• Basic Concepts (Problems; Algorithms; Asymptotic Worst-Case Time Complexity; Recursive algorithms; Recurrences; Summations) (7 lectures) [Chapters 1-4 and Appendix A, Textbook]
• Algorithm Design Techniques (Combinatorial solution-space trees (Brute force search / Backtracking / Branch and Bound); Divide-and-Conquer; Dynamic Programming; Greedy Algorithms; Exploiting Data Structures) (11 lectures) [Chapters 15-16, Textbook]
• Graph Algorithms (Graph Traversal (Breadth-First, Depth-First); Minimum Spanning Trees; Shortest Paths) (7 lectures) [Chapters 22-25, Textbook]
• Computational Complexity Theory (Reductions; Hardness and Completeness; Classes P and NP; Heuristics (Hill Climbing / Genetic Algorithms); Randomized Algorithms; Approximation Algorithms; Parameterized Algorithms) (9 lectures) [Chapters 34 and 35, Textbook]

Evaluation Scheme

Students must pass the final exam to pass the course.

Assignment Deadlines (Tentative)

Textbook

• Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001) Introduction to Algorithms. Second Edition. The MIT Press; Cambridge, MA.

Recommended Readings

• Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley.
• Brassard, G. and Bratley, P. (1996) Fundamentals of Algorithms. Prentice-Hall.
• Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman; San Francisco, CA.
• Horowitz, E. and Sahni, S. (1978) Fundamentals of Computer Algorithms. Computer Science Press; Rockville, MD.
• Johnsonbaugh, R. and Schaefer, M. (2003) Algorithms. Pearson Education; Upper Saddle River, NJ.
• Skiena, S. (1998) The Algorithm Design Manual. Springer-Verlag; Berlin.

General Notes

• Assignments are due at the start of class on the specified date. Late assignments will only be accepted on medical or bereavement grounds; in these cases, appropriate documentation must be provided (see below). Otherwise, a mark of 0% will be given.
• University regulations wrt academic dishonesty will be applied if necessary (see pages 67-69 of the MUN 2005-2006 Calendar).
• University regulations wrt medical notes will be applied (see page 71 of the MUN 2005-2006 Calender):
  14.4.1 Students who request permission to drop courses, to withdraw from University studies, to have examinations deferred or to obtain other waivers of University, departmental or course regulations based on medical grounds are required by the University to produce a note from a physician in support of their request. Such notes must be sufficiently specific to allow a proper consideration of the student's case. The University requests that all medical notes be on letterhead, be signed by the physician and include details on the following:
  • confirmation of the specific dates on which the student visited the physician.
  • the degree to which the illness (or treatment, in the case of medication, for example) is likely to have affected the student's ability to study, attend classes, or sit examinations.
  • the length of time over which the student's abilities were likely hampered by the medical condition (e.g., recurring and severe back pain over a two-month period would likely have a more adverse effect on studies than a single episode of back pain requiring bed rest for a week).
  • the fitness of the student to resume studies (it is in the student's best interest not to return to studies prematurely).

Created: July 8, 2005
Last Modified: September 7, 2005