74.208 Analysis of Algorithms

Textbook:

• Fundamentals of Algorithmics, Gilles Brassard & Paul Bratley, Prentice-Hall, 1996 (ISBN 0-13-335068-1).

Books on Reserve in the Science Library:

• Introduction to algorithms, Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Cambridge, Mass. : MIT Press ; New York : McGraw-Hill, c1990.

Help:

• There will be consulting hours with TAs.
• Visit the course website at http://www.cs.umanitoba.ca/~cs208 for slides, assignments, assignment solutions, etc. Use the ps or pdf links to get a postscript or pdf version of the documents.
• Read or post an article on local.cs208.
• Visit the instructors during the consulting hours.

Outline of Topics:

• Textbook, chapters 1 to 8 (included).
• Review of basic algebra, logarithms and calculus
• Introduction to analytic methods for algorithms:
• When an algorithm is specified
• Elementary operation
• Sums and finding closed forms
• Average and worst-case analysis
• Asymptotic notation (big O, Theta, Omega)
• Techniques for solving recurrences.
• Read Chapter 5, data structures.
• Algorithm design techniques:
• Divide-and-conquer
• Greedy algorithms
• Dynamic programming
• Time permiting, algorithms on graphs (Chapter 9).

Assignments:

• There will be 5 assignments.
• The assignments are to be handed in either in class at the beginning of class on the due date.
• Late assignments with a good excuse will be accepted after class, not during class.
• Random marking will be applied to mark assignments.
• Assignments must be legibly written in pen, pencils 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. Don't forget the Honesty Declaration.

Term Tests:

There will be two term tests. They 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.

 

Marking Scheme:

• Assignments 10%
• Term tests 30% (15% each)
• Final 60%

Academic Dishonesty:

You should be aware that plagiarism of any sort and any other form of cheating is considered a very serious offense, and it will be severely dealt with. In particular, make sure that all the work you hand in is yours and yours alone. If you are found guilty of copying any work you hand in, then you are liable for serious academic penalties. Note that you are also guilty if you help someone else cheat. Read the section on plagiarism and cheating and examination impersonation in the University General Calendar.

Send comments about this page to 74.208 Web Master - cs208@cs.umanitoba.ca

This page last modified: 17 December 2000