Practical approaches to teaching the CS theory course: nondecision problems and real computer programs
Date and Time: 4th October, 13:00-14:00
Location: SCI 0.31
Speaker: Dr. John MacCormick's seminar
Institution: Dickinson College, PA, USA
Organiser: Dr. Michal Mackiewicz
Computational and complexity theory are core components of the computer science curriculum, and in the vast majority of cases they are taught using decision problems as the main paradigm. We present evidence that nondecision problems (such as optimization problems and search problems) are preferable, when the material is targeted for undergraduates encountering the theory of computation for the first time. We discuss some interesting reformulations of standard material (e.g., P and NP) that are required for this approach. In addition, we show how to maintain rigor while adopting real computer programs (written, for example, in Python) as the dominant computational model instead of Turing machines. Finally, since I will be visiting UEA for the next two years, I will mention some other projects and interests in computer vision, distributed systems, and the public understanding of computer science.