Week |
Subject |
Related Preparation |
1) |
Formation of preliminary concepts, mathematical tools, definitions, theorems and proofs, types of proofs |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
2) |
Deterministic finite automata (DFA) |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
3) |
Non-deterministic finite automata (NFA) |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
4) |
Equivalence of DFA and NFA and regular expressions |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
5) |
Epsilon transition, pumping Lemma, pigeon principle and closure features |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
6) |
Optimal DFA and overview |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
7) |
Context-free languages, context-free grammars, parse tree, ambiguity, closure properties |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
8) |
|
|
9) |
|
|
10) |
Overview of context-free grammars and the Church-Turing hypothesis |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
11) |
Stacked Vending Machines |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
12) |
Overview of context-free grammars and the Church-Turing hypothesis |
|
13) |
Turing Machines, Recognition and Computation, Church-Turing Hypothesis |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
14) |
Turing Machines, Recognition and Computation, Church-Turing Hypothesis |
|
15) |
NP-completeness, decidability, reducibility and recognizability |
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
16) |
|
Data Structures – A Pseudocode Approach with C, R. Gillberg, B. Forouzan, Thomson Course Technology Second Edition |
Course Notes / Textbooks: |
Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2012
Daniel I. A. Cohen, Introduction to Computer Theory, Prentice-Hall, 2nd Edition, 1997 |
References: |
Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2012
Daniel I. A. Cohen, Introduction to Computer Theory, Prentice-Hall, 2nd Edition, 1997 |
|
Program Outcomes |
Level of Contribution |
1) |
Knowledge of mathematics, science, basic engineering, computer computing, and engineering discipline-specific topics; ability to use this knowledge in solving complex engineering problems |
5 |
2) |
Sufficient knowledge of issues related to software engineering; theoretical and To be able to use applied knowledge in solving algorithmic and software problems Skill. |
4 |
3) |
Ability to define, formulate and analyze complex engineering problems using basic science, mathematics and engineering knowledge and taking into account the UN Sustainable Development Goals relevant to the problem under consideration. |
|
4) |
Ability to design creative solutions to complex engineering problems; The ability to design complex systems, processes, devices or products to meet current and future requirements, taking into account realistic constraints and conditions. |
5 |
5) |
Ability to choose and use appropriate techniques, resources, modern engineering computational tools for the analysis, solution, prediction and modelling of complex engineering problems. |
|
6) |
Ability to use research methods to examine complex engineering problems, including researching literature, designing experiments, conducting experiments, collecting data, analyzing and interpreting results. |
|
7) |
Information about the effects of engineering practices on society, health and safety, economy, sustainability and the environment within the scope of the UN Sustainable Development Goals; Awareness of the legal consequences of engineering solutions |
|
8) |
Acting in accordance with engineering professional principles and knowledge about ethical responsibility; Awareness of acting impartially, without discrimination on any issue, and being inclusive of diversity. |
|
9) |
Ability to work effectively as a team member or leader in intradisciplinary and multidisciplinary teams (face-to-face, remote or hybrid). |
|
10) |
Individual working ability. |
5 |
11) |
Ability to communicate effectively verbally and in writing on technical issues, taking into account the various differences of the target audience (such as education, language, profession). |
|
12) |
Knowledge of business practices such as project management and economic feasibility analysis |
|
13) |
Awareness about entrepreneurship and innovation. |
|
14) |
A lifelong learning skill that includes being able to learn independently and continuously, adapting to new and developing technologies, and thinking inquisitively about technological changes. |
|