Modules Topics covered in this class.
1. Introduction
Information, assessment, format, assignments, policies, topics, and the role of algorithms in computing.
2. Analysis examples
Insertion sort, merge sort, asymptotic analysis, recurrences, loop invariants, linear search, binary search.
3. Growth of functions
Asymptotic notations, omega, theta, recurrences, substitution, master method.
4. Abstract data types
Stacks, queues, lists, trees, dynamic sets, pointers and objects, rooted trees, asymptotic analysis.
5. Probabilistic Analysis
Indicator random variables, inversions, randomized algorithms, skip lists, the hiring problem.
6. Hash Tables
Analysis of chaining, universal chaining, open addressing, direct address tables, hash functions.
7. Divide and conquer
Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.
8. Binary Search Trees
Queries, insertion, deletion, modification, height, performance.
9. Heapsort
Heaps, correctness, run-time analysis, priority queues, application to sorting.
10. Quicksort
Randomizing, lower bounds on comparison sorts, counting sort, radix sort, bucket sort.
11. Balanced Trees
(2,4) trees, red-black trees, insertion, deletion, rotations, comparison of dictionary implementations.
12. Dynamic Programming
Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.
13. Greedy Algorithms
Dynamic programming, activity scheduling, the greedy strategy, Huffman codes.
14. Graphs
Definitions, methods, breadth first search, depth first search, shortest path, asymptotic complexity, topological sort, strongly connected components.
15. Amortized analysis
Aggregate method, accounting method, potential method, dynamic tables, multipop example.
16. Disjoint sets
Union-find, linked list representation, forest representation, finding connected components.
17. Minimum spanning tree
Generic algorithm, safe edge algorithm, Kruskal’s algorithm, Prim’s algorithm, shortest path, dense paths.
18. Single source shortest paths
Bellman-Ford algorithm, shortest paths in direct acyclic graphs, Dijsktra’s algorithm.
19. All pairs shortest paths
Johnson’s algorithm, Floyd-Warshall algorithm, dynamic programming for dense graphs, transitive closure
20. Maximum flow
Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, maximum bipartite matching
22. Multithreading
Concepts, modeling and measuring dynamic multithreading, analysis of multithreaded algorithms, matrix multiplication example, merge sort example.
23. String matching
Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm
24. NP-completeness
P and NP classes, encoding problems and polynomial time verification, constructing NPC
25. Approximation algorithms
Vertex cover example, TSP example, randomization and linear programming strategies