| 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) An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics |
|
|
|
|
|
|
|
| 2) An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors |
|
|
|
|
|
|
|
| 3) An ability to communicate effectively with a range of audiences |
|
|
|
|
|
|
|
| 4) An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts |
|
|
|
|
|
|
|
| 5) An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives |
|
|
|
|
|
|
|
| 6) An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions |
|
|
|
|
|
|
|
| 7) An ability to acquire and apply new knowledge as needed, using appropriate learning strategies. |
|
|
|
|
|
|
|
Relation to Program Outcomes and Competences
| N None |
S Supportive |
H Highly Related |
| |
|
|
| |
Program Outcomes and Competences |
Level |
Assessed by |
| 1) |
An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics |
H |
Exam,Project
|
| 2) |
An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors |
S |
Project
|
| 3) |
An ability to communicate effectively with a range of audiences |
N |
|
| 4) |
An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts |
N |
|
| 5) |
An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives |
N |
|
| 6) |
An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions |
S |
Project
|
| 7) |
An ability to acquire and apply new knowledge as needed, using appropriate learning strategies. |
N |
|
| Prepared by and Date |
MUHİTTİN GÖKMEN , December 2018 |
| Course Coordinator |
YASSINE DRIAS |
| Semester |
Fall |
| Name of Instructor |
Asst. Prof. Dr. YASSINE DRIAS |
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 Readings | Introduction 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 Methods | Lecturing and exercises in the classroom with computers. In-class exercises and 3 Projects will be carried out by students |
| Homework and Projects | In-class exercises, Projects |
| Laboratory Work | Programming exercises |
| Computer Use | For 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
|
Information Package / Course Catalogue