Asymptotics, representation of input and input size,
polynomial vs exponential running time, decision, search
and optimization problems
Basic numeric algorithms
- addition, subtraction, multiplication of n-bit numbers
Graphs
- basics, adjacency lists vs matrix,
- undirected vs directed, paths, cycles, walks
- basic search for reachability
- DFS, BFS, properties
- DAGs, properties (sinks, sources), topological sort
- linear time algorithms to check various reachability properties etc.
- strong connected components, meta graph, knowledge that meta graph
can be constructed via a linear time algorithm
Single-source shortest path algorithms
- definitions
- BFS and Dijkstra's algorithm for non-negative lengths
- shortest path trees
- Negative length edges and generic algorithm
- Bellman-Ford algorithm for negative cycle detection and
shortest paths with negative length edges
- Linear time algorithm for shortest paths in DAGs with negative lengths
Recursion
- recursive algorithms
- recurrences and ability to solve them asymptotically via
unfolding, recursion trees, guess and verify
- Divide and conquer technique
- Binary search
Sorting and selection
- Algorithms for sorting
- Linear time algorithm for selection and medians