Shahada ya kwanza (mwanzo)ComputationImepangwa
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
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 18 (hadi chini kabisa)
Utajifunza
- 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.
Fasili
- 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.
Nadharia
- 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.
Mawazo potofu ya kawaida
- Using Dijkstra's algorithm when some edge weights are negative.
- Assuming a greedy algorithm is correct without a proof.
Inaelekea kwa
Ugunduzi wa hiari
- 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
Njia za kujifunza
Usomaji zaidi
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005)