## Course Detail

## Course Description

Course | Code | Semester | T+P (Hour) | Credit | ECTS |
---|---|---|---|---|---|

ALGORITHM ANALYSIS | COE3233890 | Spring Semester | 3+0 | 3 | 6 |

Course Program | Pazartesi 15:30-16:15 Pazartesi 16:30-17:15 Pazartesi 17:30-18:15 |

Prerequisites Courses | |

Recommended Elective Courses |

Language of Course | English |

Course Level | First Cycle (Bachelor's Degree) |

Course Type | Required |

Course Coordinator | Prof.Dr. Reda ALHAJJ |

Name of Lecturer(s) | Prof.Dr. Reda ALHAJJ |

Assistant(s) | |

Aim | Introduce fundamental techniques for designing algorithms and analyzing the time and space requirements of these algorithms in a formal way. Mathematical background for algorithm analysis, sorting, searching, basic algorithms design and graph algorithms will be covered. |

Course Content | This course contains; Week 1: Introduction: analysing algorithms, designing algorithms.,Week 2: Asymptotic Notation.,Week 3: Divide and Conquer Design Paradigm.,Week 4: Solving Recurrences.,Week 5: Analysis of Quicksort, Randomized Quicksort.,Week 6: Heapsort.,Week 7: Quicksort.,Week 8: Sorting in Linear Time.,Midterm,Week 10: Medians and Order Statistics.,Week 11: Dynamic Programming.,Week 12: Greedy Algorithms.,Week 13: Amortized Analysis, Dynamic Tables.,Week 13: Graphs, Breadth-first Search (BFS).. |

Dersin Öğrenme Kazanımları | Teaching Methods | Assessment Methods |

1) At the end of this course the students will be able to describe the fundamentals of algorithm analysis. | 12, 14, 16, 9 | A, E |

2) At the end of this course the students will be able to construct complex algorithms using the data structures that they have learned. | 12, 14, 16, 9 | A, E |

3) At the end of this course the students will be able to develop complex algorithms and advanced data structures that are using trees and will be able to apply them to real world problems. | 10, 12, 14, 17, 9 | A, E, F |

4) At the end of this course the students will be able to develop complex algorithms and advanced data structures that are using graphs and will be able to apply them to real world problems. | 10, 12, 14, 17, 9 | A, E, F |

5) At the end of this course the students will be able to systematically look at a given computational problem and design a novel algorithm using techniques like dynamic programming, divide and conquer and greedy algorithms. | 12, 14, 16, 19, 9 | A, E |

Teaching Methods: | 10: Discussion Method, 12: Problem Solving Method, 14: Self Study Method, 16: Question - Answer Technique, 17: Experimental Technique, 19: Brainstorming Technique, 9: Lecture Method |

Assessment Methods: | A: Traditional Written Exam, E: Homework, F: Project Task |

## Course Outline

Order | Subjects | Preliminary Work |
---|---|---|

1 | Week 1: Introduction: analysing algorithms, designing algorithms. | Lecture Slides and textbook chapters 1 & 2 |

2 | Week 2: Asymptotic Notation. | Lecture Slides and textbook chapter 3 |

3 | Week 3: Divide and Conquer Design Paradigm. | Lecture Slides and textbook chapter 4 |

4 | Week 4: Solving Recurrences. | Lecture Slides and textbook chapter 4 |

5 | Week 5: Analysis of Quicksort, Randomized Quicksort. | Lecture Slides and textbook chapter 5 |

6 | Week 6: Heapsort. | Lecture Slides and textbook chapter 6 |

7 | Week 7: Quicksort. | Lecture Slides and textbook chapter 7 |

8 | Week 8: Sorting in Linear Time. | Lecture Slides and textbook chapter 8 |

9 | Midterm | Lecture Slides and textbook chapters from 1 to 9, inclusive. |

10 | Week 10: Medians and Order Statistics. | Lecture Slides and textbook chapter 9 |

11 | Week 11: Dynamic Programming. | Lecture Slides and textbook chapter 15 |

12 | Week 12: Greedy Algorithms. | Lecture Slides and textbook chapter 16 |

13 | Week 13: Amortized Analysis, Dynamic Tables. | Lecture Slides and textbook chapter 17 |

14 | Week 13: Graphs, Breadth-first Search (BFS). | Lecture Slides and textbook chapter 22 |

Resources |

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Mit Press and McGraw-Hill, 2009. |

The notes and the presentations will be delivered during the lectures. |

## Course Contribution to Program Qualifications

Course Contribution to Program Qualifications | |||||||

No | Program Qualification | Contribution Level | |||||

1 | 2 | 3 | 4 | 5 | |||

1 | 1. An ability to apply knowledge of mathematics, science, and engineering | X | |||||

2 | 2. An ability to identify, formulate, and solve engineering problems | X | |||||

3 | 3. An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability | X | |||||

4 | 4. An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice | X | |||||

5 | 5. An ability to design and conduct experiments, as well as to analyze and interpret data | ||||||

6 | 6. An ability to function on multidisciplinary teams | X | |||||

7 | 7. An ability to communicate effectively | X | |||||

8 | 8. A recognition of the need for, and an ability to engage in life-long learning | X | |||||

9 | 9. An understanding of professional and ethical responsibility | X | |||||

10 | 10. A knowledge of contemporary issues | ||||||

11 | 11. The broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context |

## Assessment Methods

Contribution Level | Absolute Evaluation | |

Rate of Midterm Exam to Success | 30 | |

Rate of Final Exam to Success | 70 | |

Total | 100 |

ECTS / Workload Table | ||||||

Activities | Number of | Duration(Hour) | Total Workload(Hour) | |||

Course Hours | 14 | 3 | 42 | |||

Guided Problem Solving | 14 | 4 | 56 | |||

Resolution of Homework Problems and Submission as a Report | 6 | 5 | 30 | |||

Term Project | 0 | 0 | 0 | |||

Presentation of Project / Seminar | 0 | 0 | 0 | |||

Quiz | 0 | 0 | 0 | |||

Midterm Exam | 1 | 22 | 22 | |||

General Exam | 1 | 22 | 22 | |||

Performance Task, Maintenance Plan | 0 | 0 | 0 | |||

Total Workload(Hour) | 172 | |||||

Dersin AKTS Kredisi = Toplam İş Yükü (Saat)/30*=(172/30) | 6 | |||||

ECTS of the course: 30 hours of work is counted as 1 ECTS credit. |

## Detail Informations of the Course

### Course Description

Course | Code | Semester | T+P (Hour) | Credit | ECTS |
---|---|---|---|---|---|

ALGORITHM ANALYSIS | COE3233890 | Spring Semester | 3+0 | 3 | 6 |

Course Program | Pazartesi 15:30-16:15 Pazartesi 16:30-17:15 Pazartesi 17:30-18:15 |

Prerequisites Courses | |

Recommended Elective Courses |

Language of Course | English |

Course Level | First Cycle (Bachelor's Degree) |

Course Type | Required |

Course Coordinator | Prof.Dr. Reda ALHAJJ |

Name of Lecturer(s) | Prof.Dr. Reda ALHAJJ |

Assistant(s) | |

Aim | Introduce fundamental techniques for designing algorithms and analyzing the time and space requirements of these algorithms in a formal way. Mathematical background for algorithm analysis, sorting, searching, basic algorithms design and graph algorithms will be covered. |

Course Content | This course contains; Week 1: Introduction: analysing algorithms, designing algorithms.,Week 2: Asymptotic Notation.,Week 3: Divide and Conquer Design Paradigm.,Week 4: Solving Recurrences.,Week 5: Analysis of Quicksort, Randomized Quicksort.,Week 6: Heapsort.,Week 7: Quicksort.,Week 8: Sorting in Linear Time.,Midterm,Week 10: Medians and Order Statistics.,Week 11: Dynamic Programming.,Week 12: Greedy Algorithms.,Week 13: Amortized Analysis, Dynamic Tables.,Week 13: Graphs, Breadth-first Search (BFS).. |

Dersin Öğrenme Kazanımları | Teaching Methods | Assessment Methods |

1) At the end of this course the students will be able to describe the fundamentals of algorithm analysis. | 12, 14, 16, 9 | A, E |

2) At the end of this course the students will be able to construct complex algorithms using the data structures that they have learned. | 12, 14, 16, 9 | A, E |

3) At the end of this course the students will be able to develop complex algorithms and advanced data structures that are using trees and will be able to apply them to real world problems. | 10, 12, 14, 17, 9 | A, E, F |

4) At the end of this course the students will be able to develop complex algorithms and advanced data structures that are using graphs and will be able to apply them to real world problems. | 10, 12, 14, 17, 9 | A, E, F |

5) At the end of this course the students will be able to systematically look at a given computational problem and design a novel algorithm using techniques like dynamic programming, divide and conquer and greedy algorithms. | 12, 14, 16, 19, 9 | A, E |

Teaching Methods: | 10: Discussion Method, 12: Problem Solving Method, 14: Self Study Method, 16: Question - Answer Technique, 17: Experimental Technique, 19: Brainstorming Technique, 9: Lecture Method |

Assessment Methods: | A: Traditional Written Exam, E: Homework, F: Project Task |

### Course Outline

Order | Subjects | Preliminary Work |
---|---|---|

1 | Week 1: Introduction: analysing algorithms, designing algorithms. | Lecture Slides and textbook chapters 1 & 2 |

2 | Week 2: Asymptotic Notation. | Lecture Slides and textbook chapter 3 |

3 | Week 3: Divide and Conquer Design Paradigm. | Lecture Slides and textbook chapter 4 |

4 | Week 4: Solving Recurrences. | Lecture Slides and textbook chapter 4 |

5 | Week 5: Analysis of Quicksort, Randomized Quicksort. | Lecture Slides and textbook chapter 5 |

6 | Week 6: Heapsort. | Lecture Slides and textbook chapter 6 |

7 | Week 7: Quicksort. | Lecture Slides and textbook chapter 7 |

8 | Week 8: Sorting in Linear Time. | Lecture Slides and textbook chapter 8 |

9 | Midterm | Lecture Slides and textbook chapters from 1 to 9, inclusive. |

10 | Week 10: Medians and Order Statistics. | Lecture Slides and textbook chapter 9 |

11 | Week 11: Dynamic Programming. | Lecture Slides and textbook chapter 15 |

12 | Week 12: Greedy Algorithms. | Lecture Slides and textbook chapter 16 |

13 | Week 13: Amortized Analysis, Dynamic Tables. | Lecture Slides and textbook chapter 17 |

14 | Week 13: Graphs, Breadth-first Search (BFS). | Lecture Slides and textbook chapter 22 |

Resources |

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Mit Press and McGraw-Hill, 2009. |

The notes and the presentations will be delivered during the lectures. |

### Course Contribution to Program Qualifications

Course Contribution to Program Qualifications | |||||||

No | Program Qualification | Contribution Level | |||||

1 | 2 | 3 | 4 | 5 | |||

1 | 1. An ability to apply knowledge of mathematics, science, and engineering | X | |||||

2 | 2. An ability to identify, formulate, and solve engineering problems | X | |||||

3 | 3. An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability | X | |||||

4 | 4. An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice | X | |||||

5 | 5. An ability to design and conduct experiments, as well as to analyze and interpret data | ||||||

6 | 6. An ability to function on multidisciplinary teams | X | |||||

7 | 7. An ability to communicate effectively | X | |||||

8 | 8. A recognition of the need for, and an ability to engage in life-long learning | X | |||||

9 | 9. An understanding of professional and ethical responsibility | X | |||||

10 | 10. A knowledge of contemporary issues | ||||||

11 | 11. The broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context |

### Assessment Methods

Contribution Level | Absolute Evaluation | |

Rate of Midterm Exam to Success | 30 | |

Rate of Final Exam to Success | 70 | |

Total | 100 |