Experimental algorithmics

Garant předmětu:

Lecturer:

Tutor:

Supervisor:

Department of Digital Design

Synopsis:

The course explains experimental evaluation of algorithms and programs, its significance for scientific work and interpretation of its results. Standards of relevance and confidence established in experimental science are transferred to this field.

Requirements:

MI-PAA, BI-GRA, BI-PST or an equivalent in complexity theory, graph theory, and statistics.

Syllabus of lectures:

1. Experimental algorithmics: why

2. Experimental algorithmics: how

3. Experiments on objects with known variance characteristics

4. Random instance generation

5. Experiments on objects without guaranteed variance characteristics

6. Hidden sources of variance

7. Variance reduction methods

8. Simulation shortcuts and acceleration

9. Characterizing experimental results

10. Presenting and visualizing experimental results

11. Examples of experimental studies I.

12. Examples of experimental studies II.

Syllabus of tutorials:

1. Topics presentation, projects planning

2. Project work

3. Project review

4. Project work

5. Project work

6. Presentation and conclusions

Study Objective:

The basic contribution of the course are knowledge and techniques bringing reliable and relevant results in experimental work, which can support scientific work without doubts and objections from the research community. Other techniques reducing the effort needed to achieve given confidence level are also discussed. As human perception is capable of noticing important characteristics and dependencies, visualization and presentation methods are explained. The tutorial are project-based; several project topics are offered but topics originating from students' own research are preferred.

Study materials:

Catherine C. McGeoch: A Guide to Experimental Algorithmics. Cambridge University Press, 30. 1. 2012 261p.

Note:

Further information:

https://moodle.fit.cvut.cz/PI-EXA/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Informatics (doctoral) (compulsory elective course)
• Informatics (compulsory elective course)