# Algorithms and Complexity

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 |

### 1. Prerequisites *

- competences corresponding the final attainment level of secondary school

an active knowledge of

- Dutch

- English

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

### 2. Learning outcomes *

### 3. Course contents *

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.

### 4. Teaching method and planned learning activities

### 5. Assessment method and criteria

### 6. Study material *

#### 6.1 Required reading

course notes

**6.2 Optional reading**

The following study material can be studied voluntarily :Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley

### 7. Contact information *

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