William Evans

Professor

Office
ICCS
X841
Office Phone #
604-822-0827

Academic Information

Professor (since 2020), Associate Professor (2004-2020), Assistant Professor (2001-2004), University of British Columbia; Assistant Professor, University of Arizona (1996-2000); NSERC Postdoctoral Fellow, University of British Columbia (1994-1996); PhD Computer Science, University of California at Berkeley (1994); B.S. Computer Science, Yale University (1987).

Research Areas

computational geometry

Research Groups

Interests

My research interests are in the design of algorithms and the understanding of the fundamental limitations of various models of computation. I've pursued this interest in various areas of computer science:

* Graph Drawing - I study problems related to the geometric representation of graphs. For example, I'm interested in what graphs can be represented using contact or visibility between geometric objects, and how several graphs can be represented simultaneously using a shared set of objects.
* Algorithms that operate with uncertain input - What guarantees can an algorithm make if it knows that its input is uncertain but the uncertainty is bounded? How do we design and analyze algorithms that can gain more certainty at a price?
* Computational geometry - I'm interested in geometric problems or problems whose solution requires geometric techniques. I've been particularly interested in problems arising from geographic information systems. For example, problems in map drawing and concise surface (terrain) representation.
* Information theory - How is computation influenced by random noise? What price do you pay for using Boolean gates that produce the wrong output randomly with some small probability? I've been studying questions of this type using tools from information theory and computational complexity theory.
* Program compression - Software that is intended for palm-top computers, cell phones, and embedded controllers is getting more and more complicated, yet space, weight, price, and power consumption issues limit the amount of memory available to run this software. I'm interested in automatically reducing software's memory footprint without changing its function; essentially, exploring techniques that could be used in a very aggressive space-optimizing compiler. Software is also frequently downloaded across potentially slow network connections. I'm interested in how to represent and compress this software to reduce transmission time. In this case, I have the flexibility to choose a compressed form that may require decompression before execution.

Courses

2023 Winter
CPSC 420 - Advanced Algorithms Design and Analysis
CPSC 536E - Topics in Algorithms and Complexity
CPSC 536E - Topics in Algorithms and Complexity
2022 Winter
CPSC 420 - Advanced Algorithms Design and Analysis
CPSC 516 - Computational Geometry
2020 Winter
CPSC 221 - Basic Algorithms and Data Structures
CPSC 221 - Basic Algorithms and Data Structures
2019 Winter
CPSC 221 - Basic Algorithms and Data Structures
CPSC 221 - Basic Algorithms and Data Structures
2018 Winter
CPSC 221 - Basic Algorithms and Data Structures
2017 Winter
CPSC 536E - Topics in Algorithms and Complexity
2016 Winter
CPSC 500 - Fundamentals of Algorithm Design and Analysis
CPSC 420 - Advanced Algorithms Design and Analysis
CPSC 221 - Basic Algorithms and Data Structures
2015 Winter
CPSC 500 - Fundamentals of Algorithm Design and Analysis
CPSC 420 - Advanced Algorithms Design and Analysis
CPSC 221 - Basic Algorithms and Data Structures