Information, assessment, format, assignments, policies, topics, and the role of algorithms in computing.
Insertion sort, merge sort, asymptotic analysis, recurrences, loop invariants, linear search, binary search.
Asymptotic notations, omega, theta, recurrences, substitution, master method.
Stacks, queues, lists, trees, dynamic sets, pointers and objects, rooted trees, asymptotic analysis.
Indicator random variables, inversions, randomized algorithms, skip lists, the hiring problem.
Analysis of chaining, universal chaining, open addressing, direct address tables, hash functions.
Substitution, master method, recurrence relations, induction, maximum subarray problem, Strassen’s algorithm.
Queries, insertion, deletion, modification, height, performance.
Heaps, correctness, run-time analysis, priority queues, application to sorting.
Randomizing, lower bounds on comparison sorts, counting sort, radix sort, bucket sort.
(2,4) trees, red-black trees, insertion, deletion, rotations, comparison of dictionary implementations.
Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.
Dynamic programming, activity scheduling, the greedy strategy, Huffman codes.
Definitions, methods, breadth first search, depth first search, shortest path, asymptotic complexity, topological sort, strongly connected components.
Aggregate method, accounting method, potential method, dynamic tables, multipop example.
Union-find, linked list representation, forest representation, finding connected components.
Generic algorithm, safe edge algorithm, Kruskal’s algorithm, Prim’s algorithm, shortest path, dense paths.
Bellman-Ford algorithm, shortest paths in direct acyclic graphs, Dijsktra’s algorithm.
Johnson’s algorithm, Floyd-Warshall algorithm, dynamic programming for dense graphs, transitive closure
Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, maximum bipartite matching
Gaussian elimination, simplex method.
Concepts, modeling and measuring dynamic multithreading, analysis of multithreaded algorithms, matrix multiplication example, merge sort example.
Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm
P and NP classes, encoding problems and polynomial time verification, constructing NPC
Vertex cover example, TSP example, randomization and linear programming strategies