Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2018/2019

Experimental algorithmics

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
PI-EXA ZK 4 2+1 Czech
Lecturer:
Jan Schmidt (guarantor)
Tutor:
Jan Schmidt (guarantor)
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/
Time-table for winter semester 2018/2019:
Time-table is not available yet
Time-table for summer semester 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri
Thu
roomTH:A-942
Schmidt J.
11:00–12:30
(lecture parallel1)
Thákurova 7 (FSv-budova A)
Fri
The course is a part of the following study plans:
Data valid to 2019-05-23
For updated information see http://bilakniha.cvut.cz/en/predmet4807306.html