Sherif Khattab

October 2016

Examiners: Dr. Basheer Yousef and Dr. Sherif Khattab

الخوارزميات المتقدمة

يغطي الامتحان موضوعات متقدمة في الخوارزميات تشمل: الطرق الأساسية لتصميم الخوازرميات وطرق تحليل كل منها من حيث حساب السرعة والتأكد من صحة الحل، وهذه الطرق هي تكسير المسألة لمسائل صغيرة و التحديد غير المكتمل والبرمجة الديناميكية كما يشمل الامتحان الخوارزميات الخاصة بالشبكات وتأثير هياكل البيانات المتقدمة على سرعة الخوازميات وأخيرا يشمل الامتحان طرق حل المشاكل الصعبة و الحلول الممكنه باستخدام العشوائيات، التقريب, أو التحديد غير المكتمل.

 Reference: Introduction to Algorithms (2^nd Edition), Cormen, Leiserson, Rivest, and Stein (CLRS)

 Topics:

1.      Divide and conquer:

·         Asymptotic analysis including big-oh notation

·         Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, closest pair, and selection.

·         Running time analysis of divide-and-conquer algorithms.

·         The master method.

2.      Randomized algorithms:

·         Randomized QuickSort.

·         Randomized selection.

·         Computing the median in linear time.

·         A randomized algorithm for the minimum graph cut problem.

3.      Graph algorithms:

·         Graph primitives.

·         Depth- and breadth-first search.

·         Connected components in undirected graphs.

·         Topological sort in directed acyclic graphs.

·         Strongly connected components in directed graphs.

·         Dijkstra's shortest-path algorithm.

4.      Advanced data structures:

·         Heaps and applications.

·         Hash tables and applications.

·         Balanced binary search trees.

·         Union-Find Data Structure.

5.      Greedy algorithms:

·         Scheduling.

·         Prim's Minimum Spanning Tree Algorithm.

·         Kruskal's Minimum Spanning Tree Algorithm.

·         Clustering.

·         Huffman Codes.

6.      Dynamic Programming:

·         The Knapsack Problem.

·         Sequence Alignment.

·         Optimal Search Trees.

·         Single-Source Shortest Paths (The Bellman-Ford Algorithm)

·         Internet Routing.

·         The All-Pairs Shortest Paths Problem.

·         The Floyd-Warshall Algorithm.

·         Johnson's Algorithm.

7.      NP-Completeness:

·         P, NP, and What They Mean.

·         Reductions between Problems.

·         NP-Complete Problems.

·         The P vs. NP Problem.

·         Solvable Special Cases of NP-Complete Problems.

·         Smarter (But Still Exponential-Time) Search Algorithms for NP-Complete Problems (Vertex Cover Problem)

·         Heuristics with Provable Guarantees (Approximation Algorithms).

·         Greedy and Dynamic Programming Heuristics for the Knapsack Problem.

·         Local Search: General Principles, Max Cut, and 2SAT.

Support Material: The exam topics are covered in the following online courses:

https://www.coursera.org/learn/algorithm-design-analysis

The slides are also available at:

http://theory.stanford.edu/~tim/mooc/algo1slides.zip

http://theory.stanford.edu/~tim/mooc/algo2slides.zip