Course full name: Comprehensive Course in Computer Science - Theoretical Computer Science
Course acronym: CCinCS-TCS

Study program: Computer Science (doctoral)
Course type: preparatory
Year: 1st

Credit points (ECTS): 6 (as one of four parts of the Comprehensive Course)
Duration: N/A
Academic year: 2020/21

Professor: assist. prof. Branko Kavšek
Assistant: N/A

Course contents (short):

Finite automata and regular expressions:

  • Computation model, finite automaton – DFA and NFA
  • Alphabet, language, regular expression/language
  • The relation between DFA, NFA and regular expressions
  • Using FA to solve problems
  • RE pumping lemma, non-regular languages

Grammars, context (non)free languages and stack automata:

  • Grammar, derivation tree, attribute grammar
  • Context-dependent and context-free languages, stack automaton
  • Grammar normal forms: Greibach, Chomsky (CNF)
  • Transforming grammars into CNF
  • CYK algorithm
  • Pumping lemma for CFG
  • Operations on languages (intersection, union …)

Turing machines and their languages:

  • Turing machine and its derivations, RAM
  • Church-Turing thesis
  • Recursively enumerable languages, Chomsky hierarchy
  • Unsolvable and undecidable problems, the stopping problem, Rice theorem and PCP

Introduction to the theory of complexity:

  • P and NP – relation between them
  • Problem translation, NP completeness
  • NP complete problems

Objectives and competences:

The main objective of this course is that it serves as a preparatory course for the Theoretical Computer Science part of the Comprehensive Exam in Computer Science.

Goals:

  • The student gets to know the formal models basics as well as the notions of computability, decidability, P and NP.
  • He develops the ability to work in groups and is able to confidently use the acquired knowledge.
  • He is given the prerequisites to in-depth understanding of computer science.

General competences:

  • Abstract and analytical thinking.
  • The ability to define and formalize a problem.

Subject-specific competences:

  • The ability to build a model for solving the problem at hand.
  • The ability to construct formal proofs.

Intended learning outcomes:

Knowledge and understanding:

  • Basic notions of theoretical computer science.
  • Knowing and considering limitations of a computer as a machine.

Usage:

  • The student is capable of framing the model basics for solving the given problem.
  • Translation of one problem to another.

Student's obligations:

  • Written exam at the end of the lectures (can be substituted by two midterms - 1st at mid course, 2nd at the end of the course)
  • Home-works (after individual lectures)
  • Quizzes (after individual lectures)
  • Oral exam (on student's demand)

Obtaining the final grade:

Activity Part of grade Condition
Written exam / 2 midterms 50% More than half of all points,
but not less that 40% of all
points on individual midterm.
Home-works
(after lectures / 9 in total)		 35% Submitted in time = all points;
until 1 week late = half of the points;
more than 1 week late = zero points
(submission closed).
Quizzes
(after lectures / 5 in total)		 15% Submitted in time = all points;
No late submission possible.
Oral exam 0% If student wants to raise the final grade
(not possible to raise more than 1 grade). 
Total: 100% All conditions fulfilled.


Literature:

  1. John C. Martin, Introduction to Languages and the Theory of Computation (fourth edition), McGraw-Hill, 2010.
  2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (third edition), Addison-Wesley, 2006. (:-))

Last modified: Friday, 8 January 2021, 1:51 PM