Computer Science 3600:
Algorithm Design and Analysis
(Winter 2023)

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

Instructor	Office	Office Hours	Lectures
Todd Wareham harold@mun.ca	EN-2034 864-4601	TBA	Tue, 9:00-10:15 am, Thu, 9:00-10:15 am, Room EN-2040

Prerequisites

COMP 2002 or the former COMP 2711

Lecture Outline (Tentative)

• Basic Concepts (Problems; Algorithms; Asymptotic Worst-Case Time Complexity) (3 lectures) [Chapters 1-3, Cormen et al (2009)]
• Algorithm Design Techniques (Combinatorial solution-space trees (Brute force search / Backtracking / Branch and Bound); Divide-and-Conquer; Dynamic Programming; Greedy Algorithms; Exploiting Data Structures (Heaps)) (9 lectures) [Chapters 4, 6, and 15-16, Cormen et al (2009)]
• Graph Algorithms (Graph Traversal (Breadth-First); Shortest Paths) (3 lectures) [Chapters 22, 24, and 25, Cormen et al (2009)]
• Computational Complexity Theory (Reductions; Hardness and Completeness; Classes P and NP; Heuristics (Hill Climbing / Genetic Algorithms); Randomized Algorithms; Approximation Algorithms; Parameterized Algorithms) (3 lectures) [Chapters 34 and 35, Cormen et al (2009)]

The lectures and displays (and all material) delivered or provided in this course by the instructor, including any visual or audio recording thereof, are subject to copyright owned by the instructor.. It is prohibited to record or copy by any means, in any format, openly or surreptitiously, in whole or in part, in the absence of express written permission from the instructor any of the lectures or materials provided or published in any form during or from the course.

Evaluation Scheme

• There will be no supplementary assignments. Extensions for missed assignments (with appropriate documentation) will be given at the instructor's discretion. Where such extensions are not given, either (1) late assignments will be docked 25% or (2) marks for missed assignments (with appropriate documentation) will be averaged over the remaining assignments at the instructor's discretion.
• There will be no supplementary exams. Marks for missed in-class exams (with appropriate documentation) will be averaged over the remaining exams at the instructor's discretion.
• Students must pass the final exam to pass the course.

Assignment Deadlines (Tentative)

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.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009) Introduction to Algorithms. Third Edition. The MIT Press; Cambridge, MA.
• Downey, R. and Fellows, M.R. (1999) Parameterized Complexity. Springer-Verlag; Berlin.
• 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.
• Levitin, A. (2002) Introduction to the Design and Analysis of Algorithms. Addison-Wesley.
• Papadimitriou, C.H. (1994) Computational Complexity. Addison-Wesley.
• Papadimitriou, C.H. and Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall.
• Skiena, S. (2008) The Algorithm Design Manual. Second Edition. Springer-Verlag; Berlin.

• Memorial University of Newfoundland is committed to supporting inclusive education based on the principles of equity, accessibility, and collaboration. Accommodations are provided within the scope of the University Policies for the Accommodations of Students with Disabilities ( www.mun.ca/policy/site/policy.php?id=239). Students who may need an academic accommodation are asked to initiate the request with the Glenn Roy Blundon Centre at the earliest opportunity ( https://www.mun.ca/student/about-us/units-and-contacts/accessibility-services---the-blundon-centre/).
• Students are expected to adhere to those principles which constitute proper academic conduct. A student has the responsibility to know which actions, as described under Academic Offences in the University Regulations, could be construed as dishonest and improper. Students found guilty of an academic offence may be subject to a number of penalties commensurate with the offence including reprimand, reduction of grade, probation, suspension or expulsion from the University. For more information regarding this policy, students should refer to the University Regulations for Academic Misconduct (Section 6.12) in the University Calendar.

Created: October 31, 2022
Last Modified: February 14, 2023