CS 6310 (Spring 2019)


Advanced Design and Analysis of Algorithms


[ courses ] [ syllabus ] [ class policy ] [ references ] [ projects ] [ assignments ]


Dr. Elise de Doncker
Department of Computer Science
College of Engineering and Applied Sciences
B-240 Parkview Campus
Kalamazoo, MI-49008

Phone: (269) 276-3102 (office), 276-3101 (Dept. office) 276-3122 (fax)
(but preferably contact me by e-mail: elise [dot] dedoncker [at] wmich [dot] edu)

Office hours (tentative) MW : 13:00 - 14:00 (please let me know if you plan on coming; other times by appointment)
TA: MW 14:30-1600 (Tasnim Gharaibeh):
tasnim [dot] gharaibeh [at] wmich [dot] edu


  • Recommended:
    • (Required) Algorithms and Complexity, Herbert S. Wilf, Online edition: https://www.math.upenn.edu/~wilf/AlgoComp.pdf
    • Foundations of Algorithms, Richard E. Neapolitan, 5th edition, Jones & Bartlett Learning (ISBN-13: 978-1-284-04919-0, ISBN-10: 1284049191), http://www.amazon.com/Foundations-Of-Algorithms-Richard-Neapolitan/dp/1284049191
    • The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys, Cambridge University Press, 2011 (ISBN: 978-0-521-19527-0 (hbk))
    • Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 2000 (ISBN: 0-521-47465-5 (hbk))
    • Complexity Theory, Exploring the Limits of Efficient Algorithms, Ingo Wegener, Springer-Verlag 2003 (ISBN-13: 978-3-540-21045-0, ISBN-10: 3-540-21045-8)
    • Computers and Intractability, A Guide to the Theory of NP-Completeness, Michael R. Garey and David S. Johnson, W. H. Freeman and Company (ISBN: 0-7167-1044-7, 0-7167-1045-5 (pbk))
    • Advanced Data Structures, Peter Brass, 1st edition, Cambridge University Press (ISBN-13: 978-0521880374, ISBN-10: 0521880378), http://www.amazon.com/Advanced-Data-Structures-Peter-Brass/dp/0521880378
  • Reference texts:
    • (Required) Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, (3rd edition), Mc Graw Hill (ISBN-13: 9780262033848/hardcover, ISBN-13: 9780262533058/softcover),
    • Algorithmics: Theory & Practice, Gilles Brassard and Paul Bratley, Prentice Hall (ISBN-10: 0-13-340761-6)
    • Algorithms from P to NP, Volume I: Design and Efficiency Bernard M.D. Moret and Henry D. Shapiro, The Benamin/Cummings Publishing Company, Inc. (ISBN: 0-8053-8008-6)
    • Fundamentals of Data Structures in C++, Ellis Horowitz, Sartaj Sahni and Dinesh Mehta, 2nd Edition (ISBN 13:9780929306377); 1st Edition (ISBN-10 0-7167-8292-8)

Catalog description
This course introduces students to advanced concepts for designing and analyzing algorithms. The effect of data structures on program design is investigated. The uses of data structures and algorithms in a variety of application areas are covered. Focus is on algorithmic thinking, performance guarantees and boundary cases, and efficient solutions to practical problems. Advanced topics will cover a selection of modern algorithms, many of which come from real-world applications.

The following scale will be used to determine your final grade on the basis of your final average:
A:    92.0 - 100.0, BA: 88.0 -  91.9, B:    82.0 -  87.9, CB: 78.0 -  81.9, C:    72.0 -  77.9, DC: 68.0 -  71.9, D:    60.0 -  67.9, E:    below  60.0

Academic Integrity Policies
You are responsible for making yourself aware of and for understanding the policies and procedures in the Undergraduate Catalog (pp. 271-272) that pertain to Academic Integrity. These policies include cheating, fabrication, falsification and forgery, multiple submission, plagiarism, complicity and computer misuse. If there is reason to believe you have been involve in academic dishonesty, you will be referred to the Office of Student Judicial Affairs. You will be given the opportunity to review the charge(s). If you believe you are not responsible, you will have the opportunity for a hearing. You should consult with me if you are uncertain about an issue of academic honesty prior to the submission of an assignment or test.

Additional instructor's notes regarding homework:

  • No content downloaded from the internet may be used.
  • Cooperating on the homework among students is not allowed.
If you do not comply there will be consequences.

[ courses ] [ syllabus ] [ class policy ] [ references ] [ projects ] [ assignments ]