Duration
30h Th, 22h Pr, 45h Proj.
Number of credits
| Bachelor of Science (BSc) in Computer Science | 5 crédits |
Lecturer
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
The objective of the course is to increase students' programming skills.
In particular, the course can be divided in two big parts:
- Algorithmic. In this part, rigourous programs construction is at the heart of the course: inductive reasoning, problem formalisation, program construction guided by the loop invariant (Hoare's triplet). This methodology is applied to basic data structures, such as arrays and files. Recursion and its removal are also addressed. Complexity of algorithms is analyzed. The class also introduces the theoretical complexity
- Data Structures. In this part, abstract data type (ADT) approach is at the heart of the course. Abstract specification of a data structure and its implementation (static or dynamic) are discussed. Linear data structures are presented as ADT (list, stack, queue).
The course structure is the following:
- Introduction
- Chapter 1: Mathematical Reasoning
- Chapter 2: Program Construction
- Chapter 3: Introduction to Complexity
- Chapter 4: Recursion
- Chapter 5: Abstract Data Type
- Chapter 6: List
- Chapter 7: Stack
- Chapter 8: Queue
- Chapter 9: Recursion Removal
Learning outcomes of the learning unit
The purpose of the course is to improve the students knowledge and skills in programming.
A program construction and its complexity 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. Students will also be able to analyze their solution through theoretical complexity.
Finally, the student will learn how to write reports (for various assignments through the semester) with the LaTeX tool.
Prerequisite knowledge and skills
Corequisites are the following:
- MATH2019: Mathématiques pour l'Informatique (syllabus)
- INFO0946: Introduction à la Programmation (eCampus)
- INFO0030: Projet de Programmation (eCampus).
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. Attending those sessions is mandatory. Each student must prepare a certain number of exercises prior to each practical session. Computers/tablets/smartphones are to be avoided during practical sessions.
In addition, the course proposes two 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.
Finally, one or multiple "Collaborative Design and Build" (CDB) sessions will be organized throughout the semester.
Additional trainings are also proposed during the semester (report writing, LaTeX usage)
Mode of delivery (face to face, distance learning, hybrid learning)
Face-to-face course
Additional information:
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 (PDF) of the slides is also made available on the course Web page. Students are supposed to have the slides as soon as possible.
Practical sessions subjects are made available electronically on the course Web page. A printed version will also be available at the Centrale des Cours
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)
Exam(s) in session
Any session
- In-person
oral exam
Additional information:
Students are assessed in two ways: assignments and exam.
Assignments
The course is composed of several 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 an absence).
Exam
The exam is oral and mandatory. It is organized in June and is made of two parts. First, the students is examined by the Teacher. Second, the student must quickly code a function/procedure (related to programming assignments) with the TA. The exam counts for 60% of the final grade.
The main objective of the oral exam is to check the student's ability to think by himself and his ability to adopt a strict methodological approach when solving a problem.
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 are taken from unseen problems and part of the various assignments.
September Resit
In case of failure in June, there are two possibilities for the student:
- the student passes the assignments (grade > 10/20 for each assignments). In that case, the grade for the assignments is maintained and the student only has to redo the oral exam.
- the student fails the assignments. All the assignments must be done again (but alone) and the oral exam must be passed. Note that, during the summer, no support will be provided for the projects. Projects are mandatory for the resit. Otherwise, the student will not be allow to take the oral exam and an absence grade will be assigned.
Work placement(s)
Organisational remarks and main changes to the course
The course is given during the second semester.
Contacts
Teacher: Benoit Donnet (mail -- Office 1.87b/B28)
TA: Géraldine Brieven (mail -- Office 1.73b/B28)