Course detail

Programming Seminar

FIT-IPSAcad. year: 2020/2021

Dynamic memory allocation, pointer and reference data type. Activation record and recursion. Compilation, binary program invocation. Implementation of state automata. Implementation of algorithms for regular expressions. Program synchronization. Principles of threads and processes. Selected synchronization issues. Introduction to message passing interface. Problematics of page faults and related performance effects.

Learning outcomes of the course unit

  • The student is able to explain the problems of program execution, she/he can explain dynamic memory allocation.
  • Student can use state automata in program control.
  • Student manages the application of regular expressions.
  • Student manages implementation of parallel programs.
  • The student is able to identify a decrease in program performance due to memory accesses.

Prerequisites

Programming in C language. Fundamentals of algorithmization. Basic synchronization primitives. Computer architecture.

Co-requisites

Not applicable.

Recommended optional programme components

Not applicable.

Recommended or required reading

A. Kumar, A. K. Verma. A Novel Algorithm for the Conversion of Parallel Regular Expressions to Non-deterministic Finite Automata. 2014. doi: 10.1.1.403.6706
Kernighan and Ritchie. The C Programming Language, 2nd edition. Chapter A. Storage Allocator for C maloc and free. 1989.
Kernighan, B.; Ritchie, D.: The C Programming Language, 2nd edition. Kapitola A. Alokátor paměti pro maloc a free v C. Addison-Wesley, 1989.
Michael, M.M.: Scalable lock-free dynamic memory allocation. 2004. In Proc. of PLDI'04. doi: 10.1145/996841.996848
Maged M. Michael. Scalable lock-free dynamic memory allocation. In Proc. of PLDI'04. doi: 10.1145/996841.996848
Drepper, D.: What Every Programmer Should Know About Memory, 2007.
Ulrich Drepper. What Every Programmer Should Know About Memory, 2007.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

  • Evaluation of the two home assignments (max 35 points)
  • Evaluation of the two home assignments (max 30 points)

Exam prerequisites:
The minimal total score of 50 points gained during a semester and 5 points for each of home assignments.

Language of instruction

Czech, English

Work placements

Not applicable.

Aims

The goal of the course is to provide a different point of view to key principles of programming and operating systems. In particular, with respect to the abstraction of algorithms and formal automata and models, to reach the connection of theoretic and practical knowledge of a given topic.

Classification of course in study plans

  • Programme BIT Bachelor's, 2. year of study, winter semester, 2 credits, elective

  • Programme IT-BC-3 Bachelor's

    branch BIT , 2. year of study, winter semester, 2 credits, elective

Type of course unit

 

Seminar

20 hours, optionally

Teacher / Lecturer

Syllabus

  1. Pointers, dynamic memory allocation.
  2. Stack frames, recursion.
  3. Compilation and debugging of programs.
  4. --
  5. Demonstration and solution of a given task.
  6. Finite automata, POSIX regular expressions.
  7. Synchronization of processes.
  8. Deadlock.
  9. --
  10. Demonstration and solution of a given task.
  11. Page tables.
  12. Demand paging and cache in relation to performance.
  13. Demonstration and solution of a given task.

Project

6 hours, compulsory

Teacher / Lecturer