Skip to the content of the web site.

Lecture materials

The course text is provided by the course instructor.

A Practical Introduction to Real-time Systems for Undergraduate Engineering.

The most recent version is dated July 31, 2018. It is 745 pages long.

The printed version of the text is here. It is only 615 pages long.

You may also wish to look at the original course design document.

An earlier version of the text contained source code in the appendices describing reasonable implementations of a number of data structures for use in real-time embedded systems. The real-time component requires that the algorithms have guaranteed and reasonable upper bounds on their run times, and the embedded aspect requires that recursive calls are not allowed and that all memory, generally, is allocated when the data structure is initialized. Everything is implemented in C and macros are used instead of functions where appropriate, and assertions are liberally used.

  1. Singly linked list with an iterator
  2. Stack
  3. Generic stack
  4. Queue
  5. Generic queue
  6. Heap-based priority queue
  7. Array-based priority queue
  8. Disjoint set
  9. Sorting algorithms
  10. B-dagger tree (incomplete)
  11. Sorted list with an iterator

My favorite data structure is the last: it is an implementation similar to that of the type std::map<int, void *> in the C++ Standard Template Library. It does not use recursion, but instead uses a stack. There is an additional discussion as to how even the memory of the stack can be removed, but at the cost of having the run-time of insert and erase being increased to $O(\lg^2(n))$ time. The data structure is also designed to ensure that the sorted list can be itterated through in $O(n)$ time, but discussing how the extra memory required can be removed so long as iterating through the sorted list need only be accomplished in $O(n \lg(n))$ time.