Simon Fraser University
Engaging the World

Course Outlines

Fall 2019 - MATH 796 G100

Selected Topics in Mathematics (3)

Class Number: 10472

Delivery Method: In Person

Overview

  • Course Times + Location:

    Sep 3 – Dec 2, 2019: Tue, 11:30 a.m.–1:20 p.m.
    Burnaby

    Sep 3 – Dec 2, 2019: Thu, 11:30 a.m.–12:20 p.m.
    Burnaby

  • Exam Times + Location:

    Dec 13, 2019
    Fri, 12:00–3:00 p.m.
    Burnaby

Description

CALENDAR DESCRIPTION:

Held jointly with MATH 496-3. See description for MATH 496-3. Students may not take a 700 division course if it is being offered in conjunction with a 400 division course which they have taken previously.

COURSE DETAILS:

MATH 796 in Fall 2019 is being offered by the School of Computing Science, not by the Mathematics department and is cross-listed with CMPT 409/CMPT 815. 

Contact the Computing Science office or the instructor directly if you have any questions about MATH 796.

Course Title: Approximation/Randomized Algorithms

Most interesting optimization problems are NP-hard. For an NP-hard problem, it is impossible to have an algorithm which gives an optimal solution efficiently (in polynomial time) for any input instance of the problem unless P=NP. Approximation are powerful and widely used approaches for tackling hard optimization problems. An approximation  algorithm finds a near-optimal solution with guaranteed accuracy efficiently for any input instance. Randomized algorithms are another powerful and widely used approach to tackle problems for which efficient deterministic algorithms are not known. This course will cover the fundamentals on the design and analysis of approximation and randomized algorithms for discrete optimization problems. By completing this course, students are expected to be able to design approximation and randomized algorithms for their own problems, prove and analyze the correctness and efficiency of their algorithms, and apply theoretical analysis to the study of heuristics.

Prerequisites: Students should be comfortable with basic probability, linear algebra, and algorithms (e.g., graph algorithms such as BFS/DFS).

Resources: 

David P. Williamson and David B. Shmoys - The Design of Approximation Algorithms
R. Motwani and P. Raghavan - Randomized Algorithms
M. Mitzenmacher and E. Upfal - Probability and Computing

Contact the instructor directly to inquire about the readings above (required or recommended).

Grading

  • Homework 30%
  • Midterm 30%
  • Final 40%

Graduate Studies Notes:

Important dates and deadlines for graduate students are found here: http://www.sfu.ca/dean-gradstudies/current/important_dates/guidelines.html. The deadline to drop a course with a 100% refund is the end of week 2. The deadline to drop with no notation on your transcript is the end of week 3.

Registrar Notes:

SFU’s Academic Integrity web site http://www.sfu.ca/students/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating.  Check out the site for more information and videos that help explain the issues in plain English.

Each student is responsible for his or her conduct as it affects the University community.  Academic dishonesty, in whatever form, is ultimately destructive of the values of the University. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the University. http://www.sfu.ca/policies/gazette/student/s10-01.html

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS