BSc Course Weekly Outline

BSc Course Weekly Outline

Course Instructor Asst. Prof. Dr. Ali Kadhum Idrees
E_mail ali.kadhum.idrees@gmail.com
ali.idrees@uobabylon.edu.iq

Course Title Algorithm Design and Analysis (1)

Course Objective
1- تعلم كيفية كتابة خوارزمية متضمنة كل شروطها.
2- تعلم أهم أنواع الخوارزميات وكيفية التعبير عن الخوارزمية والفرق بين الخوارزمية والبرنامج.
3- تعلم كيفية استخراج متطلبات الخزن للخوارزميات التكرارية (Iterative Algorithms) والخوارزميات المرتدة (Recursion Algorithms).
4- تعلم كيفية استخراج متطلبات الوقت للخوارزميات التكرارية (Iterative Algorithms) والخوارزميات المرتدة(Recursion Algorithms) باستخدام طرق تحليل الخوارزميات.
5- تعلم كيفية استخدام طريقة عد العمليات(Operations count method) للتعبير عن وقت الخوارزمية.
6- تعلم كيفية استخدام طريقة عد الخطوات(Steps count method) للتعبير عن وقت الخوارزمية.
7- تعلم كيفية استخدام التدوينات التقاربية للتعبير عن تعقيدات الوقت والخزن ولجميع أنواع الخوارزميات بالإضافة إلى كيفية استخدامها للمقارنة بين الخوارزميات.
8- تعلم كيفية عمل العلاقات التداخلية للخوارزميات المرتدة وكيفية حلها بالإضافة إلى كيفية استخراج وقت وخزن هكذا خوارزميات.
9- تعلم كيفية استخراج متطلبات الوقت بالحالات الأفضل و الأسوأ والمتوسطة للخوارزميات.
10- تعلم خوارزميات الترتيب الخطية وكيفية تحليلها للحصول على متطلبات الخزن والوقت لها.
11- معرفة كيفية التخطيط لتجربة لغرض قياس انجازية الخوارزميات.
12- فهم فكرة طريقة تصميم الخوارزميات Divide-and-Conquer وكيفية تطبيقها في حل المشاكل من خلال اخذ بعض أمثلة المشاكل وكيفية حلها بهذه الطريقة.
13- فهم فكرة مسألة البحث الثنائي وكيفية استخدام طريقة التصميم Divide-and-Conquer لتصميم خوارزمية لهذه المسألة وكيفية تحليل هذه الخوارزمية.
14- فهم فكرة مسألة ترتيب الدمج وكيفية استخدام طريقة التصميم Divide-and-Conquer لتصميم خوارزمية لهذه المسألة وكيفية تحليل هذه الخوارزمية.
15- فهم فكرة مسألة الترتيب السريع وكيفية استخدام طريقة التصميم Divide-and-Conquer لتصميم خوارزمية لهذه المسألة وكيفية تحليل هذه الخوارزمية.
فهم فكرة طريقة تصميم الخوارزميات Greedy Method وكيفية تطبيقها في حل مسائل الامثلية من خلال اخذ بعض الأمثلة وكيفية حلها بهذه الطريقة.
16- تعلم كيفية استخدام خوارزمية دايجسترا لحساب اقصر المسارات في المخططات واهم تطبيقاتها .

Course Description
يعتبر موضوع تصميم وتحليل الخوارزميات من المواضيع المهمة والأساسية في علوم الحواسيب وذلك لأنه يعلم الطالب القدرة على تحليل كل أنواع الخوارزميات ومعرفة ما تحتاجه من الوقت والخزن ، التنبؤ بسلوكية الخوارزميات بالإضافة إلى إمكانية المقارنة بين الخوارزميات بالإضافة إلى إمكانية حل المشاكل التي توجهننا باستخدام طريقة التصميم المناسبة. ستوضح طرق عد الخطوات والعمليات . بعد ذلك ستوضح أسلوب التدوينات التقاربية ثم كيفية حساب الحالات الأفضل والاسوأ للخوارزميات. بعد ذلك ستعطى بعض طرق التصميم مثل قسم تسد وطريقة الجشع مع بعض الاكثلة عليها.
References 1. ATALLAH, M. J. (1999). Algorithms and theory of computation handbook, CRC Press.
2. Cormen,T. H., Leiserson,C. E., Rivest, R. L., and Stein, C.(2001). Introduction to Algorithms, Second Edition, MIT press.
3. Drozdek, A.(2001). data structures and algorithms in C++, 2nd Edition, Brokes/Cole.
4. EDMONDS, J. (2008). HOW TO THINK ABOUT ALGORITHMS, Cambridge University Press.
5. Horowitz, E., Sahni, S., and Rajasekaran, S. (1997).Computer Algorithms/C++, W.H.Freeman Press.
6. Kleinberg, J. and Tardos, E. (2006). Algorithm Design , 1st edition, Pearson Education, Inc..
7. Leiss , E. L.(2007). A Programmer’s Companion to Algorithm Analysis, Chapman & Hall/CRC.
8. McConnell, J. J.(2001). Analysis of Algorithms:An Active Learning Approach, Jones and Bartlett Publishers, Inc.
9. Miller, R. and Boxer, L. (2005).Algorithms Sequential and Parallel: A Unified Approach, 2nd Edition, Career & Professional Group, a division of Thomson Learning Inc.
10. Neapolitan, R. and Naimipour, K.(2004). Foundations of Algorithms Using C++ Pseudocode, Third Edition, Jones and Bartlett Publishers.
11. parberry, I.(2001). Lecture notes on algorithm analysis and computational complexity, Fourth Edition, university of north texas.
12. parberry, I. and Gasarch, W.(2002). problems on algorithms, second Edition, I. parberry and W. Gasarch.
13. Alsuwaiyel, M. H.(1999). Algorithms design techniques and analysis, world scientific publishing.
14. Sahni, S.(1998). data structures, algorithms, and applications in c++, McGraw-Hill companies, Inc.
15. Skiena, S. S.(2008). The Algorithm Design Manual, 2nd edition, Springer-Verlag London Limited.

Course Assessment Term Tests Laboratory Quizzes Project Final Exam
(17%) (33 %) (%) (50%)


General Notes

1- تغلق جميع الهواتف قبل دخول القاعة
2- لا يسمح بدخول القاعة بعد دخول الاستاذ وبعد المحاضرة
3- سيكون هناك 2 امتحان بنظام المودل و2 امتحان ورقي.
4- تقسيم درجة السعي 10 درجة لكل امتحان مودل و10 درجة لكل امتحان ورقي و10 درجة لنشاط الطالبة فبكون المجموع 50 درجة للسعي النهائي.
5- طرائق التدريس المعتمدة: سيتم استخدام الطريقتين التاليتين من خلال الدمج بينهما
1- طريقة المحاضرة. 2- طريقة المناقشة.
وباستخدام الوسائل التعليمية الآتية:
• الحاسوب.
• وسائل العرض ( شاشة LCD 47” ).
• سبورة مع قلم الماجك.
• المختبرات العملية.


Course weekly Outline
week Date Topics Covered Reading
1 4/10/2017 Introduction to Algorithm Design and Analysis and reviewing the syllabus and study plan [1-15]
2 11/10/2017 Algorithms definition: it s conditions, Algorithm analysis methods: space and time complexity, Operations Count Method with examples [1-15]
3 18/10 Step count method, Analysis of the recursion codes with step count method, some mathematical facts, summation formula and complexity analysis from pseudo-code [1-15]
4 25/10 complexity analysis by Asymptotic Notations with Examples [1-15]
5 2/11 The best, Average and worst case Analysis with examples. [1-15]
6 9/11 Performance measurement with example [1-15]
7 16/11 First Exam
8 23/11 Divide-and-Conquer method with binary search Example [1-15]
9 30/11 Divide-and-Conquer method for Merge sort problem [1-15]
10 7/12 Divide-and-Conquer method for Quick sort problem [1-15]
11 14/12 Greedy Method with knapsack problem example [1-15]
12 21/12 Greedy Method for optimal storage pattern, optimal merge pattern. [1-15]
13 28/12 Greedy Method single source shortest path problem ( Dijkstra Algorithm ) [1-15]
14 3/1/2018 Greedy Method for scheduling problem [1-15]
15 10/1 Second Exam


Instructor Signature: Head of Dep. Signature: