Tech Heart
Harbour.Space University

RESERVE MY SPOT

Prof. Elkind joined the Oxford Computer Science Department in 2013. In 2014 she was awarded an ERC Starting Grant. Prior to coming to Oxford she was an Assistant Professor at Nanyang Technological University (Singapore). Prof Elkind obtained her PhD from Princeton University in 2005, and was a postdoctoral research fellow at the University of Warwick, University of Liverpool and Hebrew University of Jerusalem, as well as a lecturer at University of Southampton.

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.

SKILLS:

- Algorithms

- Game theory

- Voting

- Auctions

- Cooperation

DATE: 22 May - 9 June, 2017

DURATION: 3 Weeks

LECTURES: 3 Hours per day

LANGUAGE: English

LOCATION: Barcelona, Harbour.Space Campus

COURSE TYPE: Offline

WHAT YOU WILL LEARN
ABOUT EDITH
HARBOUR.SPACE 

COMPUTATIONAL
COMPLEXITY THEORY 

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.

EDITH ELKIND
RESERVE MY SPOT

We offer innovative university degrees taught in English by industry leaders from around the world, aimed at giving our students meaningful and creatively satisfying top-level professional futures. We think the future is bright if you make it so.

HARBOUR.SPACE UNIVERSITY

DATE: 22 May – 9 June, 2017

DURATION:  3 Weeks

LECTURES: 3 Hours per day

LANGUAGE: English

LOCATION: Barcelona, Harbour.Space Campus

COURSE TYPE: Offline

COMPLEXITY 
THEORY 
BIBLIOGRAPHY
COURSE OUTLINE

Session 1

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.

Session 2

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.

Session 3

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.

SHOW MORE

Session 4

Turing machines:

Definition of a Turing machine, examples of Turing machines, non-determinism, Church-Turing thesis, equivalence of different variants of Turing machines.