- Divide and Conquer Paradigm
- Solving recurrences characterizing the running time of divide and conquer algorithms.
- Familiarity with specific Divide and Conquer Algorithms and the running times: Binary Search, Merge Sort, Quick Sort, Karatsuba's Algorithm, Linear Selection.
- Ability to design and analyze divide and conquer algorithms for new problems.
- Backtracking and Dynamic Programming Algorithms
- Using the dynamic programming methodology to design algorithms for new problems.
- Ability to analyze the running time of dynamic programming algorithms.
- Graphs
- Basic definitions of undirected and directed graphs, DAGs, paths, cycles.
- Definitions of reachable nodes, connected components, and strongly connected components.
- Understand the structure of directed graphs in terms of the meta-graph of strongly connected components.
- Understand the structure of DAGs: sources, sinks and topological sort.
- Graph Search
- Understand properties of the basic search algorithm and its running time.
- Understand properties of depth first search traversal on directed and undirected graph.
- Understand properties of the depth first search tree.
- Understand properties of depth first search traversal on directed and undirected graph.
- Algorithms based on search for finding connected components in undirected graphs, checking whether a graph is a DAG, topological sort for DAGs, knowledge of a linear-time algorithm to create the meta-graph, finding a cycle in a graph etc.
- Shortest Paths in Graphs
- Understand properties of the breadth first search tree.
- Understand properties of breadth first search traversal on directed and undirected graph to find distances in unweighted graphs.
- Dijkstra's algorithm for finding single-source shortest paths in undirected and directed graphs with non-negative edge lengths.
- Negative length edges and Bellman-Ford algorithm to check for negative length cycles or find shortest paths if there is none.
- Single-source shortest paths in DAGs—linear time algorithm for arbitrary edge lengths.
- Shortest path trees and their basic properties.
- Dynamic programming for shortest path problems in graphs.
- Graph reductions and tricks
- Modeling problems via graphs and solving them using graph structure, reachability and shortest path algorithms.
- Adding sources, sinks, splitting edges, nodes
- Creating layered graphs