स्नातक (प्रारंभिक)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)