Design and Analysis of Algorithms

Dasgupta, Sanjoy, Christos Papadimitriou, and Umesh Vazirani. Algorithms . McGraw-Hill, 2006. ISBN: 9780073523408.

Kleinberg, Jon, and Eva Tardos. Algorithm Design . Addison-Wesley, 2005. ISBN: 9780321295354.

Bentley, Jon. Programming Pearls . Association for Computing Machinery, 1986. ISBN: 9780201103311. Applications of algorithm design techniques to software engineering.

———. More Programming Pearls: Confessions of a Coder . Addison-Wesley, 1988. ISBN: 9780201118896. More applications of algorithm design techniques to software engineering.

———. Writing Efficient Programs . Prentice-Hall, 1982. ISBN: 9780139702518. Performance hacking extraordinaire.

Gonnet, Gaston. Handbook of Algorithms and Data Structures: Coded in Pascal and C . Addison-Wesley, 1984. ISBN: 9780201142181. Pascal and C code, comparisons of actual running times, and pointers to analysis in research papers.

Even, Shimon. Graph Algorithms . Computer Science Press, 1979. ISBN: 9780914894216. Broad treatment of graph algorithms, including network flow and planarity.

Garey, Michael, and David Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979. ISBN: 9780716710455. Reference book devoted to NP-completeness. Second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.

Lawler, Eugene. Combinatorial Optimization: Networks and Matroids . Holt, Rinehart, and Winston, 1976. Dense graph algorithms, network flows, and linear programming. First few chapters are excellent.

Papadimitriou, Christos, and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity . Prentice-Hall, 1981. ISBN: 9780131524620. Linear programming and its variants.

Sipser, Michael. Introduction to the Theory of Computation . PWS, 1997. A good text on computability and complexity theory, with proof ideas to kick off each proof.

Chung, Kai. Elementary Probability Theory with Stochastic Processes . Springer, 1974. Intuitive introduction to probability.

Feller, William. An Introduction to Probability Theory and Its Applications . Wiley, 1968 (Volume 1), 1971 (Volume 2). ISBN: 9780471257080. Excellent reference for probability theory.

Liu, Chung. Introduction to Combinatorial Mathematics . McGraw-Hill College, 1968. ISBN: 9780070381247. Combinatorial mathematics relevant to computer science. Excellent problems.

Niven, Ivan, and Herbert Zuckerman. An Introduction to the Theory of Numbers . John Wiley & Sons, 1991. ISBN: 9789971513016. Readable introduction to number theory.

The table below provides information on the course’s reading assignments, which are taken from the course textbook:

Analysis of Algorithms, Insertion Sort, Mergesort Chapters 1-2

Substitution, Master Method Chapters 3-4, excluding section 4.6

SES #: L3 · TOPICS: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication · READINGS: Sections 4.2 and 30.1

SES #: L4 · TOPICS: Quicksort, Randomized Algorithms · READINGS: Sections 5.1-5.3

SES #: R3 · TOPICS: Heapsort, Dynamic Sets, Priority Queues · READINGS: Chapter 6

SES #: L5 · TOPICS: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort · READINGS: Sections 8.1-8.3

SES #: L6 · TOPICS: Order Statistics, Median · READINGS: Chapter 9

SES #: L7 · TOPICS: Hashing, Hash Functions · READINGS: Sections 11.1-11.3

SES #: L8 · TOPICS: Universal Hashing, Perfect Hashing · READINGS: Section 11.5

SES #: R6 · TOPICS: Binary Search Trees, Tree Walks · READINGS: Sections 12.1-12.3

SES #: L10 · TOPICS: Red-black Trees, Rotations, Insertions, Deletions · READINGS: Chapter 13

SES #: L11 · TOPICS: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees · READINGS: Chapter 14

SES #: L13 · TOPICS: Amortized Algorithms, Table Doubling, Potential Method · READINGS: Chapter 17

SES #: L14 · TOPICS: Competitive Analysis: Self-organizing Lists · READINGS: Sleator, Daniel D., and Robert E. Tarjan. “Amortized efficiency of list update and paging rules.” Communications of the ACM 28, no. 2 (February 1985): 202-208.

SES #: L15 · TOPICS: Dynamic Programming, Longest Common Subsequence · READINGS: Chapter 15

SES #: L16 · TOPICS: Greedy Algorithms, Minimum Spanning Trees · READINGS: Sections 16.1-16.3 and 22.1

SES #: L17 · TOPICS: Shortest Paths I: Properties, Dijkstra’s Algorithm, Breadth-first Search · READINGS: Section 22.2

SES #: R10 · TOPICS: Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths · READINGS: Sections 22.3-22.4

SES #: L19 · TOPICS: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson · READINGS: Chapter 25

SES #: L24 · TOPICS: Advanced Topics (cont.) · READINGS: Demaine, Erik D. “Cache-Oblivious Algorithms and Data Structures.” To appear in Lecture Notes from the EEF Summer School on Massive Data Sets , a volume of Lecture Notes in Computer Science . Berlin, Germany: Springer-Verlag.

Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms . Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296. The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.

———. Data Structures and Algorithms . Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237. Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.

Baase, Sara. Computer Algorithms: Introduction to Design and Analysis . 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353. General reference, although the exposition is sometimes terse or sketchy.

Bentley, Jon Louis. Programming Pearls . Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311. Applications of algorithm design techniques to software engineering.

———. More Programming Pearls: Confessions of a Coder . Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890. More applications of algorithm design techniques to software engineering.

———. Writing Efficient Programs . Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512. Performance hacking extraordinaire.

Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice . Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432. Good examples and problems. Focus on methods rather than specific problems.

Chung, Kai Lai. Elementary Probability Theory with Stochastic Processes . New York, NY: Springer-Verlag, 1974. ISBN: 0387900969. Intuitive introduction to probability.

Even, Shimon. Graph Algorithms . Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218. Broad treatment of graph algorithms, including network flow and planarity.

Feller, William. An Introduction to Probability Theory and Its Applications . 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095. Excellent reference for probability theory.

Garey, Michael R., and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness . San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447. Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.

Gonnet, Gaston H. Handbook of Algorithms and Data Structures . Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X. Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.

Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198. General treatment of algorithms that operate on character strings and sequences.

Horowitz, Ellis, and Sartaj Sahni. Fundamentals of Computer Algorithms . Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226. Good on data structures, dynamic programming, and branch-and-bound algorithms.

Kingston, Jeffrey H. Algorithms and Data Structures: Design, Correctness, Analysis . Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057. A nice introductory book on data structures, with a good chapter on algorithm correctness.

Knuth, Donald E. The Art of Computer Programming. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850. Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.

Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids . New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660. Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.

Liu, Chung L. Introduction to Combinatorial Mathematics . New York, NY: McGraw-Hill, 1968. ISBN: 0070381240. Combinatorial mathematics relevant to computer science. Excellent problems.

Manber, Udi. Introduction to Algorithms: A Creative Approach . Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372. Elementary text with an emphasis on creativity.

Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428. Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.

Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers . 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517. Readable introduction to number theory.

Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity . Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623. Linear programming and its variants.

Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipies in C: The Art of Scientific Computing . Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X. Code for numerical algorithms.

Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice . Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X. Good on recurrence relations and binary search trees.

Sedgewick, Robert. Algorithms . 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734. Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.

Sipser, Michael. Introduction to the Theory of Computation . Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X. A good text on computability and complexity theory.

Tarjan, Robert Endre. Data Structures and Network Algorithms . Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878. Advanced book with tons of good stuff.