Efficient Programs (185.190 VU, 194.189 PR)

Curricula

The VU is a mandatory elective course in the Curricula "Data Science", "Visual Computing", and "Software Engineering". It is an elective course in the curriculum "Computational Science and Engineering".

The PR is a mandatory elective course in the Curriculum "Software Engineering". In that curriculum the VU and the PR together form the module "Efficient Programs".

If you want to perform the PR, my recommendation is to perform it in the same semester as the VU. The material from the VU will be fresh on your mind, and the PR helps to avoid forgetting it. You will also have an easier time finding other students.

Übergangsbestimmungen (transitional regulations) for the curriculum "Software Engineering": If you have successfully completed the VU in 2024W or earlier, that satisfies the requirements for the module "Efficient programs", but will only give you 3ECTS (see point 7 of Übergangsbestimmungen). I do not recommend taking the PR in this case; you already have learned what the PR is intended to teach, and the "studienrechtliches Organ" may decide that completing the old VU is equivalent to completing the PR and that you cannot use both of them for the same curriculum (see point 4 of Übergangsbestimmungen). Mandatory elective course in the Curricula "Computational Science and Engineering" (Module "Computational Informatics")), "Data Science" (Module "Big Data and High Performance Computing - Core"), "Logic and Computation" (Module "Programming Languages and Verification") "Software Engineering and Internet Computing" (Module "Computersprachen und Programmierung"), as either "VU Efficient Programs" or "VU Effiziente Programme". It has 2 hours (SWS) and 3 ECTS.

Time

Registration in TISS: VU, PR.

Lecture time: Mon, 16:15-18:00, starting on 2024-10-07, EI 2 (Old EI, Gusshausstrasse 25, 2nd floor). The VU lectures will happen until early December.

Afterwards the presentations of the PR will happen at the same time of the week at the same location. Attendance is required for these presentations.

TUWEL

There is a TUWEL course that you can reach through the TISS page. All the participants of the VU are automatically insribed to the TUWEL course.

Videos

Lectures in German from the 2020W and 2021W semesters are available online. Note that the lecture changes over time, so if you follow only these videos, you will miss some of the current content; you will also miss the option of asking questions. The videos may still be useful if you have an easier time with German, or if you miss a lecture.

Learning outcomes

After successful completion of the course, students are able to determine whether a program is sufficiently efficient, to find inefficient parts, and to make them more efficient.

Contents

Is efficiency needed? Kinds of efficiency. The effect of specification on efficiency. Design for efficiency. The role of efficient algorithms (constant factors, logarithmic factors). Hardware characteristics (cache, block sizes, registers, bandwidth, latency). Microoptimizations. Tools.

Grading

For the VU you have to perform some exercises where you have to deliver some results. The grade will be based on an oral exam that checks your knowledge of the course material, as well as whether you can explain how you achieved the exercise results.

For the VU exercises, and also for the PR you will get an account on g0.complang.tuwien.ac.at; the accounts are generated in batches on Tuesdays. Register ASAP to get your account soon.

The rest of this section is only relevant for the PR:

A group of 3-5 students optimizes a program and presents the result. The grade is based on the presentation. The presentation should point out which optimization steps worked how well, compare this to your expectations, and ideally also have an explanation of why an optimization step worked better or worse than expected.

While algorithmic optimizations are not the topic of this course, they are allowed (and, for the given exercise program, usually expected). One way to deal with that is to write the code resulting from an algorithmic optimization in a straightforward way, and then performing additional non-algorithmic optization steps that you can evaluate and present.

You can optimize a program of your choice.

Exercises

Results Directory

If you want to publish your PR work (not graded), it is probably best to do that on platforms like Sourcehut or Github.

It would be nice if you also create a short page with a link to your work or a directory with your work in /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2025w/ (on the g0). This directory can be seen here in the WWW.

Results from earlier years

Literature

Lecturer

Anton Ertl