Introduction to algorithms

5.00 credits

30.0 h + 30.0 h

Teacher(s)

Dupont Pierre;

Language

French

Prerequisites

This course assumes that the student already masters the basics of programming covered by the course LINFO1101.

Main themes

Design and implementation of iterative or recursive algorithms: path, counting, sorting, searching in collections
Computational complexity
Basic data structures: arrays, stacks, queues, linked lists
Recursive data structures: tree structures, binary search trees
Invariants

Learning outcomes

At the end of this learning unit, the student is able to :

Given the learning outcomes of the "Bachelor in Computer science" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

S1.I2, S1.I3
S2.2-4
S6.2

Students who have successfully completed this course will be able to:

justify a choice between several algorithmic solutions to solve a given problem,
analyze algorithms, iterative or recursive, to represent and manipulate collections and to propose variants thereof,
choose, design and use data structures, including recursive,
give a reasoned estimate of the time complexity of iterative algorithms and the spatial complexity of data structures;
reasoning about properties of algorithms or data structures in terms of invariants.

Students will have developed methodological and operational skills. In particular, they have developed their ability to:

to take a critical look and make a reasoned analysis of a solution or set of solutions that could be made to a given problem by setting quality criteria,
realize small programs using conventional algorithms and data structures.

Content

Algorithmics is concerned with solving problems by implementing sequences of elementary operations according to a predefined process or procedure leading to a solution.
This discipline is both abstract and put into practice through programs (e.g. implemented in Python) and run on a computer.

Time and space complexity
Search algorithms through arrays
Abstract data types, data structures: stacks, queues, dynamic arrays, linked lists
Sorting algorithms
Recursion
Recursive data types
Computaional complexity of recursive algorithms, recurrence equations
Binary trees and dictionnaries
Invariants

Teaching methods

Lectures
Practical sessions on the Inginious server
One project at the end of the semester

Evaluation methods

A note of PARTICIPATION reflects the involvement of the student during the year for solving the practice problems on Inginious and when implementing the final project.

In the first session, the participation grade is worth 20% of the final grade + 80% for the final exam.

The participation mark can not be reassessed.

In the second session, participation grade and the final exam are worth respectively 10 % and 90% of the overall score.

The (closed book) final exam is a written exam on a computer or, when appropriate, on paper.

Online resources

moodle.uclouvain.be/course/view.php?id=1916

Bibliography

Il n'y a pas d'ouvrage de référence obligatoire mais, à titre complémentaire, des ouvrages sont recommandés sur le site Moodle.

Teaching materials

Les supports obligatoires sont constitués de l'ensemble des documents (transparents des cours magistraux, énoncés des travaux pratiques, compléments, ...) disponibles depuis le site Moodle du cours.
Required teaching material include all documents (lecture slides, project assignments, complements, ...) available from the Moodle website for this course.

Faculty or entity

INFO

Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme

Sigle

Credits

Prerequisites

Learning outcomes

Master [120] in Linguistics

LING2M

Additionnal module in Geography

APPGEOG

Minor in Computer Sciences

MINSINF

Minor in numerical technologies and society

MINSTIC

Bachelor in Computer Science

SINF1BA

Bachelor in Mathematics

MATH1BA