Algorithms and Complexity

Course Code :1001WETALC
Study domain:Computer Science
Academic year:2017-2018
Semester:2nd semester
Sequentiality:-
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. The complexity of problems (as opposed to algorithms) is considered, leading to a number of classical results concerning NP-completeness and complexity classes.  Finally we briefly discuss te complexity of randomized and distributed algorithms.