بداية المرحلة الجامعيةComputationمُخطَّط له
Algorithm design and analysis
Recursion and divide and conquer, greedy algorithms, dynamic programming, graph algorithms (breadth- and depth-first search, shortest paths, spanning trees), asymptotic analysis and correctness proofs.
math.comp.algorithm-design
لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.
يعتمد على
عدد المتطلبات السابقة الإلزامية (حتى الأساس): 18
ستتعلّم
- Design divide-and-conquer algorithms and analyse them with recurrences, as for mergesort.
- Prove the correctness of greedy algorithms such as Kruskal's algorithm and Dijkstra's algorithm with non-negative weights.
- Design dynamic-programming algorithms for problems such as longest common subsequence.
تعريف
- Divide and conquer splits a problem into smaller instances, solves them recursively and combines the results.
- Dynamic programming solves a problem by combining solutions of overlapping subproblems, storing them to avoid recomputation.
مبرهنة
- Mergesort runs in O(n log n) time.
- Dijkstra's algorithm finds shortest paths from a source vertex when all edge weights are non-negative.
- Kruskal's algorithm finds a minimum spanning tree of a connected weighted graph.
مفاهيم خاطئة شائعة
- Using Dijkstra's algorithm when some edge weights are negative.
- Assuming a greedy algorithm is correct without a proof.
يقود إلى
اكتشافات اختيارية
- Graph theory Matching and network-flow algorithms are algorithmic counterparts of theorems such as Hall's and Menger's.
- ← Dots and lines: networks and puzzles
مسارات التعلّم
قراءات إضافية
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005)