Algorithms I

What you'll learn

• Define algorithms, problem instances and input size, analyze algorithms in the RAM model by counting basic operations, distinguish best, worst and average cases, and use doubling experiments to check predicted growth.
• Prove and disprove asymptotic bounds using big-O, big-Omega, big-Theta, little-o and the limit test, order common functions by growth, and combine bounds for sequential and nested code.
• Analyze loops with summations, write recurrences for recursive algorithms, and solve them with recursion trees, substitution and the master theorem, recognizing when the master theorem does not apply.
• Implement and analyze selection sort, insertion sort and merge sort, relate insertion sort to inversions, prove merge sort correct by induction, and count inversions in Θ(n log n).
• Implement quicksort with random pivots, binary heaps and heapsort, build a heap in linear time, prove the Ω(n log n) lower bound for comparison sorting with decision trees, and apply counting and radix sort.
• Design divide-and-conquer algorithms for selection, the closest pair of points and integer multiplication, and analyze them with recurrences, including recurrences with unequal subproblems.
• Represent graphs with adjacency lists and matrices, choose between them, and implement breadth-first and depth-first search to find unweighted shortest paths, components and bipartitions in Θ(n + m).
• Classify edges in depth-first search, detect cycles, compute topological orders by DFS finish times and by Kahn's algorithm, and find strongly connected components with Kosaraju's algorithm.
• Solve single-source shortest-path problems with Dijkstra's algorithm, Bellman–Ford and DAG relaxation, justify each algorithm's correctness and restrictions, and detect negative cycles.
• Prove the cut and cycle properties, implement union–find with union by rank and path compression, and find minimum spanning trees with Kruskal's and Prim's algorithms.
• Design greedy algorithms for activity selection, interval partitioning, scheduling with deadlines and Huffman coding, prove them with greedy-stays-ahead and exchange arguments, and recognize problems where greedy fails.
• Apply amortized analysis, map real requirements to classic algorithmic problems, estimate costs before implementation, recognize NP-hard problems, and weigh constant factors and hardware effects in algorithm choice.