CS313 Theory of Computation

Print this page Please use the scale options of your printing settings for adjustments.

Course Code Course Title Weekly Hours* ECTS Weekly Class Schedule
T P
CS313 Theory of Computation 3 2 6 Tue 9-11:50am
Prerequisite CS105, MATH204 It is a prerequisite to

None

Lecturer Office Hours / Room / Phone

Currently not available

E-mail
Assistant Assistant E-mail
Course Objectives The aims of this course are to understand basic theory of computation concepts that lies at the backbone of all state-of-the-art applications and program design. Students should understand the capabilities and limits of computation, particular applications and capabilities of deterministic and non-deterministic finite automata, context-free grammars, and finally Turing machines, as well as NP-completeness and complexity classes.
Textbook Automata, Computability and Complexity: Theory and Applications, 1/E., Elaine A. Rich, 2008 is the compulsory textbook. A great resource is also Theory of Computation, by Michael A. Sipser, 2nd edition.
Additional Literature
Learning Outcomes After successful  completion of the course, the student will be able to:
  1. Design deterministic and non-deterministic finite state machines and understant their capabilities and limits
  2. Design deterministic and non-deterministic context-free grammars and pushdown automata
  3. Design and analyze Turing machines, their capabilities and limitations
  4. Demonstrate the understanding of complexity classes and current unsolved problems in theoretical computer science
  5. Apply the theoretical concepts to the practice of program design with regular expresisons, parsing, and complexity analysis
Teaching Methods Class discussions with examples.
Teaching Method Delivery Teaching Method Delivery Notes
WEEK TOPIC REFERENCE
Week 1 Course introduction
Week 2 Theory of computation: The big picture Chapters 1-4
Week 3 Finite state machines (DFA) Chapter 5
Week 4 Non-deterministic finite state machines (NFA) Chapters 5,6
Week 5 Regular and nonregular languages Chapter 8
Week 6 Context-free grammars Chapter 11
Week 7 Pushdown automata/ Context-free and non-context-free languages Chapter 12, 13
Week 8 Review and Test 1
Week 9 Turing machines, Church-Turing thesis Chapter 17, 18
Week 10 Halting Problem, Decidability Chapter 19, 20
Week 11 Analysis of complexity/NP-completeness Chapter 27 (Also Sipser's book)
Week 12 NP-complete Reductions Chapter 28 (Also Sipser's book)
Week 13 NP-complete Reductions Chapter 28 (Also Sipser's book)
Week 14 Review and Test 2
Week 15 Final Review
Assessment Methods and Criteria Evaluation Tool Quantity Weight Alignment with LOs
Final Exam 1 40 1,2,3,4,5
Semester Evaluation Compenents
Tests 2 50 1,2,3,4,5
In-class participation 1 10 1,2,3,4,5
***     ECTS Credit Calculation     ***
 Activity Hours Weeks Student Workload Hours Activity Hours Weeks Student Workload Hours
Lecture Hours 3 15 45 Tests study 17 2 34
Final exam study 26 1 26 Home study 3 15 45
        Total Workload Hours = 150
*T= Teaching, P= Practice ECTS Credit = 6
Course Academic Quality Assurance: Semester Student Survey Last Update Date: 15/02/2021
QR Code for https://ecampus.ius.edu.ba/course/math204-discrete-mathematics

Print this page Please use the scale options of your printing settings for adjustments.