Course Outline - CMPT 705 - Design/Analysis Algorithms

Information

Subject

Catalog Number

Section

Semester

Title

Instructor(s)

Campus

CMPT

705

G100

2022 Fall (1227)

Design/Analysis Algorithms

Qianping Gu

Burnaby Mountain Campus

Calendar Objective/Description

Design/Analysis Algorithms

Instructor's Objectives

This is an advanced course on algorithms. We will review basic paradigms of algorithm design (greedy, divide-and-conquer, dynamic programming, etc.), and then explore some of the more advanced topics (e.g., NP-completeness, randomized algorithms, approximation algorithms, algorithms for special cases of NP-hard problems, etc.)

Prerequisites

see go.sfu.ca

Topics

Greedy Algorithms
Divide and Conquer
Dynamic Programming
Network Flow
NP and Computational Intractability
Approximation Algorithms
Randomized Algorithms
Algorithms for special cases of NP-hard problems
Slected topics on advanced algorithms

Grading

Lectures will be in person at the scheduled class time (currently 8:30-10:20am M and 8:30-9:30am W). Grading will be based on assignments, midterm tests and final exam. Details will be announced during the first week of classes.

Students must attain an overall passing grade on the weighted average of exams in the course in order to obtain a clear pass (C- or better).

Required Books

Algorithm Design, J. Kleinberg, E. Tardos, Addison-Wesley, 2006, 9780321295354

Reference Books

Introduction to Algorithms, 3rd Edition, T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill, 2003, 9780262033848
Computers and Intractability: A Guide To The Theory Of NP-Completeness, M. R. Garey, D. S. Johnson, W. H. Freeman, 1979, 9780716710455

Academic Honesty Statement

Academic honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty will be handled in accordance with the SFU Academic Honesty and Student Conduct Policies ( http://www.sfu.ca/policies/gazette/student.html ).