3️MIT 6.046J

Design and Analysis of Algorithms

Algorithmic Paradigms

• Divide and conquer

• Dynamic programming

• Greedy algorithms

• Graph algorithms

• NP-completeness

Divide and conquer

This technique involves breaking a problem down into smaller sub-problems, solving each sub-problem recursively, and then combining the solutions to the sub-problems to obtain a solution to the original problem. For instance, binary_search, merge sort, quicksort and Karatsuba algorithm for multiplying large integers.

Dynamic programming

This technique involves solving a problem by breaking it down into smaller sub-problems and then solving each sub-problem only once and storing the solution for future use. This can be more efficient than solving the sub-problems repeatedly.

Greedy algorithms

This technique involves making locally optimal choices at each step in the hope of finding a global optimum. For example, like Huffman coding, Prim's algorithm for minimum spanning trees, and Dijkstra's algorithm for shortest paths in a graph.

Graph algorithms

This topic covers a range of algorithms for working with graphs, including algorithms for finding shortest paths, minimum spanning trees, and maximum flows. For exmaple, like Dijkstra's algorithm, Prim's algorithm, Kruskal's algorithm for minimum spanning trees, and the Ford-Fulkerson algorithm for maximum flow.

NP-completeness

This topic deals with the complexity of computational problems and the class of problems that are considered "intractable" (i.e., cannot be solved efficiently using current algorithms). For example, like the traveling salesman problem and the Boolean satisfiability problem.