DM852: Introduction to Generic Programming

Study Board of Science

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340038102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master

STADS ID (UVA): N340038101
ECTS value: 5

Date of Approval: 27-10-2022


Duration: 1 semester

Version: Approved - active

Entry requirements

None

Academic preconditions

Students taking the course are expected to
  • have knowledge of and competences in object-oriented programming.
  • have basic knowledge of and skills in system programming functional programming.
  • have knowledge of computer architecture and basic compiler construction.
  • have knowledge of common algorithms and data structures, and basic skills in their implementation.
  • 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 with concrete types. Templates in C++ is a compile-time mechanism that makes it possible to implement generic algorithms on a high abstraction level, which are statically type safe and have minimal runtime overhead.

The course builds on competences in programming, computer architecture, system programming, algorithms and data structures, and compiler construction, with the aim of combining them to enable the student to make reusable practical
implementations of common algorithms and data structures.

In relation to the learning outcomes of the degree the course has explicit focus on
  • expert knowledge in a defined subject area that is based on the highest international field of research within the field of computer science.
  • to be able to understand and on a scientific basis reflect on the knowledge of the field of computer science and be able to identify scientific issues.
  • describe, analyze and solve advanced computer science problems using the learned models.
  • analyze advantages and disadvantages of different computer science methods, also within academically complex areas.
  • develop new variants of the learned methods where the specific problem requires it.
  • disseminate research-based knowledge and discuss professional and scientific issues with both peers and non-specialists.
  • plan and carry out scientific projects at a high professional level, including managing work and development situations that are complex, unpredictable and require new solution models.
  • be able to take responsibility for own professional development and specialization.

Expected learning outcome

After the course the student is expected to have the following.

Knowledge of
  • the object model of C++, and the overall differences to models in other common programming languages.
  • the basic the use of exceptions in C++ and their interaction with the object model and resource management.
  • different types of polymorphism on a basic level.
  • the foundational principles for generic programming in C++, including the difference between abstract descriptions, descriptions using concepts, and concrete implementations of algorithms and data structures.
  • foundational concepts for generic data structures in C++, including regularity and iterators,
  • overall differences in support for generic programming in common programming languages.
  • basic use of template meta-programming in C++ for solving concrete problems.
Skills in
  • programming in C++ using modern facilities of the language and common idioms.
  • implementation of generic data structures that model given concepts.
  • implementation of generic algorithms using interfaces defined by given concepts.
  • basic implementation of concept checking of data structures.
  • basic use of template meta-programming in C++ for solving concrete problems.

Competences in

  • basic design of generic data structures that model given concepts.
  • basic design of generic algorithms using interfaces defined by given concepts.
  • basic documentation of generic data structures that model given concepts.
  • basic documentation of generic algorithms using interfaces defined by given concepts.
  • basic evaluation of practical efficiency of generic algorithms and data structures, both with respect to space and time.
  • communication and discussion of basic design decisions for generic algorithms and data structures.
  • obtaining further knowledge on generic programming.

Content

The following main topics are contained in the course.
  • Programming in C++, including use of the standard library, and the ideas behind part of its implementation.
  • Templates, type deduction, and type safety.
  • Error handling.
  • Resource handling (e.g., memory).
  • Common generic data structures.
  • Common generic algorithms.
  • Metaprogramming.

Literature

See itslearning for material and additional literature references.

Examination regulations

Exam element a)

Timing

Spring and June

Tests

Portfolio and test

EKA

N340038102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Examination aids

 Allowed, a closer description of the exam rules will be posted in itslearning.

ECTS value

5

Additional information

Portfolio consists of: Final project and assignments.
A number of assignments submitted during the course as well as a final project. Grade is based on an overall impression of the components that are used in the evaluation, but with the highest weighting of the final project. The external examiner will have access to the answers to the assignments.
The reexam will have the same format as the ordinary exam with a number of assignments and aproject, but the deadline will be during the reexam period.

Indicative number of lessons

40 hours per semester

Teaching Method

On the Faculty og Science the teaching method is based on three phase model, that is intro, training, and study phase.
  • Intro phase: 30 hours of lectures.
  • Training phase: 10 hours of laboratory exercises.
Activities during the study phase:
  • Using the acquired knowledge to develop skills and competences in exercises and projects.
  • Reading and discussing the scientific articles, book chapters, and other material.

Teacher responsible

Name E-mail Department
Jakob Lykke Andersen jlandersen@imada.sdu.dk Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.