Discrete Optimization, Approximation Algorithms, Mathematical Programming.
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.
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
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 2021
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.Fall Term 2020