 | | |
| INFO2050-1 | Advanced computer programming
|
|
| Duration : | 25h Th, 20h Pr, 40h Proj. |
|
| Number of credits : |
|
|
| Lecturer : | Pierre Geurts |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| Teaching in the first semester, review in January |
|
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:
- Tools to analyse algorithms (correction of algorithms, asymptotic notations, sums and recurrences...)
- Sorting algorithms (merge sort, quicksort, heapsort...)
- Elementary data structures (stacks, priority queues, vector, sets, heap, graphs...)
- Dictionnary structure (binary search trees, hash tables, tries...)
- Generic problem solving methods (brute force, divide and conquer, greedy algorithm, dynamic programming...)
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 :
|
| Prerequisites are the following:
Corequisites are the following:
|
|
Planned learning activities and teaching methods :
|
| The weekly theoretical and exercice 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, in the first semester. |
|
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 :
|
| Assessment methods:
- First session (January): 3 assignments (30%) and written exam (70%). Assignments are mandatory to have access to the written exam.
- Second session: 1 assignment for students who have not completed the assignments during the year (10%), written exam (90%).
|
|
Work placement(s) :
|
| |
|
Organizational remarks :
|
| |
|
Contacts :
|
| Instructor: Pierre Geurts - Tel: 04/366.48.15 - e-mail: p.geurts@ulg.ac.be
Teaching Assistant: Jean-Michel Begon
Preferred contact modes: e-mail or personal contact after the lectures or by appointment. |
|
|
| Items online : |
|
| Course web page |
| This web page collects lecture notes, practical exercices, and all details about the projects. |
|
|
