Simon Fraser University
Engaging the World

Course Outlines

Spring 2019 - CMPT 881 G100

Special Topics in Theoretical Computing Science (3)

Approximation & Randomized Algorithms

Class Number: 6556

Delivery Method: In Person

Overview

  • Course Times + Location:

    Jan 3 – Apr 8, 2019: Tue, Thu, 11:30 a.m.–12:50 p.m.
    Burnaby

Description

COURSE DETAILS:

This is a graduate-level course in approximation and randomized algorithms. Many discrete optimization problems arising in theory and practice turn out to be NP-hard, and thus optimal solutions cannot be computed efficiently unless P=NP. One approach to deal with this situation is to design approximation algorithms, i.e., efficient algorithms that are guaranteed to return a near-optimal solution. Randomized algorithms are another powerful and widely used approach to tackle problems for which efficient deterministic algorithms are not known. The objective of this course is to expose students to techniques in approximation and randomized algorithms.

Topics

  • Approximation Algorithms
  • Greedy Algorithms
  • Linear Programming
  • Semidefinite Programming
  • Randomized Algorithms
  • Linearity Of Expectation
  • Probabilistic Method
  • Sublinear Time Algorithms
  • Hardness of Approximation

Grading

NOTES:

There will be 3-4 homework assignments and a project/presentation in the end of the course.
The details to be discussed in the first week of the class.

Materials

MATERIALS + SUPPLIES:

  • The Design of Approximation Algorithms
  • David P. Williamson and David B. Shmoys
  • Cambridge University Press
  • 9780521195270

  • Randomized Algorithms 
  • Rajeev Motwani and Prabhakar Raghavan
  • 9780521474658

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