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

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.