Zachary Friggstad, PhD
Contact
Associate Professor, Faculty of Science - Computing Science
- 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 303 - Algorithmics in Practice
This course is focused on algorithmic problems, where a solution involves properly understanding a written description, designing an efficient algorithm to solve the problem, and then correctly implementing the solution. Students will use previous knowledge in algorithms, data structures, and mathematical reasoning to solve problems in addition to learning new algorithms and data structures. Lectures are shared with CMPUT 403. Credit cannot be obtained for both CMPUT 303 and CMPUT 403. Prerequisites: One of CMPUT 201 or CMPUT 275, CMPUT 204.
CMPUT 403 - Algorithmics in Competitive Programming
This course is focused on algorithmic problems that can be solved within at most several hours by well-prepared people, where a solution involves properly understanding a written description, designing an efficient algorithm to solve the problem, and then correctly implementing the solution. Students will use algorithms, data structures, and mathematical reasoning to solve problems. Lectures are shared with CMPUT 303. CMPUT 403 covers additional material relevant to advanced programming contests. Credit cannot be obtained for both CMPUT 303 and CMPUT 403. Prerequisites: One of CMPUT 201 or CMPUT 275, CMPUT 204, and any 300-level Computing Science course, or consent of the instructor.
CMPUT 499 - Topics in Computing Science
This topics course is designed for a one on one individual study course between a student and an instructor. Prerequisites are determined by the instructor in the course outline. See Note (3) above.