Algorithms and Data Structures

List of topics:
  1. Introduction. Computing Fibonacci numbers, time and space complexity of algorithms, asymptotic growth (logarithm, polynomial, exponent).
  2. Elementary data structures. Array, stack, list, queue, tree, dynamic array. Amortized analysis,
  3. Recurrence relations. Divide and conquer. The master theorem: $T(n)=aT(\lceil n/b \rceil)+O(n^d)$. Binary search. Mergesort.
  4. Sorting. Mergesort, heapsort, quicksort, quicksort3. Lower bound $\Omega(n\log n)$ for comparison sorting. Radixsort, countsort.
  5. Order statistics. Randomized and determenistic linear algorithms.
  6. Graph decompositions. Depth-first search, connected components in undirected graphs, topological sorting of dags, strongly connected components.
  7. Paths in graphs. Breadth-first search, shortest paths, Dijkstra algorithm, Bellman-Ford algorithm.
  8. Greedy algorithms. Minimum spanning tree, Prim and Kruskal algorithms, disjoint sets (with path compression), Huffman encoding, Horm formulas, set cover.
  9. Dynamic programming. Shortest paths in dags, longest increasing subsequence, edit distance, knapsack, chain matrix multiplication, shortest paths, independent sets in trees.
  10. Search trees. AVL tree, splay tree, cartesian tree, treap.
  11. Hashing. Chain hashing, universal hashing.
  12. Range minimum/sum query (RMQ) and least common ancestor (LCA). Constant-time queries with linear-time preprocessing.
  13. Linear programming. Simplex method, flows in graphs.
  14. Algorithms with numbers. Basic arithmetic, modular arithmetic, primality testing, RSA.
  15. Fast Fourier transform. Multiplying two polynomials in $O(n\log n)$.
  16. Pattern matching. KMP, suffix tree, suffix array.
  17. Randomized algorithms. All pairs shortest paths, min-cut, polynomial identity testing.
  18. Geometry algorithms. Convex hull, closest pair of points.
  19. NP-complete problems. Easy and hard problems, reductions. NP-completeness of SAT, maximum independent set, vertex cover.
  20. Exact algorithms for NP-hard problems. Branch and bound, splitting, local search.
  21. Approximation algorithms. Approximation algorithms for MIN-TSP, vertex cover, FPTAS for knapsack.

References

  • Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, Cambridge, second edition, 2001.
  • R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.