Aims

- To design correct and efficient algorithms to solve well specified computational problems.

- To motivate the choice of appropriate data structures and algorithms.

- To implement data structures and algorithms in Java in a professional way.

- To apply object-oriented programming principles such as genericity, data abstraction, composition and reusability.

- To work efficiently in teams for the analysis, design, programming and documentation of the proposed solutions.

Main themes

- Computational complexity
- Specifications and object-oriented design
- Basic data structures (lists, trees, binary search trees): study of their abstract properties, practical representations, concrete applications and associated algorithms
- Introduction to data structures design pattersn
- Advanced data structures and algorithms: hash tables, heaps, balanced search trees, text processing techniques, dictionaries, graph representation and processing

Content and teaching methods

- Computational complexity
- Trees, binary search trees, AVL trees, multi-way search trees
- Dictionaries and hash tables
- Priority queues and heaps
- Graphs
- Text processing (suffix trees, pattern matching, compression algorithms)
- Design patterns in Java

Teaching method:
- problem based learning

Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

- Prerequisites
(1) Significant programming experience in an object-oriented language such as Java and knowledge of elementary data structures (stacks, queues, lists)

OR

(1) LINF1150 Introduction à l'algorithmique et la programmation: 1ère partie B. LeCharlier
(2) LINF1251 Introduction à l'algorithmique et à la programmation : 2ème partie P. VanRoy

OR

(1) FSAC1650 Informatique T6

- References
(1) Goodrich et Tamassia, "Data Structures and Algorithms in Java, Third Edition" , John Wiley & Sons, 2004.
(2) Cormen T.H. et al. , "Introduction to Algorithms, Second Edition" , MIT Press, 2001. Brassard G. & Bratley P., "Fundamentals of Algorithms" , Prentice Hall, 1996.

- Modalités d'organisation
(1) Evaluation during the whole year
(2) Written exam at the end.

- Remarque:
Course Web Site: http://www.info.ucl.ac.be/notes_de_cours/LINF2121/