logo Insalogo Insa

POO and Graphs

Presentation

Programme (detailed contents):

 

Introduction to the object oriented programming

-       A first part introduces the fundamental concepts of object oriented design and programming. Then, the application of those concepts using an object-oriented language (JAVA) is studied. A second part is dedicated to the introduction of UML (Unified Modeling Languages). Class diagrams are particularly used. Finally, tutorials allow practical implementation of the objects concepts.

 

Graphs

-       General concepts of Graphs-

-       Classical graph problems and some associated methods : search, connectivity, shortest path, spanning tree, network flow, …)

 

Project « Graphs»

-       Implementation of a standard graph algorithm using efficient data structures

-       Performance evaluation on several data sets (based on real instances)

-       Conception of an original method (based on the previous one) to solve a non-standard problem

-       To perform the given work, the programming language studied in part 1 will be used

 

Organisation:

 

- POO and Graphs, followed by the project

- Within POO 1 : course then tutorials

- Within Graphs : course then tutorials

- Within Project “Graphs” : a set of tutorials

Objectives

At the end of this module, the student will have understood and be able to explain (main concepts):

 

-       the principles and fundamental notions of objects oriented design and programing,

-       the principles of UML class diagram and object oriented programming in Java

-       the different kinds of graphs, several classical problems on graphs and solving methods, comparison between several graph representations and algorithms

-       Apply the Graph theory for modelling various problems

-       Conception and Implementation of efficient algorithms based on graph data structure to solve a given problem.

 

 

The student will be able to:

 

-       design class diagrams of an application

-       design and program in JAVA a simple application,

-       to develop a classical graph algorithm aimed at solving a well-known problem whose specificity is to manipulate great amount of data,

-       to develop and compare different implementation of a well-known algorithm with the aim to apprehend the notion of algorithm complexity,

-       to propose and adapt classical algorithms aimed at solving a new problem,

-       to perform relevant measurements tests aimed at evaluating performances of different algorithms.

Needed prerequisite

- C Language (3e year MIC)

- Introduction to complexity (3e year MIC)

- Algorithms and Data structures (2e year MIC, 1st year)

Form of assessment

The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...

Additional information

Graph, complexity, Java, UML, class diagrams