Focus in Theory of Computation (Specialist) - ASFOC1689I

(5.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 strongly encourage taking the enriched theory courses ( CSC240H1, CSC265H1) as well as specialist/major versions of the MAT requirements for our focus. [Depending on courses selected for points 3 & 4, students may need to complete 0.5–1.0 credit in addition to the 12.0 credits required to complete the Specialist program.]

Enrolment Requirements

Enrolment in the Computer Science Specialist Program (ASSPE1689).

Completion Requirements

Required Courses:

  1. MAT137Y1/​ MAT157Y1/​ MAT237Y1 (Note: If MAT237Y1 is used here, it cannot be counted as part of the 2.0 credits for point 4, below.)
  2. CSC463H1
  3. 2.0 credits from the following: CSC304H1, CSC336H1, CSC438H1, CSC448H1, CSC473H1; MAT309H1, MAT332H1, MAT344H1; at UTM: MAT302H5; graduate courses: CSC2221H, CSC2401H, CSC2410H, CSC2412H, CSC2420H, CSC2421H, CSC2426H, CSC2451H, CSC2556H (note that students must petition to take a graduate course)
  4. 2.0 credits from the following: APM236H1/​MIE262H1, MIE263H1, APM421H1, APM461H1, MAT224H1/​ MAT247H1, MAT237Y1/​ MAT257Y1, MAT244H1/​ MAT267H1, MAT301H1/​ MAT347Y1, MAT315H1, MAT327H1, MAT334H1/​ MAT354H1, MAT335H1, MAT337H1/​ MAT357H1, any 400-level MAT course, STA238H1/​ STA248H1/​ STA261H1, STA347H1

Notes:

  1. Students who complete an independent study project ( CSC494H1/​ CSC495H1) under the supervision of a faculty member from the Theory group may request to substitute one of CSC494H1/​ CSC495H1 for one of the courses in list 3 above. This request must be made directly to the department's Undergraduate Office.
  2. Students who complete a graduate Topics course in Theory may request to count it towards the completion of list 3 above. This request must be made directly to the department's Undergraduate Office.

Recommended Courses:

  1. Students are strongly encouraged to take the enriched theory courses: CSC240H1 and CSC265H1, rather than their regular counterparts: CSC165H1/​ CSC236H1 and CSC263H1, respectively.