Aims

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.

Main themes

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
- Data abstraction
- Linear data abstractions (stacks, queues, lists, ...) 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

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.

Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

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
- Workfiles for each of the parts (available on the website and in
printed version); Reference book: University Physics (Freedman and Young)

Other credits in programs