School/Faculty/Institute Faculty of Engineering
Course Code COMP 303
Course Title in English Analysis of Algorithms
Course Title in Turkish Algoritma Analizi
Language of Instruction EN
Type of Course Flipped Classroom
Level of Course Introductory
Semester Fall
Contact Hours per Week
Lecture: 3 Recitation: none Lab: none Other: none
Estimated Student Workload 158 hours per semester
Number of Credits 6 ECTS
Grading Mode Standard Letter Grade
Pre-requisites COMP 201 - Data Structures and Algorithms
Expected Prior Knowledge Object Oriented Programming, Data Structures
Co-requisites None
Registration Restrictions Only Undergraduate Students
Overall Educational Objective To evaluate the efficiency of algorithms used to solve a computational problem.
Course Description This course provides a comprehensive introduction to some fundamental aspects of Analysis of Algorithms. The following topics are covered: Introduction, mathematical foundations; asymptotic analysis; recurrences; sorting algorithms, merge sort, heap sort; randomized algorithms, Hashing, searching, Binary search Trees, 2-3 Tress, Red and Black trees , Binomial Heaps; Fibonacci Heaps Given a computational problem, we want to (a) find an algorithm to solve the problem, (b) prove that the algorithm solves the problem correctly, (c) prove that we cannot solve the problem any faster, and (d) implement the algorithm. The course focuses on these topics by studying useful algorithmic design techniques and methods for analyzing algorithms.
Course Description in Turkish Bu derste; Algoritma Analizinin temel kavramları şu konu başlıklar altında kapsamlı bir şekilde incelenmektedir: Giriş, Matematiksel temeller, asimptotik analiz, yineleme, sıralama algoritmaları, birleştirme sıralama, yığın sıralama, rastsal algoritmalar, özütleme, arama, ikili arama ağaçları, 2-3 Ağaçları, Kırmızı-Siyah ağaçlar, İkiterimli yığınlar, Fibonacci yığınları

Course Learning Outcomes and Competences

Upon successful completion of the course, the learner is expected to be able to:
1) analyze the performance of algorithms by using asymptotic notation;
2) solve recurrences;
3) describe and compare sorting algorithms
4) identify complicated data structures such as Hashing, B-trees, Red-Black trees, heap structures;
5) analyze graphs ;
6) design and implement efficient algorithms to solve a computational problem;
7) analyze and interpret algorithms to solve a computational problem;
Program Learning Outcomes/Course Learning Outcomes 1 2 3 4 5 6 7
1) Thorough knowledge of the major concepts, theoretical perspectives, empirical findings, and historical trends in psychology.
2) Understanding of and ability to apply essential research methods in psychology, including research design, data analysis, and data interpretation.
3) Competence to use critical and creative thinking, skeptical inquiry and a scientific approach to solving problems related to behavior and mental processes.
4) Understanding and ability to apply psychological principles, skills and values in personal, social, and organizational contexts.
5) Ability to weigh evidence, to tolerate ambiguity, and to reflect other values that underpin psychology as a discipline.
6) Internalization and dissemination of professional ethical standards.
7) Demonstration of competence in information technologies, and the ability to use computer and other technologies for purposes related to the pursuit of knowledge in psychology and the broader social sciences.
8) Skills to communicate the knowledge of psychological science effectively, in a variety of formats, in both Turkish and in English (in English, at least CEFR B2 level).
9) Recognition, understanding, and respect for the complexity of sociocultural and international diversity.
10) Recognition for the need for, and the skills to pursue, lifelong learning, inquiry, and self-improvement.
11) Ability to formulate critical hypotheses based on psychological theory and literature, and design studies to test those hypotheses.
12) Ability to acquire knowledge independently, and to plan one’s own learning.
13) Demonstration of advanced competence in the clarity and composition of written work and presentations.

Relation to Program Outcomes and Competences

N None S Supportive H Highly Related
     
Program Outcomes and Competences Level Assessed by
1) Thorough knowledge of the major concepts, theoretical perspectives, empirical findings, and historical trends in psychology. N
2) Understanding of and ability to apply essential research methods in psychology, including research design, data analysis, and data interpretation. N
3) Competence to use critical and creative thinking, skeptical inquiry and a scientific approach to solving problems related to behavior and mental processes. H Exam,HW,Participation
4) Understanding and ability to apply psychological principles, skills and values in personal, social, and organizational contexts. N
5) Ability to weigh evidence, to tolerate ambiguity, and to reflect other values that underpin psychology as a discipline. N
6) Internalization and dissemination of professional ethical standards. N
7) Demonstration of competence in information technologies, and the ability to use computer and other technologies for purposes related to the pursuit of knowledge in psychology and the broader social sciences. N
8) Skills to communicate the knowledge of psychological science effectively, in a variety of formats, in both Turkish and in English (in English, at least CEFR B2 level). N
9) Recognition, understanding, and respect for the complexity of sociocultural and international diversity. S Participation
10) Recognition for the need for, and the skills to pursue, lifelong learning, inquiry, and self-improvement. S HW,Participation
11) Ability to formulate critical hypotheses based on psychological theory and literature, and design studies to test those hypotheses. N
12) Ability to acquire knowledge independently, and to plan one’s own learning. S Exam,HW
13) Demonstration of advanced competence in the clarity and composition of written work and presentations. H Exam,HW
Prepared by and Date MUHİTTİN GÖKMEN , December 2018
Course Coordinator YASSINE DRIAS
Semester Fall
Name of Instructor Prof. Dr. MUHİTTİN GÖKMEN

Course Contents

Week Subject
1) Introduction
2) Asymptotic Analysis
3) Recurrences
4) Probabilistic Analysis and Randomized Algorithms
5) Heap Sort and Merge sort
6) Quicksort, sorting in linear time
7) Medians and Order Statistics
8) Elementary Data Structures and overview
9) Hash tables
10) Hash functions
11) Binary search tree, 2-3 trees
12) 2-3-4 trees, Red-Black trees
13) B-trees
14) Graphs
15) Final Exam/Project/Presentation
16) Final Exam/Project/Presentation
Required/Recommended ReadingsIntroduction to Algorithms , Third Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein MIT Press, 2009, ISBN 978-0-262-03384-8
Teaching MethodsLecturing and exercises in the classroom with computers. In-class exercises and 3 Projects will be carried out by students
Homework and ProjectsIn-class exercises, Projects
Laboratory WorkProgramming exercises
Computer UseFor Programming
Other Activities
Assessment Methods
Assessment Tools Count Weight
Quiz(zes) 6 % 30
Project 1 % 20
Midterm(s) 2 % 50
TOTAL % 100
Course Administration gokmenm@mef.edu.tr
0 212 395 36 26
Instructor’s office and phone number, office hours, email address: To be announced -Office: 5th Floor, #18 -Phone number: 0 212 395 36 26 - Email address: gokmenm@mef.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 midterm: Provided that proper documents of excuse are presented, each missed midterm by the student will be given the grade of the final exam. 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 3 1 70
Project 1 30 2 2 34
Quiz(zes) 6 4 1 30
Midterm(s) 2 10 2 24
Total Workload 158
Total Workload/25 6.3
ECTS 6