المرفقات
المحاضرات
الإسم تفاصيل أخرى
PowerPoint Slides

PowerPoint Slides for the course

Chapter 11

computational complexity

الخطة الدراسية
3401 عال  -  تحليل وتصميم الخوارزميات
عدد الوحدات عدد الساعات
نظري عملي
3 3 0
وصف المقرر

This course introduces formal techniques to support the design and analysis of algorithms, focusing on both the underlying mathematical theory and practical considerations of efficiency. Topics include correctness of algorithms, asymptotic notation, recurrences and Master theorem, divide and conquer, transform and conquer (Balanced Trees), time-space trade-offs, median and order statistics, searching and sorting algorithms, dynamic programming, greedy algorithms, branch-and-bound, recursive backtracking, computational geometry, string matching. Optional material: NP-completeness, competitive analysis, amortized analysis, randomized algorithms and approximation algorithms.

المتطلبات

CS2311

الكتاب

Introduction to the Design and Analysis of Algorithms

المؤلفين

Anany V. Levitin

المحاضرين

Dr. Mohammad Alhawarat

احتساب الدرجات
نوع التقييم الدرجة
   1 .  First Exam 25 % ()
   2 .  Second Exam 25 % ()
   3 .  Quizzes 10 % ()
   4 .  Final Exam 40 % ()
الأهداف
الهدف التقييم
   1 .  Identify Algorithms main concepts, Asymptotic notations, Algorithm’s Analysis techniques and Complexity Classes. Exams & Quizzes
   2 .  Describe different design techniques including Brute Force, Exhaustive Search, Divide & Conquer, Dynamic Programming, Greedy Algorithms and Time-Space Tradeoffs. Exams & Quizzes
   3 .  Solve several computation problems such as sorting, order statistics, searching, computational geometry and graph problems using the appropriate algorithmic design technique. Exams & Quizzes
   4 .  Analyze the efficiency of an algorithm using appropriate analysis technique. Exams & Quizzes
   5 .  Distinguish the worst/average cases running time for known algorithms. Exams & Quizzes
   6 .  Specify the most appropriate design technique in solving a computational problem. Exams & Quizzes
الموضوعات
الأسبوع الوصف - القراءة  
1-15
  • Introduction and mathematical background
  • Asymptotic analysis
  • Recurrence
  • Brute Force & Exhaustive Search
  • Sorting and order statistics
  • Divide and conquer and Randomized algorithms
  • Transform & Conquer
  • Space-Time Trade-offs, String matching
  • Dynamic programming and Greedy algorithms
  • Optional Topics: NP-completeness, competitive analysis, branch-and-bound, amortized analysis and approximation algorithms.

القراءة:

Introduction to the Design and Analysis of Algorithms", Anany V. Levitin, Addison-Wesley, Latest Edition. ISBN-10: 0132316811, ISBN-13: 978-0132316811