IU:TestPage

Theoretical Computer Science

• Course name: Theoretical Computer Science
• Course number: BS-18

Course Characteristics

Key concepts of the class

• Automata Theory
• Formal Grammars
• Computability

What is the purpose of this course?

A good software developer ignorant of how the mechanics of a compiler works is not better than a good pilot when it comes to fix the engine and he will definitively not be able to provide more than average solutions to the problems he is employed to solve. Like automotive engineering teach us, races can only be won by the right synergy of a good driving style and mechanics. Most importantly, limits of computation cannot be ignored in the same way we precisely know how accelerations, forces and frictions prevent us from racing at an unlimited speed. This course will investigate the prerequisites to understand compilers functioning. Although the act of compilation appears deceptively simple to most of the modern developers, great minds and results are behind the major achievements that made this possible. All starts with the Epimenides paradox (about 600 BC), which emphasizes a problem of self-reference in logic and brings us to the short time window between WWI and WW2 when, in 1936, Alan Turing proved that a general procedure to identify algorithm termination simply does not exist. Another major milestone has been reached by Noam Chomsky in 1956 with his description of a hierarchy of grammars. In this long historical timeframe we can put most of the bricks with which we build modern compilers. The course will be an historical tour through the lives of some of the greatest minds who ever lived on this planet.

Course objectives based on Bloom’s taxonomy

- What should a student remember at the end of the course?

By the end of the course, the students should be able to

• Define a formal language
• List different computational models
• Define computational models such as Finite State Automata and Pushdown Automata
• List different types of Formal Grammars
• Define computability and related concepts
• List applications for automata theory and formal grammar

- What should a student be able to understand at the end of the course?

By the end of the course, the students should be able to

• Describe the basic mathematical machinery behind automata theory and how can be applied to programming languages compilers
• Explain Strengths and weaknesses of specific computational model
• Explain Finite State Automata and Pushdown Automata
• Abstract systems using the given models

- What should a student be able to apply at the end of the course?

By the end of the course, the students should be able to

• Formally modelling a system
• Reasoning about verification of program properties
• Specifying a system as Finite State Automata, Pushdown Automata or Turing Machine
• Coding in programming languages an emulator of Finite State Automata
• Using proof techniques by diagonalization

Course evaluation

Course grade breakdown

type	points
Labs/seminar classes	40
Interim performance assessment	30
Exams	30

Grades range

Course grading range

grade	low	high
A	80	100
B	65	79
C	50	64
D	0	49

Resources and reference material

• Handouts supplied by the instructor
• \bibentry{houl79}
• \bibentry{Martin94}
• \bibentry{Hromkovic09}