Experimental algorithmics
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| PI-EXA | ZK | 4 | 2P+1C | Czech |
- Garant předmětu:
- Jan Schmidt
- Lecturer:
- Jan Schmidt
- Tutor:
- Jan Schmidt
- 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 2023/2024:
- Time-table is not available yet
- Time-table for summer semester 2023/2024:
-
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 Wed Thu Fri - The course is a part of the following study plans:
-
- Informatics (doctoral) (compulsory elective course)
- Informatics (compulsory elective course)