1. Algorithm design: specification, correctness, invariants, termination; stable matching (Gale-Shapley); asymptotic notation, input size. 2. Greedy algorithms: interval scheduling, counterexamples, exchange argument, "stays ahead"; minimising lateness; Huffman coding. 3. Greedy on graphs: cut property; minimum spanning trees (Boruvka, Jarnik-Prim, Kruskal), union-find; Dijkstra, A*, admissible heuristics. 4. Divide and conquer: binary search, mergesort, counting inversions; recurrences, recursion trees, substitution, Master theorem; sorting lower bound. 5. Divide and conquer II: Karatsuba multiplication; linear-time selection (median of medians); closest pair of points; FFT. 6. Dynamic programming I: overlapping subproblems, memoisation, tabulation, state design; weighted intervals; paths in a DAG; reconstruction. 7. Dynamic programming II: 0/1 knapsack and pseudopolynomial time; edit distance and alignment; optimal BST; memory optimisation. 8. Network flows: residual network, augmenting paths, Ford-Fulkerson, Edmonds-Karp; max-flow/min-cut; matching, disjoint paths, project selection. 9. Systematic search: state-space tree, backtracking, safe pruning; n queens; constraint satisfaction, propagation, MRV; SAT and DPLL. 10. Branch and bound: incumbent, bounds, relaxations, node selection, optimality gap; integer programming; P and NP, reductions, NP-completeness. 11. Adversarial design: game trees, minimax, alpha-beta, negamax, move ordering; depth limits, evaluation functions, transposition tables. 12. Approximation and heuristics: approximation ratio; vertex cover, set cover, metric TSP; PTAS/FPTAS; local search, simulated annealing. 13. Randomisation and synthesis: Las Vegas and Monte Carlo, linearity of expectation; randomised quicksort, Karger's min-cut; choosing a method.
|
-
Anany Levitin. (2003). The design & Analysis of Algorithms.
-
Bhargava, A. Y. (2016). Algorithms.. Manning Publications Co.
-
CORMEN, T. H., LEISERSON C. E., RIVEST D. L., STEIN C. (2001). Introduction to Algorithms, Second Edition.
-
Dasgupta, S., Papadimitriou, C. H., Vazirani U. (2006). Algorithms. McGraw.
-
Kleinberg J., Tardos, E. (2006). Algorithm design. Pearson Education.
-
Kozen, D.C. (1992). The design and analysis of algorithms.
-
Manber U. (1989). Introduction to Algorithms. A creative approach.. Addison.
-
Skiena, S.S. (2012). The Algorithm Design Manual. Springer.
|