Introduction to Algorithmics

Language

French

Prerequisites

LSINC1101

Main themes

The course introduces the student to the main methods for building algorithms based on a specification answering an identified problem. Recursion is used as a basis and the evaluation of the efficiency is based on the calculation of the execution time (complexity theory). We use recursive data structures: lists, binary trees, red-black trees, etc. We also use systematic methods for building efficient programs: divide and conquer, memoization, dynamic programming, greedy methods, and generate/test.

Learning outcomes

At the end of this learning unit, the student is able to :
.	At the end of this course, the student will be able to:          - formalize a recursive solution from a given problem statement; - calculate the theoretical complexity of a simple algorithm (recursive or not); - define and use a recursive data structure; - solve a problem in a systematic way and propose a correct and efficient algorithm.

Content

The course covers the following topics:
- Specification using pre- and post-conditions
- Execution time evaluation
- Recursion
- Recursive data structures: lists, binary trees, red-black trees
- Program construction methods: divide and conquer, memoization, dynamic programming, greedy method, generate/test

Teaching methods

Lectures with many examples, plus practical work. Students are also invited to do exercises at home.

Evaluation methods

Written exam.

Other information

The course follows part of the book: Hetland, Magnus Lie. Python Algorithms: mastering basic algorithms in the Python Language. Apress, 2014.

Faculty or entity

SINC