CMP741 ADVANCED ALGORITHMS ANALYSIS I

SPRING 2019

INSTRUCTOR: Engin Demir

LECTURES: Monday 14:00-16:45 @ D5

COURSE DESCRIPTION: The design and analysis of algorithms is the core subject matter of Computer Science. Given a problem, we want to (a) find an algorithm to solve the problem, (b) prove that the algorithm solves the problem correctly, (c) prove that we cannot solve the problem any faster, and (d) implement the algorithm. Designing an algorithm for a computational problem involves knowledge of the problem domain, a thorough knowledge of the data structures that are available and suitable and no small measure of creativity. This course concentrates on the above problems, studying useful algorithmic design techniques, and methods for analyzing algorithms.

You are expected to have mastered the material presented in BBM201, BBM202, and BBM205.

TEXTBOOKS:

• Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd edition, The MIT Press, 2009. ISBN: 978-0-262-53305-8
• -Y. Kao (ed.), Encyclopedia of Algorithms, 2008. ISBN 978-0-387-30770-1
• Knuth, The Art of Computer Programming, all volumes.
• Miller, Bradley, and David Ranum. Problem Solving with Algorithms and Data Structures Using Python. 2nd ed. Franklin, Beedle & Associates, 2011.

Recommended Readings

• ACM Computing Reviews
• ACM Computing Surveys
• Algorithmica

Supplementary Course Videos:

• MIT OpenCourseWare 2011
• TUBA Open Course Notes (in Turkish) 2005

GRADING POLICY:

COMMUNICATION:

The course webpage will be updated regularly throughout the semester with lecture notes, programming and reading assignments and important deadlines. All other communications will be carried out through Piazza. Please enroll it by following the links http://www.piazza.com/hacettepe.edu.tr/spring2019/cmp741

POLICIES:

All work on assignments must be done individually unless stated otherwise. You are encouraged to discuss with your classmates about the given assignments, but these discussions should be carried out in an abstract way. That is, discussions related to a particular solution to a specific problem (either in actual code or in the pseudocode) will not be tolerated. In short, turning in someone else's work, in whole or in part, as your own will be considered as a violation of academic integrity. Please note that the former condition also holds for the material found on the web as everything on the web has been written by someone else.

CLASS SCHEDULE