74.317 Analysis of Algorithms and Data Structures

Textbook:
    The following book is recommended: Fundamentals of Algorithmics, Gilles Brassard & Paul Bratley, Prentice-Hall, 1996 (ISBN 0-13-335068-1).

Other books:
    Randomized Algorithms,  Rajeev Motwani & Prabhakar Raghavan, Cambridge University Press, 2000, (ISBN 0-521-47465-5).
    Approximation algorithms, Vijay V.  Vazirani, Springer-Verlag, 2003, (ISBN 3-540-65367-8).
    Approximation Algorithms for NP-Hard Problems, Edited by Dorit S. Hochbaum, PWS Publishing Company, 1997, (ISBN 0-534-94968-1).
 

Also provided:
    Class notes, references to web sites, articles and other material.

Course's objective:
    The course can be understood as having two sections: Fundamentals and Applications. In the fundamentals, we first review a few essential concepts of algorithm analysis & design (seen in cs208). Then, we spend some time making connections between real life application problems and their mathematical representations (mathematical modeling). Algorithms are designed based on mathematical representations of real life problems, a requirement when using the scientific method. To some extend, you will be on familiar ground  as mathematical representations play a similar role in science as data structures for algorithms. Next, for a few lectures, we make a digression from algorithm analysis & design in order to introduce Complexity Theory. This theory provides a classification of computational problems based on what seems to be their inherent time (space) requirement for classical computers. This classification identifies some problems as inherently difficult to solve by computers, problems for which it is unlikely we will ever find any efficient algorithm. On the other hand, solving many of these problems is crucial for the well been of our society. In the Applications section, we study different algorithm design techniques often used to tackle those computationally hard problems: search techniques, randomized and approximation algorithms. About 1/4 of the semester will be dedicated to the fundamentals and 3/4 to algorithm design techniques.
 

Outline of topics covered:

• Review of basic algorithm analysis concepts and algorithm design techniques:
• Average and worst-case analysis, asymptotic notations, solving recurrences, etc.
• Greedy algorithms, Divide-&-Conquer, Dynamic programming.
• Introduction to Mathematical Modeling.
• Purpose of models and abstractions in science, Mathematical structures as modelization tools, with emphasis on graph representations.
• Introduction to some classical problem's representations (models) and how their structures (or lack of structures) impact algorithmic solutions to problems.
• Exact methods:
• Dynamic programming
• Exhaustive explicit enumeration.
• Backtracking (Brassard pa. 305).
• Branch & Bound (Brassard pa. 312).
• Introduction to Complexity Theory:
• Problems' complexity versus algorithms' complexity.
• Lower bounds on problems' complexity (Brassard pp. 418-421).
• The classes P & NP (Brassard, section 12.5).
• Polynomial time reducibility & NP-completeness (Brassard, section 12.5).
• Searches heuristics
• Local search
• Genetic algorithms
• Simulated annealing
• Tabu search
• Randomized Algorithms
• Elementary probability theory (Brassard section 1.7.4)
• Las Vegas algorithms (Brassard chap. 10.7):
• Monte Carlo algorithms (Brassard chap. 10.6):
• Approximation Algorithms (Brassard chap. 13):
• Relative approximation algorithms
• Absolute approximation algorithms
• Hardness of approximation (Complexity theory of approximation)
• Approximation schemes:
• PAS
• FPAS.
• Challenges facing algorithm designers in the future.

• There will be 4 or 5 assignments.
• The assignments are to be handed in either in class at the beginning of class on the due date.
• Assignments must be legibly written or typed. Assignments may be handed in in a letter-sized folder (but you don't have to use a folder and please do not use legal-sized folders). Assignments must be securely stapled in the top left-hand corner. Each assignment must begin with a cover page with your name (please underline your family name), your student number, the course number, your instructor's name and the assignment number. An academic honesty declaration is to be included with each assignment.

Midterm:

• An one hour midterm exam will be held during regular class time.
• The midterm exam must be written in pen (no pencils).
• No other aids will be permitted: no calculators, no texts, and no notes.
• You must bring your student identification card to the midterm.

Final:

• 3 hours

Marking Scheme:

• Assignments 20%
• Midterm 20%
• Final 60%

Academic Dishonesty: