(3.5 credits)

Why is it easy to sort a list of numbers, but hard to break Internet encryption schemes? Is finding a solution to a problem harder than checking that a solution is correct? Can we find good approximate solutions, even when the exact solutions seem out of reach? Theory of Computation studies the inherent complexity of fundamental algorithmic problems. On one hand, we develop ground-breaking efficient data structures and algorithms. On the other, we have yet to develop good algorithms for many problems despite decades of effort, and for these problems we strive to prove no time- or space-efficient algorithms will ever solve them. While the field has seen some successful impossibility results, there are still many problems (such as those underlying modern cryptography and security) for which we do not know either efficient algorithms or strong lower bounds!

This focus takes a rigorous, mathematical approach to computational problem-solving: students will gain a deep understanding of algorithm paradigms and measures of problem complexity, and develop the skills necessary to convey abstract ideas with precision and clarity. Many of our students go on to graduate studies and sophisticated algorithmic work in industry. This focus has natural ties with many branches of mathematics and is the foundation of many computer science fields. Consequently, our students often apply their theoretical knowledge to other fields of interest.

We advise you to take CSC240H1 and CSC265H1, the enriched versions of CSC236H1 and CSC263H1, because these courses are particularly well-aligned with the goals of this focus and will best prepare you for advanced theory courses. However, students who have already taken CSC236H1/​ CSC236H5/​ CSCB36H3 or CSC263H1/​ CSC263H5/​ CSCB63H3 are also welcome to enrol in the focus.