Subject

Foundations of Computer Science Theory

Course Title

Foundations of Computer Science Theory
Basics of theory of computing

Code

F23L3S039

Study Programme

Computer Science

Organizer of the study programme (unit, institute, department or division)

Faculty of Computer Science and Engineering

Degree level (first, second, third cycle)

First Cycle

Academic year / semester

6 / Summer

Number of ECTS credits

Teacher

Maria Mihova, Mile Jovanov

Prerequisites for enrolling in the course

Discrete Mathematics or Discrete Structures 2 or Mathematics 2 or Selected Topics in Mathematics

10.

Objectives of the course programme (competences)

In this course, you will gain a basic understanding of the classical models used in computer science to analyze computational processes, including finite automata, grammars, and Turing machines. These models can be used to answer questions such as which problems can be solved by a computer and whether there are some problems that are inherently harder to solve than others.

11.

Course content

1. Basic concepts of languages, grammars, and automata
2. Regular expressions and regular languages
3. Deterministic Finite Automaton
4. Nondeterministic Finite Automata, Equivalence between Deterministic and Nondeterministic Finite Automata, and Reduction of the Number of States.
5. Properties of regular languages. Lemma for pumping in regular languages.
6. Context-free languages
7. Push-down machines
8. Connection between context-free languages and push-down automata
9. Pumping lemma for context-free languages and a closure.
10. Turing machines.
11. Hierarchy of languages (recursive languages, context-sensitive...)
12. Introduction to Computational Complexity (P, NP)
13. Calculatingness.

12.

Learning methods

Lectures using presentations, interactive lectures, exercises (using equipment and software packages), teamwork, case studies, guest lectures, independent preparation and defense of a project assignment and a seminar paper.

13.

Total available time

6 ECTS x 30 hours = 180 hours

14.

Distribution of available time

30 + 45 + 15 + 15 + 75 = 180 hours

15.

Forms of teaching activities

15.1.	Lectures - theoretical instruction	30 hours
15.2.	Exercises (laboratory, auditory), seminars, teamwork	45 hours

16.

Other forms of activities

16.1.	Project assignments	15 hours
16.2.	Independent assignments	15 hours
16.3.	Home study	75 hours

17.

Assessment method

17.1.	Tests	0 points
17.2.	Seminar paper / project (presentation: written and oral)	15 points
17.3.	Activities and learning	0 points
17.4.	Final exam	90 points

18.

Grading criteria (points / grade)

up to 50 points	5 (five) (F)
from 51 to 60 points	6 (six) (E)
from 61 to 70 points	7 (seven) (D)
from 71 to 80 points	8 (eight) (C)
from 81 to 90 points	9 (nine) (B)
from 91 to 100 points	10 (ten) (A)

19.

Requirement for obtaining a signature and taking the final exam

Activities 15.2 and 16.1 completed

20.

Language of instruction

Macedonian and English

21.

Method for monitoring the quality of teaching

internal evaluation and survey mechanism

22.

Literature

22.1.	Required literature 1. Michael Spiser \| Introduction to the Theory of Computation \| Cengage \| 2012 2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman \| Introduction to Automata Theory, Languages, and Computation \| Addison-Wesley \| 2006 3. https://www.geeksforgeeks.org/introduction-of-finite-automata/?ref=lbp \| geeksforgeeks \| 2022 4. B. Yaneva \| Algorithms and Automata \| PMF Skopje \| 1999
22.2.	Additional literature No. Author Title Publisher Year