Topics that might be on the second examination on October 27 2022

A few time complexity and recurrence problems, since not everyone has
mastered them.

Be able to write pseudocode:
 1. Floyd Warshall algorithm.
 2. Bellman Ford algorithm.

Be able to step through Dijkstra's algorithm for a small graph.

Johnson's algorithm.
 Given a figure showing a weighted directed graph with some negative weights,
 Update the weights on edges so that there are no negative weights.

What is the worst-case time complexity for each of those four algorithms?

Dynamic Programming, possibly with memoization.

Example problem: maximum sum contiguous subsequence.  Given a sequence of
numbers, each either positive or negative, find a contiguous subsequence of
maximum total.  As an example if the input sequence is 3,-4,8,-2,3,5,-1,6,-5
the output sequence is 8,-2,3,5,-1,6.  There are several algorithms for this
problem.
1. Dumb Brute Force: O(n^3) time.
2. Slightly Smarter Brute Force: O(n^2) time.
3. Divide and Conquer: O(log n) time.
4. Dynamic Programming: O(n) time.

BFPRT (median of medians) algorithm for Selection.
 Explain how to obtain the recurrence for the time complexity, that is
 T(n) <= T(n/5)+T(7n/10)+n.

Find components of an undirected graph using union/find.

Heapsort.  O(n log n) time.  A sped up version of selection sort.