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 275 - Introduction to Tangible Computing II

This is part 2 of a 2 sequence intensive introduction to Computing Science. Part 2 expands to add object-oriented programming, a higher level language (Python), and more complex algorithms and data structures such as shortest paths in graphs; caching, memoization, and dynamic programming; client-server style computing; recursion; and limited distributed of computation tasks between the Arduino platform and the traditional desktop in order to explore design tradeoffs. Prerequisite: CMPUT 274. Note: this course is taught in studio-style, where lectures and labs are blended into 3 hour sessions, twice a week. Enrollment is limited by the capacity of the combined lecture/lab facilities. Credit cannot be obtained for CMPUT 275 if one already has credit for any of CMPUT 174, 175, or 201, except with permission of the Department.

Winter Term 2021