EPOKA UNIVERSITY
FACULTY OF ARCHITECTURE AND ENGINEERING
DEPARTMENT OF COMPUTER ENGINEERING
COURSE SYLLABUS
2025-2026 ACADEMIC YEAR
COURSE INFORMATIONCourse Title: THEORY OF COMPUTATION |
| Code | Course Type | Regular Semester | Theory | Practice | Lab | Credits | ECTS |
|---|---|---|---|---|---|---|---|
| CEN 350 | C | 6 | 2 | 2 | 0 | 3 | 6 |
| Academic staff member responsible for the design of the course syllabus (name, surname, academic title/scientific degree, email address and signature) | Dr. Edlir Spaho espaho@epoka.edu.al |
| Main Course Lecturer (name, surname, academic title/scientific degree, email address and signature) and Office Hours: | Dr. Edlir Spaho espaho@epoka.edu.al , Thursday, 10:00 AM - 11:00 AM |
| Second Course Lecturer(s) (name, surname, academic title/scientific degree, email address and signature) and Office Hours: | NA |
| Language: | English |
| Compulsory/Elective: | Elective |
| Study program: (the study for which this course is offered) | Bachelor in Software Engineering (3 years) |
| Classroom and Meeting Time: | E006, Thursday, 10:00 AM - 11:00 AM |
| Teaching Assistant(s) and Office Hours: | NA |
| Code of Ethics: |
Code of Ethics of EPOKA University Regulation of EPOKA University "On Student Discipline" |
| Attendance Requirement: | 75% |
| Course Description: | This course introduces the theory of computation through a set of abstract machines that serve as models for computation - finite automata, pushdown automata, and Turing machines - and examines the relationship between these automata and formal languages. Additional topics beyond the automata classes themselves include deterministic and non-deterministic machines, regular expressions, context free grammars, undecidability, and the P = NP question. |
| Course Objectives: | By the end of this course, students will be able to: 1. Develop a Formal Understanding of Computation 2. Analyze and Design Finite-State Computational Models 3. Model Hierarchical and Recursive Structures 4. Understand the Limits of Algorithmic Computation 5. Classify Problems by Computational Complexity 6. Strengthen Formal Reasoning and Proof Skills |
|
BASIC CONCEPTS OF THE COURSE
|
| 1 | Finite Automaton (FA) |
| 2 | Deterministic Finite Automaton (DFA) |
| 3 | Nondeterministic Finite Automaton (NFA) |
| 4 | Regular Language |
| 5 | Regular Expression (RE) |
| 6 | Context-Free Grammar (CFG) |
| 7 | Pushdown Automaton (PDA) |
| 8 | Turing Machine (TM) |
| 9 | P vs NP Complexity |
| 10 | Decidable Language |
|
COURSE OUTLINE
|
| Week | Topics |
| 1 | Introduction to Theory of Computation |
| 2 | Review of Mathematical Foundations |
| 3 | Deterministic Finite Automata (DFA) |
| 4 | Nondeterministic Finite Automata (NFA) |
| 5 | NFA to DFA Conversion |
| 6 | Regular Expressions |
| 7 | Properties of Regular Languages |
| 8 | Midterm exam |
| 9 | Context-Free Grammars (CFG) |
| 10 | Pushdown Automata (PDA) |
| 11 | Equivalence of CFG and PDA |
| 12 | Turing Machines |
| 13 | Decidability and Undecidability |
| 14 | Comprehensive Review |
| Prerequisite(s): | None |
| Textbook(s): | Introduction to Theory of Computation, Anil Maheshwari, Michiel Smid, 2024 |
| Additional Literature: | Introduction to Automata Theory Languages and Computations, John-E., Hopcroft Rajeev Motwani, Jeffrey D. Ullman, Prentice-Hall-2006 |
| Laboratory Work: | Yes |
| Computer Usage: | Yes |
| Others: | No |
|
COURSE LEARNING OUTCOMES
|
| 1 | Define and apply the fundamental concepts of formal languages, including alphabets, strings, language operations, and mathematical notation used in automata theory. |
| 2 | Design, analyze, and prove properties of deterministic and nondeterministic finite automata, and demonstrate equivalence between automata and regular expressions. |
| 3 | Construct and analyze context-free grammars and pushdown automata, including transformations and applications of the pumping lemma for context-free languages. |
| 4 | Model computation using Turing machines, distinguish between decidable and recognizable languages, and apply reduction techniques to prove undecidability results. |
| 5 | Classify problems into complexity classes (P, NP, NP-complete), apply polynomial-time reductions, and explain the theoretical and practical implications of the P vs NP question. |
|
COURSE CONTRIBUTION TO... PROGRAM COMPETENCIES
(Blank : no contribution, 1: least contribution ... 5: highest contribution) |
| No | Program Competencies | Cont. |
| Bachelor in Software Engineering (3 years) Program | ||
| 1 | Engineering graduates with sufficient theoretical and practical background for a successful profession and with application skills of fundamental scientific knowledge in the engineering practice. | 5 |
| 2 | Engineering graduates with skills and professional background in describing, formulating, modeling and analyzing the engineering problem, with a consideration for appropriate analytical solutions in all necessary situations | 5 |
| 3 | Engineering graduates with the necessary technical, academic and practical knowledge and application confidence in the design and assessment of machines or mechanical systems or industrial processes with considerations of productivity, feasibility and environmental and social aspects. | 5 |
| 4 | Engineering graduates with the practice of selecting and using appropriate technical and engineering tools in engineering problems, and ability of effective usage of information science technologies. | 5 |
| 5 | Ability of designing and conducting experiments, conduction data acquisition and analysis and making conclusions. | 5 |
| 6 | Ability of identifying the potential resources for information or knowledge regarding a given engineering issue. | 5 |
| 7 | The abilities and performance to participate multi-disciplinary groups together with the effective oral and official communication skills and personal confidence. | 5 |
| 8 | Ability for effective oral and official communication skills in foreign language. | 5 |
| 9 | Engineering graduates with motivation to life-long learning and having known significance of continuous education beyond undergraduate studies for science and technology. | 5 |
| 10 | Engineering graduates with well-structured responsibilities in profession and ethics. | 5 |
| 11 | Engineering graduates who are aware of the importance of safety and healthiness in the project management, workshop environment as well as related legal issues. | 5 |
| 12 | Consciousness for the results and effects of engineering solutions on the society and universe, awareness for the developmental considerations with contemporary problems of humanity. | 5 |
|
COURSE EVALUATION METHOD
|
| Method | Quantity | Percentage |
| Homework |
1
|
20
|
| Midterm Exam(s) |
1
|
30
|
| Final Exam |
1
|
40
|
| Other |
1
|
10
|
| Total Percent: | 100% |
|
ECTS (ALLOCATED BASED ON STUDENT WORKLOAD)
|
| Activities | Quantity | Duration(Hours) | Total Workload(Hours) |
| Course Duration (Including the exam week: 16x Total course hours) | 16 | 4 | 64 |
| Hours for off-the-classroom study (Pre-study, practice) | 16 | 4 | 64 |
| Mid-terms | 1 | 10 | 10 |
| Assignments | 0 | ||
| Final examination | 1 | 12 | 12 |
| Other | 0 | ||
|
Total Work Load:
|
150 | ||
|
Total Work Load/25(h):
|
6 | ||
|
ECTS Credit of the Course:
|
6 | ||
|
CONCLUDING REMARKS BY THE COURSE LECTURER
|
|
*** |