Key words
Algorithms, Data structures, P170, P175, T120
Objectives
The performance of many programs doesn't depend only on the speed of the computer, but often even
more on the use of efficient algorithms and data structures. This course intends to give a survey of
fundamental algorithms, data structures and algorithmic methods, and to provide insight in their
mechanisms.
Topics
An extensive survey of fundamental algorithms and data structures, together with an analysis of their
performance:
- Performance of programs. Asymptotic approximations.
- Various techniques to sort data: insertion sort, Shell sort, heapsort, mergesort, quicksort, counting
sort, radix sort, bucket sort.
- Fundamental data structures: arrays, lists, stacks, queues, priority queues, trees.
- Important data structures: hashtables, binary search trees, efficient binary search trees, B-trees.
- Representation of graphs. Fundamental graph algorithms.
Prerequisites
Final objectives of Informatica I, Informatica II, Discrete mathematics.
Final Objectives
For a variety of fundamental programming problems, different algorithms and data structures are studied,
their performance analysed, and compared. The programming exercices (using the object oriented
language C++) apply those methods to various problems, often comparing the predicted performance with
that of the implementations. This course therefore leads to the following objectives:
- 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. [SC8]: Ability to implement and apply basic algorithms and data structures.
[SC10]: Ability to obtain knowledge and insight in present-day scientific research in computer
science.
Materials used
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 (47%).
Programming exercices: permanent evaluation (53%).
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, Jan CNOPS.
|
