Сomplexity Theory
Faculty
Edith Elkind
PhD, Computer Science Professor at Oxford University
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
The module familiarizes the students with fundamental notions of computability and complexity, starting with basics such as formal languages, Turing machines and the class NP, and then exploring various measures of complexity. Understanding limits of computation is an integral part of computer science education.
Learning highlights
- The goal is to provide students with tools to classify the computational problems they face according to their worst-case complexity as well as with methods to deal with computationally intractable problems. During this module, the students will learn about fundamental limits of computation and be exposed to several formal models of computation.
Course outline
4 classes
Finite automata and regular languages:
Definition of a finite automaton, formal languages, examples of languages that can be recognized by a finite automaton, regular languages, closure under regular operations.
Non-determinism; equivalence between regular expressions and NFA:
Definition of a non-deterministic finite automaton, examples of languages that can be recognized by a non-deterministic finite automaton, equivalence between DFA and NFA, regular expressions, pumping lemma.
Pushdown automata and context-free grammars:
Definitions of context-free grammars and pushdown automata, examples, equivalence between context-free languages and languages recognizable by PDA, pumping lemma for PDA, role of determinism.
Turing machines:
Definition of a Turing machine, examples of Turing machines, non-determinism, Church-Turing thesis, equivalence of different variants of Turing machines.
Prerequisites
This course is one of three in a wholistic series.
Students that have already taken MSL-111 and those with prior experience with HTML, CSS, and Javascript building simple web pages will be good candidates for this module.
Dr. Elkind researches game theory and the computation of social choices. She looks at the decisions involved in multi-agent systems such as auctions, elections and co-operative games.
Dr. Elkind joined the Oxford Computer Science Department in 2013. Prior to coming to Oxford she was an Assistant Professor at Nanyang Technological University (Singapore), where her research was supported by the National Research foundation (NRF) Fellowship.
See full profileApply for this course
Сomplexity Theory
by Edith Elkind
Total hours
45 Hours
Dates
May 22 - Jun 09, 2017
Fee for single course
€1500
Fee for degree students
€750
How to secure your spot
Complete the form below to kickstart your application
Schedule your Harbour.Space interview
If successful, get ready to join us on campus
FAQ
Will I receive a certificate after completion?
Yes. Upon completion of the course, you will receive a certificate signed by the director of the program your course belonged to.
Do I need a visa?
This depends on your case. Please check with the Spanish or Thai consulate in your country of residence about visa requirements. We will do our part to provide you with the necessary documents, such as the Certificate of Enrollment.
Can I get a discount?
Yes. The easiest way to enroll in a course at a discounted price is to register for multiple courses. Registering for multiple courses will reduce the cost per individual course. Please ask the Admissions Office for more information about the other kinds of discounts we offer and what you can do to receive one.