MENU

Course Jukebox

Course Jukebox

Course Detail

Degree
Master
Standard Academic Year
Semester 3
Course delivery methods
face-to-face
Subject
Computer Science
Program
School
College of Science and Technology
Department
Campus
Campus Talence
Classroom
Course Offering Year
2022-2023
Course Offering Month
September - January
Weekday and Period
Capacity
Credits
6 ECTS
Language
English
Course Number
4TIN915U

Applied Algorithmics and Complexity University of Bordeaux

Course Overview

The goal of this course is to give somewhat generic algorithmic
techniques to deal with computational intractability (typically, 
NP-completeness) when one needs practical solutions. The focus is on
techniques with guaranteed performance: either exact algorithms, or
algorithms with a guaranteed approximation ratio.

Learning Achievement

Competence

Course prerequisites

Grading Philosophy

Short written examination, practical work (writing software to solve
some NP-hard problem).

Course schedule

Examples of NP-hard and NP-complete problems. Examples of
polynomial-time reductions. Exact solving techniques: exhaustive
search, SAT-solvers, pseudo-polynomial algorithms. Optimization
problems and approximation algorithms. Introduction to fixed-
parameter tractability (FPT).

Course type

> Lectures and practical work: - 48 hours of face-to-face teaching. - 100 hours personal work.

Online Course Requirement

Instructor

Other information

- Level B2 CEFR in English.
- Previous studies (Bachelor level) within the domain of computer
science or similar.
- Basic knowledge of algorithmic techniques and complexity theory.

Duration: 12 weeks

Language of instruction: English
Mode of delivery: Face-to-face teaching: personal work

Site for Inquiry

Please inquire about the courses at the address below.

Contact person: Philippe Duchon
philippe.duchon@u-bordeaux.fr