- 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
- Ability to save space in iterative algorithms derived via dynamic programming
- 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.
- 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 in particular for finding hop-constrained paths.
- Negative length edges and Bellman-Ford algorithm to check for negative length cycles or find shortest paths if there is none. We do not plan to emphasize this topic on midterm 2
- 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