| Course label : | Algorithms and their complexity 1 |
|---|---|
| Teaching departement : | EEA / Electrotechnics - Electronics - Control Systems |
| Teaching manager : | Mister PIERRE-ANTOINE THOUVENIN / Mister PIERRE CHAINAIS |
| Education language : | |
| Potential ects : | 0 |
| Results grid : | |
| Code and label (hp) : | MR_DS_S1_AC1 - Algo and their complexity 1 |
Education team
Teachers : Mister PIERRE-ANTOINE THOUVENIN / Mister PIERRE CHAINAIS
External contributors (business, research, secondary education): various temporary teachers
Summary
The course will cover the following topics: • Fundamental properties of algorithms. • Algorithm writing with pseudo-code. • Recursion. • Formal notational methods for stating the growth of resource needs (efficiency and storage) of an algorithm (Big Oh, Little oh, Theta notations). • Time and space complexity. • Best-case and worst-case complexity. • Divide-and-conquer paradigm. • Backtracking. • Branch-and-bound. • Dynamic programming. • Greedy algorithms.
Educational goals
This course gives an overview about algorithms and computation with a particular focus on the cost of algorithms. The overall goal is to be able to understand a range of algorithmic approaches, use them to solve practical problems, evaluate their cost, and compare the costs of different algorithms solving a given problem. After successfully taking this course, a student should be able to: • Write recursive algorithms, • Understand the following families of algorithms and use them to solve problems: divide-and-conquer, backtracking, branch-and-bound, dynamic programming, greedy algorithms. • Understand and evaluate the time and space complexity of an algorithm. • Analyze worst-case and best-case running times of algorithms using asymptotic analysis. • Derive and solve recurrences describing the performance of recursive and divide-and-conquer algorithms.
Sustainable development goals
Knowledge control procedures
Continuous Assessment
Comments: Quizzes, grading scale: (min) 0 – 20 (max)
Homework, grading scale: (min) 0 – 20 (max)
Online resources
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Clifford Stein) – McGraw-Hill.
Pedagogy
24 hours : 8 lectures, 8 tutorials. Language of instruction is specified in the course offering information in the course and program directory. English is the default language.
Sequencing / learning methods
| Number of hours - Lectures : | 12 |
|---|---|
| Number of hours - Tutorial : | 12 |
| Number of hours - Practical work : | 0 |
| Number of hours - Seminar : | 0 |
| Number of hours - Half-group seminar : | 0 |
| Number of student hours in TEA (Autonomous learning) : | 0 |
| Number of student hours in TNE (Non-supervised activities) : | 0 |
| Number of hours in CB (Fixed exams) : | 0 |
| Number of student hours in PER (Personal work) : | 0 |
| Number of hours - Projects : | 0 |
Prerequisites
This course requires some basic programming knowledge (expressions, variable, control flow statements, functions, arrays or lists) and some fundamental notions of mathematics (functions and sequences, recurrence relations). The knowledge of specific programming languages is not required.