Algorithmics and data structures
[SINF1121]
[30h + 30h] 5 credits
This course is taught in the 1st semester.
Teacher(s): Pierre Dupont
Language: French
Level: First
Aims
- 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
- 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
- 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, ...)
(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/