Duration
26h Th, 20h Pr, 40h Proj.
Number of credits
Lecturer
Substitute(s)
Language(s) of instruction
French language
Organisation and examination
Teaching in the second semester
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit 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 analyze algorithms (correction of algorithms, asymptotic notations)
- Sorting algorithms (merge sort, quicksort, heapsort...)
- Elementary data structures (stacks, priority queues, vector, sets, heap, graphs...)
- Dictionary structure (binary search trees, hash tables, tries...)
- Generic problem solving methods (brute force, divide and conquer, greedy algorithm, dynamic programming...)
- Graph algorithms (search, shortest path, minimum spanning trees...)
Learning outcomes of the learning unit
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 algorithms given the practical problem constraints. They will also be able to use the main theoretical tools available to analyze the performance of algorithms.
Prerequisite knowledge and skills
The following course is a prerequisite:
- INFO2009: Introduction to computer science (http://progcours.ulg.ac.be/cocoon/cours/INFO2009-2.html)
Planned learning activities and teaching methods
The weekly theoretical lectures and practical sessions will be complemented by practical assignments, which will consist in analyzing a problem, finding the best algorithm and data structures to solve it, and to implement the solution in C.
Participation to the theoretical lectures and practical sessions is voluntary but highly recommended. The assignments are mandatory.
Mode of delivery (face-to-face ; distance-learning)
Face-to-face, in the second quadrimester, in French.
Recommended or required readings
Several reference books will be suggested to the students, but reading them is not mandatory. Slides, problems and solutions and other materials will be available on the eCampus space of the course.
Assessment methods and criteria
Assessment methods:
- First session (June): 3 assignments (30%) and written exam (70%).
- Second session: 1 assignment for students who have not completed the assignments during the year (10%), written exam (90%).
- Assignments are mandatory to have access to the written exam. Students who have completed the assignments during the semester can keep their mark for the second session.
Work placement(s)
Organizational remarks
The contents of the theoretical and practical sessions, as well as the assignments and useful links, will be made available on the eCampus space of the course.
Contacts
- Substitute Teacher: Pascal Fontaine, +32 4 366 28 75, Pascal.Fontaine@uliege.be
- Teaching Assistants: Jean-Michel Begon, +32 4 366 29 72, jm.begon@ulg.ac.be Romain Mormont, r.mormont@uliege.be
- Preferred contact modes: e-mail or personal contact after the lectures or by appointment.
Adaptation of teaching commitments following the COVID-19 pandemic for the May-June 2020 session
Teaching methods implemented : distance-learning
Podcasts are available for students on the eCampus space of the course, together with small quizzes. There is a question/answer session organized weekly during the quadrimester.
A question/answer session will also be organized before the exam.
Assessment subjects
The contents for the exam are the full contents of the courses before the lock down, as well as the material from the podcasts.
Assessment methods
The evaluation will be based on a quiz with multiple choice questions and questions with short answers. The quiz is with penalty (a wrong answer gives negative points, it is thus possible to answer correctly to some questions and still have 0 for the global result). Students with more than 12/20 for the quiz, and 10/20 for projects succeed.
The final marks will be the average (50% / 50%) of the project and the quiz.
We *might* (no obligation on our part) organize an oral exam already in June for the students that would have either less than 12/20 for the quiz, or less than 10/20 for the project, but that have an average of both higher than 8/20.
Contacts
See contacts above.
Adaptation of teaching commitments following the COVID-19 pandemic for the Aug-Sept 2020 session
Assessment subjects
The contents for the exam are the full contents of the courses before the lock down, as well as the material from the podcasts.
Assessment methods
Students having below 10/20 for the assignments will have to redo them. If the evaluation of the assignment for the second session is still below 10, this will be the final mark.
Otherwise, there will be an exam consisting of a few questions with some allocated time for preparation. The answers will be discussed during a short oral exam. All the interaction will occur through eCampus and eCampus Collaborate. The final marks will be 50% for the assignments and 50% for the exam.
There will be a question/answer session before the exam.
Contacts
See contacts above.
Items online
Web page of the course
This web page collects lecture notes, practical exercices, and details about the projects.