Study programme 2017-2018 | Français | ||
Approximation Algorithms | |||
Programme component of Master's Degree in Mathematics à la Faculty of Science |
Code | Type | Head of UE | Department’s contact details | Teacher(s) |
---|---|---|---|---|
US-M1-SCMATH-011-M | Optional UE | MELOT Hadrien | S825 - Algorithmique |
|
Language of instruction | Language of assessment | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Credits | Weighting | Term |
---|---|---|---|---|---|---|---|---|---|
| Français | 30 | 15 | 0 | 0 | 0 | 6 | 6 | 2nd term |
AA Code | Teaching Activity (AA) | HT(*) | HTPE(*) | HTPS(*) | HR(*) | HD(*) | Term | Weighting |
---|---|---|---|---|---|---|---|---|
S-INFO-021 | Approximation Algorithms | 30 | 15 | 0 | 0 | 0 | Q2 | 100.00% |
Programme component |
---|
Objectives of Programme's Learning Outcomes
Learning Outcomes of UE
At the end of the course, the students will be initiated to the design and performance analysis of basic approximation algorithms for NP-hard optimization problems.
Content of UE
See unique learning activity.
Prior Experience
Knowledge in complexity theory, for instance, course "Calculabilité et Complexité".
Type of Assessment for UE in Q2
Q2 UE Assessment Comments
Oral examination 100% (theory 70%, exercices 30%)
Type of Assessment for UE in Q3
Q3 UE Assessment Comments
Oral examination 100% (theory 70%, exercices 30%)
Type of Teaching Activity/Activities
AA | Type of Teaching Activity/Activities |
---|---|
S-INFO-021 |
|
Mode of delivery
AA | Mode of delivery |
---|---|
S-INFO-021 |
|
Required Reading
AA | |
---|---|
S-INFO-021 |
Required Learning Resources/Tools
AA | Required Learning Resources/Tools |
---|---|
S-INFO-021 | Not applicable |
Recommended Reading
AA | |
---|---|
S-INFO-021 |
Recommended Learning Resources/Tools
AA | Recommended Learning Resources/Tools |
---|---|
S-INFO-021 | Not applicable |
Other Recommended Reading
AA | Other Recommended Reading |
---|---|
S-INFO-021 | - Williamson, Shmoys, The Design of Approximation Algorithms, Cambridge University Press (2011). Electronic version available online: www.designofapproxalgs.com - Ausiello, Crescenzi, Gambozi, Kann, Marchetti-Spaccamela, Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer (1999) - Vazirani, Approximation Algorithms, Springer (2001) |
Grade Deferrals of AAs from one year to the next
AA | Grade Deferrals of AAs from one year to the next |
---|---|
S-INFO-021 | Authorized |