ALGORITHM ANALYSIS

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.

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)..

1. 1

   1) At the end of this course the students will be able to describe the fundamentals of algorithm analysis.

   Taught by: Problem Solving Method, Self Study Method, Question - Answer Technique, Lecture Method · Assessed by: Traditional Written Exam, Homework

2. 2

   2) At the end of this course the students will be able to construct complex algorithms using the data structures that they have learned.

   Taught by: Problem Solving Method, Self Study Method, Question - Answer Technique, Lecture Method · Assessed by: Traditional Written Exam, Homework

3. 3

   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.

   Taught by: Discussion Method, Problem Solving Method, Self Study Method, Experimental Technique, Lecture Method · Assessed by: Traditional Written Exam, Homework, Project Task

4. 4

   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.

   Taught by: Discussion Method, Problem Solving Method, Self Study Method, Experimental Technique, Lecture Method · Assessed by: Traditional Written Exam, Homework, Project Task

5. 5

   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.

   Taught by: Problem Solving Method, Self Study Method, Question - Answer Technique, Brainstorming Technique, Lecture Method · Assessed by: Traditional Written Exam, Homework

WEEKLY PLAN

1. WEEK 1

   Week 1: Introduction: analysing algorithms, designing algorithms.

   Preparation: Lecture Slides and textbook chapters 1 & 2

2. WEEK 2

   Week 2: Asymptotic Notation.

   Preparation: Lecture Slides and textbook chapter 3

3. WEEK 3

   Week 3: Divide and Conquer Design Paradigm.

   Preparation: Lecture Slides and textbook chapter 4

4. WEEK 4

   Week 4: Solving Recurrences.

   Preparation: Lecture Slides and textbook chapter 4

5. WEEK 5

   Week 5: Analysis of Quicksort, Randomized Quicksort.

   Preparation: Lecture Slides and textbook chapter 5

6. WEEK 6

   Week 6: Heapsort.

   Preparation: Lecture Slides and textbook chapter 6

7. WEEK 7

   Week 7: Quicksort.

   Preparation: Lecture Slides and textbook chapter 7

8. WEEK 8

   Week 8: Sorting in Linear Time.

   Preparation: Lecture Slides and textbook chapter 8

9. WEEK 9

   Midterm

   Preparation: Lecture Slides and textbook chapters from 1 to 9, inclusive.

10. WEEK 10

    Week 10: Medians and Order Statistics.

    Preparation: Lecture Slides and textbook chapter 9

11. WEEK 11

    Week 11: Dynamic Programming.

    Preparation: Lecture Slides and textbook chapter 15

12. WEEK 12

    Week 12: Greedy Algorithms.

    Preparation: Lecture Slides and textbook chapter 16

13. WEEK 13

    Week 13: Amortized Analysis, Dynamic Tables.

    Preparation: Lecture Slides and textbook chapter 17

14. WEEK 14

    Week 13: Graphs, Breadth-first Search (BFS).

    Preparation: Lecture Slides and textbook chapter 22

ASSESSMENT

• Rate of Midterm Exam to Success30%
• Rate of Final Exam to Success70%

WORKLOAD

READING

• 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.

TEACHING STAFF

• Prof.Dr. Reda ALHAJJCOORDINATOR
• Prof.Dr. Reda ALHAJJ