Course Code : | 1001WETALC |

Study domain: | Computer Science |

Academic year: | 2014-2015 |

Semester: | 2nd semester |

Sequentiality: | Students COMPUTER SCIENCE: min. 8/20 for Discrete mathematics, Languages and machines and Data abstraction and structures. Students MATHEMATICS: min. 8/20 for Introduction to programming. |

Contact hours: | 60 |

Credits: | 6 |

Study load (hours): | 168 |

Contract restrictions: | No contract restriction |

Language of instruction: | Dutch |

Exam period: | exam in the 2nd semester |

Lecturer(s) | Dirk Janssens |

At the start of this course the student should have acquired the following competences:

an active knowledge of

- competences corresponding the final attainment level of secondary school

an active knowledge of

- Dutch

- English

See outcomes "Talen en Automaten" and "Machines en Berekenbaarheid"

In the first part of the course a number of models of computation are considered: RAM, RASP, Turing Machine. These models can be viewed as mathematical formalisms for the expression of algorithms; they differ in the choice of operations and data structures. Based on these models the notions of time and space complexity are introduced, and the models are compared. Then these notions of complexity are applied to a number of concrete algorithms. finally, the complexity of problems (as opposed to algorithms) is considered, leading to a number of classical results concerning complexity classes.

Class contact teachingLectures Practice sessions

ExaminationWritten examination without oral presentation Open book

course notes

Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley

prof. dr. Dirk Janssens (Dirk.Janssens@ua.ac.be)