 | | |
| INFO0902-1 | Data structures and algorithms
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
| Bachelor in engineering sciences, civil engineer orientation (Bachelor in engineering sciences, civil engineer orientation), 2nd year | | Second semester | | 5 |
|
| Bachelor in computer sciences, 1st year | | Second semester | | 6 |
|
| Master of science in computer science and engineering, in-depth approach, 1st year | | Second semester | | 5 |
|
| Master of science in computer science and engineering, professional focus in management, 1st year | | Second semester | | 5 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | Toute l'année | | 6 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | Second semester | | 6 |
|
| Master in Mathematical Sciences, in-depth approach, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences, didactic approach, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences, professional focus in management, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences, professional focus in computer science, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences, professional focus in computer science, 2nd year | | Second semester | | 6 |
|
| Master en sciences mathématiques, à finalité spécialisée en statistiques, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences, specialized approach, 1st year | | Second semester | | 8 |
|
| Master in Mathematical Sciences | | Second semester | | 8 |
|
|
|
| Lecturer : | Pierre Geurts |
|
Language(s) of instruction :
|
| French language |
|
Course contents :
|
| Solving complex problems involves their decomposition into standard subproblems for which efficient and well-studied algorithms and data structures exist. This course is an introduction to the most important data structures and associated algorithms.
The course topics will include:
- elementary data structures (stacks, priority queues, heap)
- binary search trees
- hash tables
- problem solving methods: divide and conquer, greedy algorithm, dynamic programming
- sorting algorithms
- graph algorithms: search, shortest path, minimum spanning trees
Our approach will be theoretical: for each problem, we will systematically determine upper and lower bounds on the running times, and show the asymptotic behavior of our algorithms. |
|
Learning outcomes of the course :
|
| At the end of the course, the students will master the basis of algorithmics and will have a good knowledge of the main data structures. Given a new problem, they will be able to make a principled choice of the most appropriate choice of structure and manipulation algorithm given the practical problem constraints. They will be also able to initiate the main theoretical tools available to analyse the performance of algorithms. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| Basic knowledge of algorithms and programming, in particular with the C programming language (as taught in course INFO2009-1). |
|
Planned learning activities and teaching methods :
|
| The weekly theoretical class will be complemented by practical assignments, which will consist in analysing a problem, finding the best algorithm and data structures to solve it, and to implement the solution in C.
The participation to the theoretical lectures is voluntary but highly recommended. The assignments are mandatory. |
|
Mode of delivery (face-to-face ; distance-learning) :
|
| Face-to-face. |
|
Recommended or required readings :
|
| Several reference books will be recommended to the students, but not mandatory. Slides, problems and solutions and other materials will be available on the course webpage. |
|
Assessment methods and criteria :
|
| The final examination will be written. The mark of the assignments will count for the final mark and the realization of the assignments is required to access to the final exam. |
|
Contacts :
|
| Instructor: Pierre Geurts - Tel: 04/366.48.15 - e-mail: p.geurts@ulg.ac.be
Teaching Assistant: Gilles Louppe - e-mail: g.louppe@ulg.ac.be
Preferred contact modes: e-mail or personal contact after the lectures or by appointment. |
|
|
| Items online : |
|
| Online notes |
| Available on the instructor's web page. |
|
|
|
| |
