Key words
Algorithms, Data structures, P170, P175, T120
Objectives
To gain insight in advanced algorithms and data structures, NP-complete problems, algorithms and data structures for strings.
Topics
Sequel to Algoritmen I, covering more advanced topics:
- Sequel to data structures: efficient search trees, external data structures, priority queues, skip lists.
- Sequel to algorithms on graphs: connectivity, union-find, minimal spanning trees, shortest distances, transitive closure, flow networks, matching.
- Sequel to algorithmic methods and analysis techniques: dynamic programming, randomized algorithms, amortized analysis.
- Introduction to NP-complete problems, and possibilities to tackle them.
- String search algorithms. Data structures for strings.
Prerequisites
Final objectives of Algoritmen I.
Final Objectives
This is a sequel to Algoritmen I, with approximately the same objectives. More advanced topics increase them, and more specific topics add another objective:
- General scientific abilities [AWC1]: Ability to think in a critical, creative and scientific fashion.
- General technical abilities [ATC2]: Ability to analyse engineering problems in a scientific way, and
to solve them. [ATC3]: Ability to perform scientific and technical tasks in an autonomous way.
[ATC4]: Ability to use research methods and techniques to solve engineering problems.
- Specific abilities [SC1]: Ability to apply principles of software design in an environment of
production, maintenance and quality management at an adequate price. [SC2]: Ability to execute
independently advanced tasks in the field of general applied computer science. [SC3]: Ability to
master all forms of present-day programming techniques, environments and languages, in order to
apply these in practice. [SC10]: Ability to obtain knowledge and insight in present-day scientific research in computer
science. [SC14]: Ability to implement and apply advanced, and specific algorithms and data structures.
Materials used
::Click here for additional information::
Handouts.
Study costs
Copy costs.
Study guidance
Lecturers are available during programming sessions and by appointment.
Teaching Methods
Theory: lectures.
Programming exercices in computer room (programming in C++).
Assessment
Theory: oral examination (37,5%).
Programming exercices in computer room: permanent evaluation (62,5%).
The final mark of the training item is the weighted average according the coefficients mentioned above.
However, if a student gains a score of 7 or less on 20 on one of the different courses (theory and programming exercices)
one can turn from the arithmetical calculation of the final mark of the training item and the new marks can be awarded on consensus.
Lecturer(s)
Rudy STOOP, members of the vakgroep informatica.
|
