Course Outline

The course is an introduction into the very large domain of software specifications. We cover the basics that will be built upon in several advanced courses on topics including theoretical computer science, compiler design, software engineering, and formal methods. The goal of the course is to offer to all CS students a basic understanding of many of the “hard” topics in computer science.

The course is therefore divided into two main parts: The first part offers an introduction into specification and systematic development of recognizers for formal languages using regular expressions, grammars, and automata, while the second part addresses specification, verification, and development of simple algorithms using pre- and post-conditions and loop invariants. Some further incursions into program verification will also be contemplated.

The following is a however tentative schedule:

Introduction to formal languages 1 week
Regular languages and state transition diagrams 2 weeks
Context-free languages 2 weeks
Introduction to specifications 1 week
Reasoning about specifications 2 weeks
Examples of algorithms 1 week
Formal methods 2 weeks
Introduction to computability 1 week