Computational Foundations I

Aim of this Lecture

This lecture introduces basic program elements like machine models, variables, pointers, objects, and control structures with very basic programming exercises in C/C++. It includes very basic exposition to recursion, event-driven programming (interrupts, event queue, etc.), and functional programming as well. We will introduce algorithms as examples covering Part I Foundations from the seminal book “Introduction to Algorithms” (Cormen et al.). Then, C++11 data structures (map, queue, list, set, unordered sets, priority queue, tree) are introduced together with their algorithms (linear search, binary search, sorting, min-hash, balanced trees). as well as modern C++ control structures and their use (e.g., unique_ptr, shared_ptr, unique_lock, scoped_lock, counting_semaphore, latches, barriers etc.). In this way, a clear introduction to core principles of programming and common pitfalls is ensured as all these advanced structures have been introduced to avoid common pitfalls and inefficiencies.

Reference literature includes parts of Bjarne Stroustrups book “Programming”. In the tutorials, we will introduce selected algorithmic patterns (e.g., dynamic programming, integer programming, shortest paths, divide & conquer) as they are only to be understood by applying them to toy problems. Then we increase the versatility of students in computational engineering problems by introducing selected non-trivial algorithms. A chapter on correctness including treatment of rounding errors, infinite precision computation, and the Hoare calculus complete the lectures core exposition. Finally, students will get an overview (partly simplified) to the real world including special situations including embedded, GPU, FPGA, Supercomputer, and other challenging computational environments and what they imply for programming and software design.

Open Education

This course aims to provide parts of its content as Open Educational Resources (OER). Hence, find the script at Script Location

© 2020 M. Werner