May 14, 2021  
University of Alberta Calendar 2020-2021 
University of Alberta Calendar 2020-2021 [ARCHIVED CATALOG]

AUCSC 415 - Automata, Algorithms and Complexity

★ 3 (fi 6) (either term, 3-0-0) Models of computers, including finite automata and Turing machines, basics of formal languages, compatibility, algorithm optimality, complexity classes (p, NP, NPcomplete, EXP, PSPACE, etc.), probabilistic algorithms, approximation algorithms, number-theoretic and other selected algorithms, including selection and order statistics. Prerequisites: AUCSC 310. Notes: This course may not be taken for credit if credit has previously been received for AUCSC 315 (2019), 410 (2019), or AUMAT 355 (2019).