Home
Colophon
Preface
Acknowledgements
Contents
1 Computer Arithmetic
1.1 Positional Notation
1.2 Binary Numbers
1.3 Addition and Subtraction
1.4 The Integers
1.5 Shifts
1.6 Summary
2 Machine Code
2.1 The von-Neumann Architecture
2.2 The RV32I ISA
2.3 The Assembler
2.4 Execution Traces
2.5 The Data Segment
2.6 Memory Segmentation
2.7 Linking
2.8 Calling Functions
3 Some Simple Algorithms
3.1 Number Conversion
3.2 The Sieve of Eratosthenes
3.3 Insertion Sort
3.4 Evaluating Polynomials with Horner’s Method
3.5 The Tortoise and the Hare
4 Introduction to C
4.1 Basics
4.2 Execution Traces
4.3 Imperative Variables
4.4 The C Memory Model
4.5 Translation Units
4.6 Number Types
4.7 Control Flow
4.8 Expressions
4.9 Calling Functions
4.10 Pointers
4.11 Examples
4.12 Dynamic Memory Management
4.13 Structs
4.14 Input and Output
4.15 Undefined Behavior
5 Algorithms and Data Structures
5.1 Lists
5.2 Trees
5.3 Hashing
5.4 Dynamic Programming
6 Formal Semantics
6.1 The Syntax of Programming Languages
6.2 The Abstract Syntax of C0
6.3 The Semantics of C0
6.4 Pointers (C0p)
6.5 Scopes (C0b)
6.6 A Simple Type System (C0t)
6.7 Summary and Further Reading
7 Testing and Verification
7.1 Functional Correctness
7.2 Failures
7.3 Testing
7.4 Verification
8 Object-Oriented Programming with Java
8.1 Compilation, Main Method, Packages
8.2 Types
8.3 Reference Types
8.4 Classes
8.5 Encapsulation
8.6 References, Aliasing, and Immutable Objects
8.7 Inheritance
8.8 Overloading Methods
8.9 The Java Collections Framework
8.10 Using Object Orientation Properly
8.11 The Expression Problem and the Visitor Pattern
8.12 Object-Oriented Programming with C
9 A Simple Compiler
9.1 A Brief Overview of Syntactic Analysis
9.2 Type Checking
9.3 Syntax-Directed Code Generation
A RISC-V Assembler Reference
A.1 Instruction Set Reference
A.2 OS Calls
A.3 Assembler Directives
B ASCII Table
C Course Structure
C.1 I: Course Introduction
C.2 R1: Computer Arithmetic
C.3 R2: Computer Arithmetic
C.4 M1: Introduction to Machine Code Programming
C.5 M2: Simple Algorithms in Machine Code
C.6 M3: Function Calls
C.7 C1: Introduction to C
C.8 C2: Expressions and Pointers
C.9 C3: Arrays, Structs, I/O
C.10 A1: Lists and Trees
C.11 A2: Dynamic Programming
C.12 S1: C0 Syntax and Semantics
C.13 S2: Extending C0 to Pointers and Scopes
C.14 S3: Correctness
C.15 S4: Testing
C.16 J1: Intro to Java
C.17 J2: Immutable Objects, Interfaces, Subtyping
C.18 J3: Abstract Classes,
Object
, Overriding and Overloading Methods
C.19 J4: Using OO Properly, OO in C, The Expression Problem, Visitor Pattern
C.20 A3: Java Collections Framework and Hashing
C.21 A4: Project Specific
C.22 O1: Compiler Introduction (Syntax Analysis, Static Semantics)
C.23 O2: Type Checking Examples, Implementation of Type Checking
C.24 O3: Syntax-Directed Code Generation
C.25 V1: Hoare Logics
C.26 V2: Loop Invariants and Mechanizing Verification
Exercise Solutions
List of Symbols
Index
Literature
PDF
Course Website
An Introduction to Imperative Programming
Home
An Introduction to Imperative Programming
Sebastian Hack
Saarland University
September 16, 2026