Algorithmics and data structures [ LSINF1121 ]

> https://www.icampus.ucl.ac.be/claroline/course/index.php?cid=SINF1121

• Master of a object-oriented programming language (p.e. Java)
• Knowledge of basic data structures (stacks, queues, lists, etc..)
• Notions of recursion and computational complexity.

• 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
• Advanced data structures and algorithms: hash tables, heaps, balanced search trees, text processing techniques, dictionaries, graph representation and processing

Students completing successfully this course will be able to

• make a reasoned choice between the main data structures used to represent collections,
• make good use of existing algorithms for manipulating these data structures and analyze their performance,
• apply the principles of object-oriented programming such as genericity, abstraction, composition and reuse,
• design and implement variants of the studied algorithms in Java programs of high quality.

Students will have developed skills and operational methodology. In particular, they have developed their ability to:

• critically analyze a problem,
• learn by themselves in a reference book and in other technical documentation,
• work effectively in groups to analyze a problem, design, implementation and documentation of programs,
• balance the individual and group work,
• manage the learning curve and produce a satisfactory solution to the problems within time constraints.

The active teaching method followed in this course is based on a Problem Solving Approach. This method is based on several phases of work, some supervised by tutors. In addition to tutored sessions, an essential component of this pedagogical approach is to promote each student to learn by himself. The success of the learning process presupposes a significant involvement of each student. The role of group work is mainly to discuss the concepts studied and, secondarily, to organize the work of each. Learning itself remains the responsibility of each student.

The work is organized into missions that each group of students must perform with strict deadline (typically 2 weeks per mission). These missions include questions for which each group must make the best possible answers and programming problems, for which the group must produce Java programs.

The missions are intended primarily to create a context and motivation for learning new concepts and for developping methodological skills. Reach the end of a mission is not an end in itself. It is important to keep in mind that each mission is primarily an opportunity to develop learning goals explicit in the statement of each mission.

• Computational complexity,
• Trees, binary search trees,
• Balanced trees,
• Dictionaries and hash tables,
• Priority queues and heaps
• Graphs,
• Text processing (pattern matching, compression algorithms)

Mandatory book:

• Goodrich and Tamassia, Data structures & algorithms in Java, 5th edition, John Wiley & suns, 2011, ISBN: 978-0-470-39880-7

Recommended books:

• Cormen T.H. et al. , "Introduction to Algorithms, Second Edition" , MIT Press, 2001.
• Brassard G. & Bratley P., "Fundamentals of Algorithms" , Prentice Hall, 1996.