 | | |
| INFO0947-1 | Complements of computer programming
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
|
|
| Lecturer : | Benoît Donnet |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| Teaching in the second semester |
|
Course contents :
|
| The course mainly focuses on advanced data structures and algorithms related to those structures.
The main themes tackled during the semester are the following: advanced data structures (linked lists, abstract data types definition, stack, queue), advanced algorithmic (recursion, removing recursion), and strict program construction (loop invariant, Hoare Triplet).
The course structure is as follows:
- Introduction
- Chapter 1: Mathematical Reasoning
- Chapter 2: Program Construction
- Chapter 3: Linked Lists
- Chapter 4: Recursion
- Chapter 5: Abstract Data Types
- Chapter 6: Removing Recursion
- Chapter 7: Sequential Files
Chapter 7 will be tackled only if is allowed by the timing. |
|
Learning outcomes of the course :
|
| The purpose of the course is to improve the students knowledge and skills in programming.
A program construction will be at the heart of the course, through a strict methodology based on Hoare's triplet.
The programming language used is C.
At the end of the course, the student will be able to model (through assertions) a problem, to draw from the model formal specifications and invariant loops on which he will build his code. The student will also be able to use an advanced data structure, as well as to entirely define (signature, semantic, and implementation) an abstract data type.
Finally, the student will learn how to write reports (for various assignments through the semester) with the LaTeX tool. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| The course assumes several prerequisites.
Mathematics:
Computer Science:
- INFO0946: Introduction à la Programmation (http://www.montefiore.ulg.ac.be/~bdonnet/info0946/index.html)The basics of the C language and the imperative programming must be acquired.
- INFO0030: Projet de Programmation (http://www.montefiore.ulg.ac.be/~info0030/index.html).Algthough both INFO0030 and INFO0947 courses are run in parallel, it is of the highest importance for students to be able to import their knowledge from one course (INFO0030) to another (INFO0947). In the particular, the management of a project through a Makefile or setting up tests must be acquired.
In addition, the course assume a good knowledge of French (spoken and written) |
|
Planned learning activities and teaching methods :
|
| In addition to theoretical lessons, practical sessions (i.e., exercises) will be weekly organized. Each session last 2 hours. Each student will have around 14 practical sessions during the semester. Attending those sessions is mandatory.
In addition, the course proposes 3 assignments, during the semester, in order to illustrate and practice notions taught. Each assignment requires to write a C program, as well as a report (in French). Those assignments, to be done by group of 2, are mandatory. |
|
Mode of delivery (face-to-face ; distance-learning) :
|
| Theoretical lessons are given during the second semester, in face-to-face.
Theoretical lessons are build around examples and small exercises. The audience is supposed to participate during lessons.
In addition, students are supposed to take additional notes. |
|
Recommended or required readings :
|
| Notes are essentially made of slides. A printable version (2 slides/page) is available, since the beginning of the semester, at the Centrale des Cours. An electronic version of the slides is also made available on the course web page. Students are supposed to have the slides as soon as possible.
An exercises book is available at the Centrale des Cours. An electronic version is also available on the course web page. Each student is supposed to have the exercises book for the first practical session.
No book is mandatory for this course. However, any student willing to have an additional written support may refer to those books (in French -- they were used to build the course):
- Jacques Courtin, Irène Kowarski. "Initiation à l'Algorithmique et aux Structures de Données. Volume 1". Editions Dunod. 1998 (2ème édition).
- Jacques Courtin, Irène Kowarski. "Initiation à l'Algorithmique et aux Structures de Données. Volume 2". Editions Dunod. 1997 (2ème édition).
- Michel Divay. "Algorithmique et Structures de Données Génériques". 2004 (2ème édition)
- Jacques Julliand. "Cours et Exercices Corrigés d'Algorithmique. Vérifier, tester et Concevoir des Programmes en les Modélisant". Ed. Vuibert. 2010 (1ère édition)
- Jean-Louis Imbert. "Algorihmes Fondamentaux et Langage C". Ed. Ellipses. 2008 (1ère édition)
|
|
Assessment methods and criteria :
|
| Students are assessed in two ways: assignments and exam.
Assignments
The course is composed of three assignments, to be realized by group of two. Groups are formed at the early stage of the semester. Groups cannot be modified during the semester.
Those assignments count for 40% of the final grade.
Those assignments are mandatory. Any student that does not give back an assignment cannot take the June exam. In that case, the student will automatically have a resit (with a 0/20 in June).
Exam
The exam is written and mandatory. It is organized in June and lasts 4 hours.
The exam counts for 60% of the final grade.
There is also a possibility for an oral resit exam. This oral exam is optional. Any student thinking he failed in June (exam + assignment) with a grade below 10/20 can take the oral exam. Typical questions of the oral exam may be taken from the written exam and/or the various assignments.
Septembre Resit
In case of failure in June, there are two possibilities for the student:
- the student passes the assignments. In that case, the grade for the assignments is maintained and the student only has to redo the exam (written plus, possibly, the oral one).
- the student fails the assignments. All the assignments must be done again (but alone) and the exam must be passed (written plus, possibly, the oral one). Note that, during the summer, no support will be provided for the projects
In both cases, the points distribution between exam and assignments are identical to the one in June |
|
Work placement(s) :
|
| |
|
Organizational remarks :
|
| There exists a web page for the course:http://www.montefiore.ulg.ac.be/~bdonnet/info0947/index.html |
|
Contacts :
|
| Teacher: Benoit Donnet (mailto:benoit.donnet@ulg.ac.be(benoit.donnet@ulg.ac.be) -- Office 1.15 (B28)
TA: Simon Liénardy
A TA student) |
|
|
| Items online : |
|
| Course Web Page |
| Course web page |
|
|
