everything.study
COMP 6651

Algorithm Design Techniques

4 credits · Graduate

Fall 2005 · Design and Analysis of Algorithms

Topics

  • Asymptotic analysis
  • Recurrences
  • Randomized algorithms
  • Quicksort and heapsort
  • Amortized analysis
  • Fibonacci heaps
  • Splay trees
  • Order statistics
  • NP-completeness
  • Approximation
  • Dynamic programming
  • Greedy algorithms
  • Graph algorithms

Readings

  • Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
    Recommended / optional / reference
  • Adrian Bondy and U.S.R. Murty, Graph Theory with Applications.
    Recommended / optional / reference
  • Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice Hall, 1988.
    Recommended / optional / reference
  • R.E. Tarjan, Data Structures and Network Algorithms.
    Recommended / optional / reference
  • D.D. Sleator and R.E. Tarjan, “Self-adjusting binary search trees,” Journal of the ACM 32(3), 652–686, 1985.
    Listed reading
  • M.L. Fredman, R. Sedgewick, D.D. Sleator and R.E. Tarjan, “The Pairing Heap: A New Form of Self-Adjusting Heap,” Algorithmica 1(1), 111–129, 1986.
    Listed reading
  • M.L. Fredman, “On the efficiency of pairing heaps and related data structures,” Journal of the ACM 46(4), 473–501, 1999.
    Listed reading
  • Listed textbook; requirement not explicitly stated: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 2nd ed., MIT Press/McGraw-Hill, 2001.
    Listed reading
Sources