ADVANCED 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; Introduction: analysing algorithms, designing algorithms.,Asymptotic Notation.,Divide and Conquer Design Paradigm.,Solving Recurrences. ,Analysis of Quicksort, Randomized Quicksort,Heapsort. ,Quicksort.,Sorting in Linear Time.,Midterm Study,Medians and Order Statistics. ,Dynamic Programming.,Greedy Algorithms.,Amortized Analysis, Dynamic Tables. ,Graphs, Breadth-first Search (BFS). .

1. 1

   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

   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

   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

   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

   Design a novel algorithm using techniques like dynamic programming, divide and conquer and greedy algorithms by systematically look at a given computational problem

   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

   Introduction: analysing algorithms, designing algorithms.

   Preparation: Lecture Slides and textbook chapters 1 & 2

2. WEEK 2

   Asymptotic Notation.

   Preparation: Lecture Slides and textbook chapter 3

3. WEEK 3

   Divide and Conquer Design Paradigm.

   Preparation: Lecture Slides and textbook chapter 4

4. WEEK 4

   Solving Recurrences.

   Preparation: Lecture Slides and textbook chapter 4

5. WEEK 5

   Analysis of Quicksort, Randomized Quicksort

   Preparation: Lecture Slides and textbook chapter 5

6. WEEK 6

   Heapsort.

   Preparation: Lecture Slides and textbook chapter 6

7. WEEK 7

   Quicksort.

   Preparation: Lecture Slides and textbook chapter 7

8. WEEK 8

   Sorting in Linear Time.

   Preparation: Lecture Slides and textbook chapter 8

9. WEEK 9

   Midterm Study

   Preparation: All the topics till Week 7.

10. WEEK 10

    Medians and Order Statistics.

    Preparation: Lecture Slides and textbook chapter 9

11. WEEK 11

    Dynamic Programming.

    Preparation: Lecture Slides and textbook chapter 15

12. WEEK 12

    Greedy Algorithms.

    Preparation: Lecture Slides and textbook chapter 16

13. WEEK 13

    Amortized Analysis, Dynamic Tables.

    Preparation: Lecture Slides and textbook chapter 17

14. WEEK 14

    Graphs, Breadth-first Search (BFS).

    Preparation: Lecture Slides and textbook chapter 22

ASSESSMENT

• Rate of Midterm Exam to Success50%
• Rate of Final Exam to Success50%

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