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 3pm-3:50pm, THU 12-1:50pm
Prerequisite CS105, MATH204 It is a prerequisite to
Lecturer Office Hours / Room / Phone

Currently not available

E-mail
Assistant Emina Dzaferovic Assistant E-mail emina.dzaferovic95@gmail.com
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 that we will also be using towards the end of the semester is Introduction to the Theory of Computation, by Michael A. Sipser, 2nd edition.
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. Active tutorial sessions for engaged learning and continuous feedback on progress.
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) (HW1 OUT) Chapters 5,6
Week 5 Regular and nonregular languages Chapter 8
Week 6 Context-free grammars (HW1 DUE) Chapter 11
Week 7 Pushdown automata/ Context-free and non-context-free languages (HW2 OUT) Chapter 12, 13
Week 8 Test 1
Week 9 Turing machines, Church-Turing thesis (HW2 DUE) Chapter 17, 18
Week 10 Halting Problem, Decidability (HW3 OUT) Chapter 19, 20
Week 11 Analysis of complexity/NP-completeness Chapter 27 (Also Sipser's book)
Week 12 NP-complete Reductions (HW3 DUE) Chapter 28 (Also Sipser's book)
Week 13 NP-complete Reductions (HW4 OUT) Chapter 28 (Also Sipser's book)
Week 14 Test 2
Week 15 Final Review (HW4 DUE)
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 40 1,2,3,4,5
Assignments 4 20 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 15 2 30
Labs 2 15 30 Labs 2 15 30
Assignments 8 4 32
        Total Workload Hours = 150
*T= Teaching, P= Practice ECTS Credit = 6
Course Academic Quality Assurance: Semester Student Survey Last Update Date: 04/03/2020
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.