Informatics 2 [ LFSAB1402 ]

FSAB1401: Informatics 1 or equivalent

The principal themes covered by this course are:

• Techniques for deriving the computational complexity of an algorithm
• Techniques for reasoning about programs 
• Object-oriented modeling
• Linear and tree-like data structures
• Recursive algorithms
• Implementation in Java of medium-sized programs
• Methods for testing and validating programs

At the conclusion of this course, the students will be able to:

• make a choice between several data representations and algorithms to process them,
• reason on program fragments: algorithmic complexity and efficiency of the programs that implement them, reasoning with recursion,
• apply the principles of object-oriented modeling,
• design and apply methods for program testing.

The evaluation has 2 components: an intermediary evaluation during the quadrimester and a final exam at the end of the quadrimester (written exam). The final mark is a combination of the scores in these two evaluations

Active learning will be encouraged. The precise form that the active participation of the student will take is up to the teacher, following the pedagogical guidelines of the Faculty.

• Data abstraction
• Linear data abstractions (stacks, queues, lists, etc.) and their applications
• Techniques for representing linear data abstractions
• Object-oriented modeling (inheritance, composition, and reuse)
• Preconditions, postconditions, invariants
• Reasoning techniques (deduction rules, termination proofs, ...)
• Basics of computational complexity
• Derivation of the temporal complexity of an algorithm
• Derivation of the spatial complexity of a data structure
• Recursive formulation of a solution and recursive algorithms
• Tree-like data abstractions (binary trees) and their applications
• Techniques for representing tree-like data abstractions
• Quantified measurements of program efficiency
• Design and implementation of methods for testing and validating programs

 Workfiles for each of the parts (available on the website and in printed version)

Peter Van Roy et Seif Haridi, PROGRAMMATION: Concepts, techniques et modèles, Dunod, 2007

Peter Van Roy et Seif Haridi, Concepts, Techniques, and Models of Computer Programming, MIT press, 2004