DM852: Introduction to Generic Programming (5 ECTS)

STADS: 15018701

Level
Master's level course

Teaching period
The course is offered in the autumn semester.

Teacher responsible
Email: jlandersen@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None.

Academic preconditions:
Students taking the course are expected to:

• have knowledge of object-oriented programming, basic system programming, and basic functional programming.
• have knowledge of computer architecture and basic compiler construction.
• be able to judge the complexity of algorithms, with regard to runtime as well as with regard to space usage.

Course introduction
The purpose of the course is to enable the student to implement efficient generic algorithms and data structures in C++. In generic programming an algorithm can be described in terms of abstract types that are only instantiated when the algorithm is used. Templates in C++ is a compile-time mechanism that makes it possible to implement high-level generic algorithms, which are statically type safe and have minimal runtime overhead.

The course builds on the programming knowledge obtained in previous courses and uses concepts, e.g., from DM552 Programming Languages, DM546 Compiler Construction, and DM548 Computer Architecture and System Programming. The course provides the student with a good foundation for the practical implementation of algorithms and data structures, e.g., in a Master's thesis.

In relation to the learning outcomes of the degree the course has explicit focus on giving the students the knowledge, competences, and skills in order to

• describe, analyse, and solve advanced computer scientific problems using the models they have learned.
• shed light on stated hypotheses with a qualified theoretical basis and be critical of both own and others research results and scientific models.
• develop new variants of the learned methods, where the concrete problem requires it.
• disseminate research-based knowledge and discuss professional and scientific problems with both colleagues and non-specialists.
• plan and execute scientific projects of high standard, including managing work situations that are complex, unpredictable, and require novel solutions.
• take responsibility of own professional development and specialisation.

Expected learning outcome
The learning objectives of the course are that the student demonstrates the ability to:

• demonstrate foundational knowledge of the principles for generic programming.
• design, implement, and document generic data structures that models given concepts.
• design and implement generic algorithms and document them using concepts.
• understand and use basic template meta-programming in C++ for solving concrete problems.

Subject overview
The following main topics are contained in the course:

• Programming in C++, including use of the standard library and Boost
• Templates, type deduction, and type safety
• Error handling
• Resource handling (e.g., memory)
• Generic algorithms
• Metaprogramming

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Project assignments. Pass/fail, internal marking by the teacher.

Assessment and marking:
Project report. External marking, Danish 7-mark scale.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 28 hours
Skills training phase: 20 hours, hereof:
 - Tutorials: 8 hours
 - Laboratory exercises: 12 hours

Educational activities

Educational form
Activities during the study phase:

• Using the aquired knowledge in projects.
• Discussing the scientific articles/book chapters.

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.