CES8AF 

Algorithm problem solving

 

ECTS Credits: 4

Duration: 36 hours

Semester: S7

Person(s) in charge:

Bart LAMIROY, Associate Professor,  bart.lamiroy@mines-nancy.univ-lorraine.fr

Keywords:

 algorithmics

Prerequisites: basic algorithmics, imperative programming

Objective: discover the “beauty” of algorithms by a detailed study of a few representative problems

 

Program and contents:

Objectives

An algorithm is a precise method used for solving a generic problem by combining operations which are simple enough to be carried out by a machine. It must be based on a rigorous and methodical approach, not subjective decisions or intuition. The entire interest of algorithms is to thereby propose elegant and efficient methods for solving a priori complex problems. To do this, we draw on a combination of elementary reasoning operations and relevant data structures.

Algorithms are at the heart of the information systems used in all engineering disciplines insofar as they bring about solutions for problems as varied as data visualization, simulation of physical phenomena, metrology, to cite just a few examples.

The course is divided into 5 or 6 parts covering 2 or 3 class sessions. Each part deals with a problem – a nugget. We begin by setting forth the problem and then “dissecting” it in order to explore the different possible ways to find a solution. After that, a representative state of the art algorithm will be scrutinized, and then programmed.

The algorithms will be chosen for being representative of a large variety of problems, and can vary from one year to the next. We will find problems in the following families:

  • Advanced data structures: heaps, sets, trees, hash, etc.
  • Computational geometry and discrete geometry: convex hulls, Voronoi diagrams, calculation of skeletons, transformed distance, etc.
  • Algorithms on words and graphs, and their numerous applications
  • Rewriting terms, syntax analysis
  • Imaging
  • Parallel algorithms
  • Game algorithms: dynamic programming, A*, etc.

 

 

Abilities: 

Levels

 Description and operational verbs

Know 

The panorama of contexts in which algorithmics brings an added value in the resolution of problems

Understand 

That the sensible choice of data structures and hypotheses of execution can have a significant impact on the practical feasibility of a solution theoretically feasible

Apply 

Problem-solving and algorithms optimization techniques

Analyze 

Physical problems and bring an algorithmic solution

Summarize

 

Assess

The qualitative difference (in terms of performances and capacities of solution) between various algorithmic solutions for the same problem.

Evaluation:

  • Written test
  • Continuous Control
  • Oral report
  • Project
  • Written report