BÄ°L604 - COMPUTATIONAL THEORY
| Course Name | Code | Semester | Theory (hours/week) |
Application (hours/week) |
Credit | ECTS |
|---|---|---|---|---|---|---|
| COMPUTATIONAL THEORY | BÄ°L604 | Any Semester/Year | 3 | 0 | 3 | 8 |
| Prequisites | ||||||
| Course language | Turkish | |||||
| Course type | Elective | |||||
| Mode of Delivery | Face-to-Face | |||||
| Learning and teaching strategies | Lecture Discussion Preparing and/or Presenting Reports Project Design/Management | |||||
| Instructor (s) | Department Responsible (bbm-bologna@cs.hacettepe.edu.tr) | |||||
| Course objective | The objective of this course is to introduce students to this fundamental area of computer science which enables students to focus on the study of abstract models of computation. These abstract models allow the students to assess via formal reasoning what could be achieved through computing when they are using it to solve problems in science and engineering. The course exposes students to the computability theory, as well as to the complexity theory. The goal is to allow them to answer fundamental questions about problems, such as whether they can or not be computed, and if they can, how efficiently. | |||||
| Learning outcomes |
| |||||
| Course Content | This course gives an introduction to the mathematical foundations of computation. The course will look at Turing machines, universal computation, the Church-Turing thesis, the halting problem and general undecidability, Rice?s theorem, the recursion theorem, efficient computation models, time and space (memory) bounds, deterministic and nondeterministic computation and their relationships, the P versus NP problem and hard problems for NP and beyond. | |||||
| References | ? Computability and Complexity Theory, Steve Homer and Alan Selman. ? The Theory of Computation, Bernard M.Moret. Addison-Wesley. | |||||
Course outline weekly
| Weeks | Topics |
|---|---|
| Week 1 | Overview |
| Week 2 | Computable Functions |
| Week 3 | Primitive Recursive Functions |
| Week 4 | A Universal Program |
| Week 5 | Turing Machines |
| Week 6 | Time Complexity |
| Week 7 | Midterm Exam |
| Week 8 | Space Complexity |
| Week 9 | Complexity of Counting |
| Week 10 | Complexity of Counting: Toda's Theorem |
| Week 11 | PRAM and Circuit Models |
| Week 12 | Student presentations |
| Week 13 | Student presentations |
| Week 14 | Project presentations |
| Week 15 | Final Exam Preparation |
| Week 16 | Final Exam |
Assesment methods
| Course activities | Number | Percentage |
|---|---|---|
| Attendance | 14 | 10 |
| Laboratory | 0 | 0 |
| Application | 0 | 0 |
| Field activities | 0 | 0 |
| Specific practical training | 0 | 0 |
| Assignments | 5 | 20 |
| Presentation | 1 | 10 |
| Project | 0 | 0 |
| Seminar | 0 | 0 |
| Midterms | 1 | 10 |
| Final exam | 1 | 50 |
| Total | 100 | |
| Percentage of semester activities contributing grade succes | 21 | 50 |
| Percentage of final exam contributing grade succes | 1 | 50 |
| Total | 100 | |
WORKLOAD AND ECTS CALCULATION
| Activities | Number | Duration (hour) | Total Work Load |
|---|---|---|---|
| Course Duration (x14) | 14 | 3 | 42 |
| Laboratory | 0 | 0 | 0 |
| Application | 0 | 0 | 0 |
| Specific practical training | 0 | 0 | 0 |
| Field activities | 0 | 0 | 0 |
| Study Hours Out of Class (Preliminary work, reinforcement, ect) | 12 | 5 | 60 |
| Presentation / Seminar Preparation | 1 | 30 | 30 |
| Project | 0 | 0 | 0 |
| Homework assignment | 5 | 8 | 40 |
| Midterms (Study duration) | 1 | 28 | 28 |
| Final Exam (Study duration) | 1 | 40 | 40 |
| Total Workload | 34 | 114 | 240 |
Matrix Of The Course Learning Outcomes Versus Program Outcomes
| D.9. Key Learning Outcomes | Contrubition level* | ||||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | |
| 1. Graduates should have a mastery of computer science as described by the core of the Body of Knowledge. | X | ||||
| 2. Graduates need understanding of a number of recurring themes, such as abstraction, complexity, and evolutionary change, and a set of general principles, such as sharing a common resource, security, and concurrency. | X | ||||
| 3. Graduates of a computer science program need to understand how theory and practice influence each other. | X | ||||
| 4. Graduates need to think at multiple levels of detail and abstraction. | X | ||||
| 5. Students will be able to think critically, creatively and identify problems in their research. | X | ||||
| 6. Graduates should have been involved in at least one substantial project. | X | ||||
| 7. Graduates should realize that the computing field advances at a rapid pace. | X | ||||
| 8. Graduates should conduct research in an ethical and responsible manner. | X | ||||
| 9. Graduates should have good command of technical terms in both Turkish and English. | X | ||||
| 10. Graduates should understand the full range of opportunities available in computing. | X | ||||
| 11. Graduates should understand that computing interacts with many different domains. | X | ||||
| 12. Graduates should develop the knowledge acquired at master level and apply scientific methods in order to solve scientific problems. | X | ||||
*1 Lowest, 2 Low, 3 Average, 4 High, 5 Highest