Modules Topics covered in this class.

This page presents the “modules”, or the topics that are covered in this course.

Click on the tile associated with a module to go to a page containing that module’s contents.

1. Analysis examples

Insertion sort, merge sort, asymptotic analysis, recurrences, loop invariants, linear search, binary search.

2. Growth of functions

Asymptotic notations, omega, theta, recurrences, substitution, master method.

3. Abstract data types

Stacks, queues, lists, trees, dynamic sets, pointers and objects, rooted trees, asymptotic analysis.

4. Probabilistic Analysis

Indicator random variables, inversions, randomized algorithms, skip lists, the hiring problem.

5. Hash Tables

Analysis of chaining, universal chaining, open addressing, direct address tables, hash functions.

6. Divide and conquer

Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.

7. Binary Search Trees

Queries, insertion, deletion, modification, height, performance.

8. Heapsort

Heaps, correctness, run-time analysis, priority queues, application to sorting.

9. Quicksort

Randomizing, lower bounds on comparison sorts, counting sort, radix sort, bucket sort.

10. Balanced Trees

(2,4) trees, red-black trees, insertion, deletion, rotations, comparison of dictionary implementations.

11. Dynamic Programming

Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.

12. Greedy Algorithms

Dynamic programming, activity scheduling, the greedy strategy, Huffman codes.

13. Graphs

Definitions, methods, breadth first search, depth first search, shortest path, asymptotic complexity, topological sort, strongly connected components.

14. Amortized analysis

Aggregate method, accounting method, potential method, dynamic tables, multipop example.

15. Disjoint sets

Union-find, linked list representation, forest representation, finding connected components.

16. Minimum spanning tree

Generic algorithm, safe edge algorithm, Kruskal’s algorithm, Prim’s algorithm, shortest path, dense paths.

17. Single source shortest paths

Bellman-Ford algorithm, shortest paths in direct acyclic graphs, Dijsktra’s algorithm.

18. All pairs shortest paths

Johnson’s algorithm, Floyd-Warshall algorithm, dynamic programming for dense graphs, transitive closure

19. Maximum flow

Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, maximum bipartite matching

20. Linear programming

Gaussian elimination, simplex method.

21. Multithreading

Concepts, modeling and measuring dynamic multithreading, analysis of multithreaded algorithms, matrix multiplication example, merge sort example.

22. String matching

Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm

23. NP-completeness

P and NP classes, encoding problems and polynomial time verification, constructing NPC

24. Approximation algorithms

Vertex cover example, TSP example, randomization and linear programming strategies