| Language of instruction : English |
|
Sequentiality
|
| |
|
Mandatory sequentiality bound on the level of programme components
|
| |
| |
| |
For following programme components you must have acquired a credit certificate, exemption, already tolerated unsatisfactory grade or selected tolerable unsatisfactory grade.
|
| |
|
Algorithms and Data Structures (0656)
|
8,0 stptn |
| |
|
| Degree programme | | Study hours | Credits | P2 SBU | P2 SP | 2nd Chance Exam1 | Tolerance2 | Final grade3 | |
 | Exchange Programme Computer Science | 2-yearly optional (next academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical |  |
| Master of Computer Science choice | 2-yearly optional (next academic year) | 162 | 6,0 | 162 | 6,0 | Yes | Yes | Numerical | |
|
| | | Learning outcomes |
- EC
| EC 2: A graduate of the Master of Computer Science programme is able to keep up with the evolution in the field of computer science (and related fields), to evaluate and to acquire new technologies. | - EC
| EC 3: A graduate of the Master of Computer Science programme has the necessary knowledge and insights in at least one subdiscipline which allow to contribute to the development and the application of innovative ideas in a certain area of computer science (by deepening basic knowledge at bachelor level, including that of mathematical and other scientific foundations). | - EC
| EC 4: A graduate of the Master of Computer Science programme takes account of the limitations of computer science, such as the existence of undecidedness and the existence of important unresolved problems in computer science such as the P=NP problem. | - EC
| EC 6: A graduate of the Master of Computer Science programme is able to independently situate a scientific problem, analyse and evaluate it, to formulate a research question and propose a solution for this in a scientifically substantiated manner. | - EC
| EC 7: A graduate of the Master of Computer Science programme is able to analyse and evaluate information in a critical manner and to process this information efficiently. | - EC
| EC 12: A graduate of the Master of Computer Science programme is able to critically reflect his or her own approach, to account for this and to adjust his/her behaviour accordingly. |
|
| | EC = learning outcomes DC = partial outcomes BC = evaluation criteria |
|
|
In the course Theoretical Computer Science it is shown that there are problems that cannot be solved by a computer: problems that are not "decidable".
In this course we are only interested in decidable problems, but we wonder how much time and how much memory, the computer needs to solve them.
Many known problems can be solved very efficiently by the computer: in the course Algorithms and Data Structures we have learned a whole series of
important efficient algorithms. On the other hand, we will see that there are also problems that are indeed decidable, but not efficiently, both in terms of time and memory.
Somewhere in between these two (efficiently solvable, not efficiently solvable) there appears to be a whole class of major problems
(the so-called NP-complete problems) for which we only know non-efficient, brute-force algorithms.
The surprising observation is that if you find an efficient algorithm for one such problem, you immediately have efficient algorithms for the whole class of NP-complete problems.
The problem of whether NP-complete problems can be solved efficiently is the most famous open problem in computer science.
A lot of important practical computer problems are (unfortunately) NP-complete, for example: problems from artificial intelligence; the planning of business processeses; optimizing solutions.
Yet not everything is unknown in terms of complexity! For example, we can make nice connections between the amount of memory needed to solve a problem and the necessary time.
For example, we will see that problems that can be solved with very little memory usage can also be solved in a reasonable time.
Apart from time and space complexity, this course also looks at space and time hierarchy theorems, Turing Machines equipped with oracles and Boolean circuit complexity,
among other topics.
The general goals of this course are:
1. The student acquires insight into the possibilities and limitations of computer science to solve problems in an efficient manner.
2. The student realizes that a number of fundamental issues about complexity are still unresolved.
|
|
|
|
|
|
|
|
|
Lecture ✔
|
|
|
|
Small group session ✔
|
|
|
|
Period 2 Credits 6,00
|
| Additional information | There is a written exam on theory and exercises. |
|
Second examination period
| Evaluation second examination opportunity different from first examination opprt | |
|
|
|
| Previously purchased compulsory textbooks |
| |
Introduction to the Theory of Computation,M. Sipser,3rd edition, (2nd edition is also fine),PWS Publishing Co |
|
|
| Compulsory course material |
| |
Extra study materials will be made available on Blackboard. |
|
|
|
|
|
1 examination regulations art.1.3, section 4. |
| 2 examination regulations art.4.7, section 2. |
3 examination regulations art.2.2, section 3.
|
| Legend |
| SBU : course load | SP : ECTS | N : Dutch | E : English |
|