Search programme

​Use the search function to search amongst programmes at Chalmers. The programme overview and the programme syllabus relating to your studies are generally from the academic year you began your studies.

​​​

Syllabus for

Academic year
DAT020 - Programming as mathematics
 
Owner: TITEA
3,0 Credits (ECTS 4,5)
Grading: UG - Fail, pass
Level: C
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: English
Minimum participants: 20
Maximum participants: 40

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0105 Examination, part A 1,0 c Grading: UG   1,0 c    
0205 Written and oral assignments, part B 2,0 c Grading: UG   2,0 c    

In programs

TITEA SOFTWARE ENGINEERING, Year 3 (elective)
TITEA SOFTWARE ENGINEERING, Year 4 (elective)

Examiner:

Docent  Sibylle Schupp



Eligibility:

For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.

Course specific prerequisites

- Mathematics: high-school level mathematics suffices; all required mathematics from abstract algebra and number theory will be developed in the class
- A working knowledge of basic C++ is required for the course: the programming exercises will be in C++
- Basic knowledge of data structures and algorithms

Aim

The purpose of the course is to present programming as a mathematical activity to students and professional programmers who want to advance their understanding.

Goal

Today's programmer is trained in a variety of sub-disciplines of computer science and mathematics. Unfortunately, such training is rather fragmented. The key objective of this course is to illustrate the unity between these disciplines, i.e., to show that every good programming technique sits on some solid mathematics and that practical pieces of code are in reality defined on algebraic structures. We will also demonstrate historical developments of these mathematical ideas and reveal mathematics and computer science as human activities. Students will learn to
- recognize the mathematics behind programming problems
- decompose a problem into correct and reusable components
- design and implement efficient, abstract, and robust interfaces
- develop programming esthetics based not on current fads, but on the ancient mathematical tradition

Content

- Mathematical foundations: natural numbers, Peano axioms, generalized Peano types; primitive recursion and primitive iteration as fundamental forms of computation
- Combinatorics; exponentiation and the Russian peasant algorithm; the Fibonacci sequence and its relation to the golden ratio and to vector spaces; elementary number theoretic and cryptographic algorithms
- Generalizing numbers to iterators: the mathematical theory behind copying, finding, moving, and other basic operations; classification of iterators; simple sequential algorithms; the mathematics of optimizations
- Permutations: the cyclic structure of permutations; reverting, rotating, partitioning algorithms; bottom-up divide-and-conquer decomposition techniques
- Data structures; implementation of vectors; whole-part semantics; the laws of regular types and the notion of construction, assignment, and equality
- "Concepts": the extension of a mathematical notion of algebraic structures to the universe of programming

Organisation

Intensive course (3 hrs lectures & 3 hrs recitation/exercises per day). The first week will be an intensive C++-reminder, to bring everyone up to speed.

Literature

The following books will help students not just for the course, but for the rest of their professional lives:
- George Chrystal, Textbook of Algebra, volumes 1 and 2
- Donald Knuth, The Art of Computer Programming, volumes 1-3

Examination

Pass/Fail


Page manager Published: Thu 03 Nov 2022.