Latest news Latest news

Use of Big Health and Actuarial Data Impact Workshop

Prof. Elena Kulinskaya is the PI on the ARC programme on Use of Big Health and Actuarial Data for understanding Longevity and Morbidity risks. The research programme held a one day Impact...

Smarter maths generates better value insurance products

Lens on Research and Innovation  (LORI) was selected by EPSRC for their showcase of impact.  Visit: www.epscr.ac.uk/lori  

Congratulations to CMP Head of School Professor Gerard Parr on his MBE

Prof Gerard Parr, Head of the School of Computing Sciences, has been made an MBE in the New Year Honours, for his services to developing telecoms infrastructure in Northern Ireland (NIR)....

CMP and Earlham Institute researchers develop new phylogenetics software package

Together with researchers in the Earlham Institute, members of Phylogenetics group in CMP have developed SPECTRE, a new open-source software package, that simplifies the complex business of...

CMP New Funding Success

Prof Elena Kulinskaya (PI) with Prof Julia Koricheva (RHUL) and Dr Gillian Petrokofsky (Oxford) have been successful in the NERC 2017 Evidence Synthesis Training Pilot Scheme call. The...

Latest Events and Seminars Latest Events and Seminars

Back

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

 

Abstract:

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.