Ensimag Rubrique Formation 2022

Algorithms and Discrete Optimization - 4MMAOD

  • Number of hours

    • Lectures 8.25
    • Tutorials 8.25

    ECTS

    ECTS 2.0

Goal(s)

in this course, we learn object oriented programming and study how to provide solutions to complex algorithmic problems. The course covers an introduction to OO programming, the design of algorithms driven by the analysis of their cost, and their implementation with an object oriented language. It is illustrated by the study of optimization problems using different techniques such as branch and bound, dynamic programming. Concepts are applied with practical training.

Contact Jean-Louis ROCH

Content(s)

Basis of OOP: concept of object, writing of classes and using of objects.
Recall of: cost and analysis of algorithms (time and memory cost; worst, average and amortized case analysis).
Abstract date type for sets of objects (containers and iterators): study and using via the notion of interface and a library of components.
Graphs – recall of the representations and OO implementation.
Modelling of some optimization problems with graph and shortest path.
Polymorphism, inheritance.
Recursive programming, Branch & Bound.
Design of complex data structures – cost and OO design
The language Java will be used. Two practical trainings (free time, by pairs) consist in programming some algorithms studied in class, with an OO language.



Prerequisites

Algorithmic and Data Structures 1 and 2.
Imperative programming (iteration, recursion, programming with procedures, genericity; practical training). Elementary and classical data structures (arrays, lists, trees, priority queues, dictionaries, hash tables).

Test

a written exam (3h) and 2 practical trainings

E1 = exam (session 1)
E2 = exam (session 2)

TP1 = practical training 1
TP2 = practical training 2
TP = practical training (global)

N1 = mark for APOO (session 1)
N2 = mark for APOO (session 2)



N1 = (3*E + TP) / 4
N2 = (3*E2 + TP) / 4

Additional Information

Curriculum->MMIS.->Semester 3
Curriculum->ENGINEERING systm of information->Semester 3
Curriculum->ISSC->Semester 3
Curriculum->SLE.->Semester 3
Curriculum->For Financial Engineering->Semester 3

Bibliography

Introduction to Algorithms (chap 1-4, 17, 14, 15, 22, 24, 25), Cormen Leiserson Rivest Stein, MIT PRESS
Thinking in Java, B. Eckel, Prentice Hall