Course Information
SemesterCourse Unit CodeCourse Unit TitleT+P+LCreditNumber of ECTS CreditsLast Updated Date
1COMP 5502ALGORITHM ANALYSIS AND COMPLEXITY THEORY3+0+03804.03.2020
Course Details
Language of Instruction English
Level of Course Unit Master's Degree
Department / Program Master of Science in COMPUTER ENGINEERING with thesis (In English)
Type of Program Formal Education
Type of Course Unit Elective
Course Delivery Method Face To Face
Objectives of the Course To build and strengthen the understanding of the fundamental concepts of algorithm analysis and complexity theory and to enable the students to effectively perform analysis of algorithms and reason about their complexity in an intensive and a rigorous manner.
Course Content Asymptotic Notations and Properties, Worst-case Analysis, Best-case Analysis, Average-case Analysis, Analysis of Iterative Algorithms, Analysis of Recursive Algorithms, Dynamic Programming, State-space Search, Decrease and Conquer, Divide and Conquer, Randomized Algorithms, Blind Search, Heuristic Algorithms, Branch and Bound, Problem Types, Complexity Classes, Decidability.
Course Methods and Techniques
Prerequisites and co-requisities None
Course Coordinator Assistant Professor MUTLU BEYAZIT
Name of Lecturers Assistant Professor Mutlu Beyazıt
Assistants None
Work Placement(s) No

Recommended or Required Reading
Resources Various resources are used (Example: Algorithms: Design Techniques and Analysis, M. H. Alsuwaiyel, 1999).


Planned Learning Activities and Teaching Methods
Activities are given in detail in the section of "Assessment Methods and Criteria" and "Workload Calculation"

Assessment Methods and Criteria
In-Term Studies Quantity Percentage
Homework 4 % 40
Project 1 % 30
Contribution of final Examination and Final Project 1 % 30
Total
6
% 100

 
ECTS Allocated Based on Student Workload
Activities Quantity Duration Total Work Load
Attendance 14 3 42
Homework 4 10 40
Project 1 50 50
Further self-study 14 3 42
Contribution of final Examination and Final Project 1 30 30
Total Work Load   Number of ECTS Credits 8 204

 
Course Learning Outcomes: Upon the successful completion of this course, students will be able to:
NoLearning Outcomes
1 To make different types of efficiency analysis of given algorithms.
2 To design efficient algorithmic solutions to given problems.
3 To have a good understading of complexity theory.

 
Weekly Detailed Course Contents
WeekTopicsStudy MaterialsMaterials
1 Introduction, Mathematical Review, Algorithm Analysis (Introduction) Reading Assignment Theory
2 Algorithm Analysis (Asymptotic Notations and Properties, Worst-case Analysis, Best-case Analysis, Average-case Analysis) Reading Assignment Theory
3 Algorithm Analysis (Iterative Algorithms) Reading Assignment Theory
4 Algorithm Analysis (Sort Functions) Reading Assignment Theory
5 Algorithm Analysis (Recursive Algorithms, Dynamic Programming) Reading Assignment Theory
6 Algorithm Analysis (Recurrence Relations, Decrease and Conquer) Reading Assignment Theory
7 Algorithm Analysis (Recurrence Relations, Master Method) Reading Assignment Theory
8 Algorithm Design (Introduction, State-Space Search, Decrease and Conquer, Divide and Conquer) Reading Assignment Theory
9 Algorithm Design (Randomized Algorithms, Blind Search) Reading Assignment Theory
10 Algorithm Design (Heuristic Algorithms, Branch and Bound) Reading Assignment Theory
11 Complexity Theory (Types of Problems) Reading Assignment Theory
12 Complexity Theory (Example Problems) Reading Assignment Theory
13 Complexity Theory (Reducibility, P, NP, NP-Complete, NP-Hard, Other Classes) Reading Assignment Theory
14 Complexity Theory (Turing Machines, Decidability) Reading Assignment Theory

 
Contribution of Learning Outcomes to Programme Outcomes
P1 P2 P3 P4 P5
All 4 4
C1
C2
C3

  bbb