Design and Analysis of Algorithms

What you’ll study

Techniques for the analysis of algorithms; methods for the design of efficient algorithms; divide and conquer; merge sort; the greedy method; dynamic programming; backtracking — the graph-colouring problem, the n-queens problem and the Hamiltonian cycle; branch and bound; basic search and traversal techniques; topological sorting; connected components; graph algorithms — shortest path and spanning tree; flow algorithms — the Ford-Fulkerson method, maximum bipartite matching; algebraic simplification and transformations; string-matching problems — the naïve string-matching algorithm, the Boyer-Moore algorithm and the Knuth-Morris-Pratt algorithm; approximation algorithms; the knapsack problem; matrix chain multiplication; lower-bound theory; NP-hard and NP-complete problems.