### Introduction to Theoretical Computer Science

#### Course Description

#### General Competencies

The course prepares the students for application of formal models in engineering for the design of computer and communication processes, protocols, and systems. Based on the problem definition, students will be able to construct the formal model of the proposed solution, validate its correctness, estimate its efficiency and complexity, implement it in software or hardware, as well as document and test it. Furthermore, students acquire solid fundamental knowledge that is the basis for further study of theory of complex computing processes and systems.

#### Learning Outcomes

- model the behavior of a computer system and communication protocol using formal language
- design a computing process using a formal model
- apply formal models to verify the corectness of a computer system
- categorize a problem with respect to Chomsky hierarchy of formal languages
- select the optimal formal model for description, design, and implementation of a computer system
- estimate time and space complexity of a computing process
- evaluate the efficiency of a computer system and communication protocol

#### Forms of Teaching

**Lectures**Lecturer-driven classroom presentations, examples of practical application of formal languages, automata, and grammars

**Exams**Two written exams

**Exercises**Lecturer-driven classroom problem solving, preparation for written exams

**Laboratory Work**Implementation of algorithms on formal languages, automata, and grammars. Application of automata and grammars in practical software development. Online submission and evaluation of student work.

**Consultations**Individual office hours with lecturers and assistants are organized on student's request.

#### Grading Method

Continuous Assessment | Exam | |||||
---|---|---|---|---|---|---|

Type | Threshold | Percent of Grade | Threshold | Percent of Grade | ||

Laboratory Exercises | 50 % | 30 % | 50 % | 0 % | ||

Class participation | 0 % | 5 % | 0 % | 0 % | ||

Mid Term Exam: Written | 0 % | 35 % | 0 % | |||

Final Exam: Written | 0 % | 35 % | ||||

Exam: Written | 50 % | 100 % |

##### Comment:

Continuous Assessment: Min (Mid Term Exam: Written + Final Exam: Written + Lecture attendance and oral examination in classroom) = 50 %

#### Week by Week Schedule

- Symbol, alphabet, string, and formal language; Example of formal language, automata, and grammar; ([1], pp. 1-14) Deterministic finite automata: example and definition; Deterministic finite automata: implementation and minimization; ([1], pp. 15-29)
- Determinism and nondeterminism; Nondeterministic finite automata; Nondeterministic finite automata with e-moves; ([1], pp. 29-39) Finite automata with output; Regular expressions; Finite automata generator; ([1], pp. 39-51)
- Properties of regular sets; Formal grammar: example and definition; Regular grammar; ([1], pp. 51-63) Regular grammar (continuation); Context-free languages; Context-free grammar; Grammar and language ambiguity; Simplification of context-free grammars; ([1], pp. 63-78)
- Simplification of context-free grammars (continuation); ([1], pp. 78-88) String derivation and parsing; Implementation of top-down parsing; Recursive-descent parsing; Bottom-up parsing; LR parsing; ([1], pp. 89-102)
- Pushdown automata: example and definition; ([1], pp. 103-114) Pushdown automata (continuation); Properties of context-free languages; ([1], pp. 114-125)
- Exercises: regular languages;
- Exercises: context-free languages;
- First mid term exam: regular languages, context-free languages;
- Recursively-enumerable languages; Turing machine; Techniques for constructing Turing machine; ([1], pp. 126-138) Generalization of basic Turing machine model; ([1], pp. 139-146)
- Restriction of basic Turing machine model; Turing machine based language generation; ([1], pp. 146-151) Unrestricted grammar; Properties of recursive and recursively-enumerable languages; Computability; Decidability; ([1], pp. 152-164)
- Context-sensitive languages; Context-sensitive grammar; Linear bounded automata; Properties of context-sensitive languages; ([1], pp. 165-172) Properties of context-sensitive languages (continuation); Chomsky hierarchy of formal languages, grammars, and automata; Definitions of space and time complexity; Complexity of automata and languages; Properties of space and time complexity functions; ([1], pp. 173-187)
- Complexity classes; ([1], pp. 187-190) Complexity properties of hierarchy of languages; ([1], pp. 190-194)
- Polynomial complexity classes; Tractability; Reduction method; Definition of complete and hard problems; P-complete (hard) and NP-complete (hard) problems; ([1], pp. 194-199)
- Exercises: recursively-enumerable languages, context-sensitive languages, complexity theory;
- Final exam: whole course matter;

#### Study Programmes

##### University undergraduate

#### Prerequisites

#### Prerequisites for

#### Literature

*Uvod u teoriju računarstva*, Element Zagreb

*Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography*, Springer

*Introduction to Automata Theory, Languages, and Computation*, Addison-Wesley

*An Introduction to Formal Languages and Automata*, Jones & Bartlett Publishers

*Automata and Computability*, Springer

#### Exercises

#### Laboratory exercises

#### General

**ID**86537

**6**ECTS

**L1**English Level

**L1**e-Learning

**45**Lectures

**15**Exercises

**15**Laboratory exercises

**0**Project laboratory

#### Grading System

**88**Excellent

**75**Very Good

**63**Good

**50**Acceptable