Business Administration
Bachelor	Length of the Programme: 4	Number of Credits: 240	TR-NQF-HE: Level 6	QF-EHEA: First Cycle	EQF: Level 6

ECTS Course Information Package

School/Faculty/Institute

Faculty of Engineering

Course Code

COMP 454

Course Title in English

Theory of Computation

Course Title in Turkish

Hesaplama Kuramı

Language of Instruction

Type of Course

Flipped Classroom

Level of Course

Introductory

Semester

Spring

Contact Hours per Week

Lecture: 3

Recitation: 0

Lab: 0

Other: 0

Estimated Student Workload

118 hours per semester

Number of Credits

6 ECTS

Grading Mode

Standard Letter Grade

Pre-requisites

MATH 321 - Automata Theory and Formal Language

Co-requisites

None

Expected Prior Knowledge

Formal Languages and Automata

Registration Restrictions

None

Overall Educational Objective

To be able to obtain a scientific prespective on the natüre of computational problems.

Course Description

Overview of types of formal languages and automata and recursively enumerable languages, computation models and computability, decidability and reducibility, introduction of advanced topics in theory of computation, space and time complexity, intractability, introduction of advanced topics in theory of complexity.

Course Learning Outcomes and Competences

Upon successful completion of the course, the learner is expected to be able to:
1) To be able to apply computability and complexity analysis on a computation problem.
2) To understand and analyze decidability characteristics of a computation problem.
3) To understand complexity classes and to be able to apply reduction on problems.
4) To grasp the basic idea of intractability of a computation problem.

Program Learning Outcomes/Course Learning Outcomes	1	2	3	4
1) Has a broad foundation and intellectual awareness with exposure to mathematics, history, economics, and social sciences
2) Demonstrates knowledge and skills in different functional areas of business (accounting, finance, operations, marketing, strategy, and organization) and an understanding of their interactions within various industry sectors
3) Applies theoretical knowledge as well as creative, analytical, and critical thinking to manage complex technical or professional activities or projects
4) Exhibits an understanding of global, environmental, economic, legal, and regulatory contexts for business sustainability
5) Demonstrates individual and professional ethical behavior and social responsibility
6) Demonstrates responsiveness to ethnic, cultural, and gender diversity values and issues
7) Uses written and spoken English effectively (at least CEFR B2 level) to communicate information, ideas, problems, and solutions
8) Demonstrates skills in data and information acquisition, analysis, interpretation, and reporting
9) Displays computer proficiency to support problem solving and decision-making
10) Demonstrates teamwork, leadership, and entrepreneurial skills
11) Displays learning skills necessary for further study with a high degree of autonomy

Relation to Program Outcomes and Competences

N None	S Supportive	H Highly Related

	Program Outcomes and Competences	Level	Assessed by
1)	Has a broad foundation and intellectual awareness with exposure to mathematics, history, economics, and social sciences	N
2)	Demonstrates knowledge and skills in different functional areas of business (accounting, finance, operations, marketing, strategy, and organization) and an understanding of their interactions within various industry sectors	N
3)	Applies theoretical knowledge as well as creative, analytical, and critical thinking to manage complex technical or professional activities or projects	N
4)	Exhibits an understanding of global, environmental, economic, legal, and regulatory contexts for business sustainability	N
5)	Demonstrates individual and professional ethical behavior and social responsibility	N
6)	Demonstrates responsiveness to ethnic, cultural, and gender diversity values and issues	N
7)	Uses written and spoken English effectively (at least CEFR B2 level) to communicate information, ideas, problems, and solutions	S	Presentation
8)	Demonstrates skills in data and information acquisition, analysis, interpretation, and reporting	S	Participation
9)	Displays computer proficiency to support problem solving and decision-making	N
10)	Demonstrates teamwork, leadership, and entrepreneurial skills	S	Participation
11)	Displays learning skills necessary for further study with a high degree of autonomy	S	Participation

Prepared by and Date	ŞENİZ DEMİR , November 2023
Course Coordinator	ŞENİZ DEMİR
Semester	Spring
Name of Instructor	Assoc. Prof. Dr. TOLGA OVATMAN

Course Contents

Week	Subject
1)	Formal Languages and Automata Theory
2)	Recursively Enumerable Languages
3)	Computation Models
4)	Computability
5)	Decidability – Decidable Languages
6)	Decidability – Undecidable Languages
7)	Reducibility
8)	Advanced Topics in Computability Theory
9)	Practical Applications of Complexity Theory
10)	Time Complexity – Complexity Measurement and P Class Problems
11)	Time Complexity – NP Class Problems and NP-Completeness
12)	Space Complexity
13)	Intractability
14)	Advanced Topics in Complexity Theory
15)	Final Exam/Project/Presentation Period
16)	Final Exam/Project/Presentation Period

Required/Recommended Readings

Sipser M., Introduction to the Theory Of Computation 3rd Edition, Cengage Learning, 2013 Martin J.C., Introduction To Languages And The Theory Of Computation 4th Edition, Mcgraw-Hill, 2011 Attalah M.J., Blanton M., Algorithms And Theory Of Computation Handbook Vol.2:Special Topics And Techniques 2nd Edition, CRC Press, 2010

Teaching Methods

Lecture only

Homework and Projects

In-class exercises

Laboratory Work

None

Computer Use

None

Other Activities

None

Assessment Methods

Assessment Tools	Count	Weight
Quiz(zes)	5	% 60
Final Examination	1	% 40
TOTAL		% 100

Course Administration

ovatman@itu.edu.tr

Instructor’s office and phone number, office hours, email address: To be announced Assoc. Prof. Tolga Ovatman - ITU -Office:İTÜ Faculty of Computer and Informatics -Email address: ovatman@itu.edu.tr Rules for attendance: Minimum of 70% attendance required. Missing a quiz: Provided that proper documents of excuse are presented, each missed quiz by the student will be given a grade which is equal to the average of all of the other quizzes. No make-up will be given. Missing a final: Faculty regulations. A reminder of proper classroom behavior, code of student conduct: YÖK Regulations Statement on plagiarism: YÖK Regulations

ECTS Student Workload Estimation

Activity	No/Weeks	Hours			Calculation
	No/Weeks per Semester	Preparing for the Activity	Spent in the Activity Itself	Completing the Activity Requirements
Course Hours	14	1.5	3	1.5	84
Quiz(zes)	5	4	1		25
Final Examination	1	13	3		16
Total Workload					125
Total Workload/25					5.0
ECTS					6