Zachary Friggstad, PhD

Associate Professor, Faculty of Science - Computing Science

Contact

Associate Professor, Faculty of Science - Computing Science
Email
zacharyf@ualberta.ca

Overview

About

Education

  • B.Sc, Computing Science, University of Lethbridge, 2005
  • M.Sc, Computing Science, University of Alberta, 2007 
  • Ph.D., Computing Science, University of Alberta, 2011

Research

Area

Algorithmics

Interests

Discrete Optimization, Approximation Algorithms, Mathematical Programming.

Summary

I design algorithms for discrete optimization problems. Common examples include vehicle routing, facility placement, resource allocation, and job scheduling problems.

Many of these problems are NP-hard. This means we do not expect any algorithm is able to efficiently find optimum solutions to these problems. I cope with this difficulty by designing approximation algorithms: algorithms that find near-optimum solutions. These are not just heuristics that tend to perform well in experiments. Such algorithms come with a proven guarantee on how far their computed solutions can deviate from the optimum solution.

Often, but not exclusively, I consider tractable convex relaxations of these problems such as linear or semidefinite programming relaxations. The goal is then to find such a relaxation that represents the original problem with high fidelity.

Courses

CMPUT 304 - Algorithms II

The second course of a two-course sequence on algorithm design. Emphasis on principles of algorithm design. Categories of algorithms such as divide-and-conquer, greedy algorithms, dynamic programming; analysis of algorithms; limits of algorithm design; NP-completeness; heuristic algorithms. Prerequisites: CMPUT 204; one of STAT 141, 151, 235 or 265 or SCI 151; one of MATH 225, 227, 228; or consent of the instructor.

Fall Term 2021
CMPUT 403 - Practical Algorithmics

The essence of computing science is in solving problems by computation. It may take anywhere from several minutes to several years from the initial posing of a problem specification to finally getting a working program. This course is interested in problems that can be solved within at most several hours by well prepared people. Prerequisites: Restricted to students participating in the programming contest. Any 300-level course, and consent of the instructor.

Winter Term 2022

Browse more courses taught by Zachary Friggstad