Algorithms and Complexity

Razvan Andonie

Honorius Galmeanu

Overview:

Topics will include basic algorithmic analysis, algorithmic strategies, fundamental computing algorithms, basic computability, the complexity classes P and NP, and advanced algorithmic analysis. The course promotes object-oriented design and illustrates the use of design patterns. Virtually all data structures are discussed in the context of a single class hierarchy. This framework clearly shows the relationships between structures and illustrates how polymorphism and inheritence can be used effectively.

Design patterns have recently emerged as a vehicle for describing and documenting recurring object-oriented design. More significantly, they offer up a long-awaited framework for teaching good software design. The benefits of using object-oriented methodologies and, in particular, of design patterns are profound. It does not make sense to save them for advanced courses. What are the pedagogic benefits? Design patterns are emerging as the abstraction that are appropriate for talking about design. They provide a framework for thinking about and for comparing design decisions and trade-offs. More importantely, they provide a common vocabulary for describing software design.

Contents:

*      Preliminaries (2 hours)

*      Elementary Data Structures (4 hours)

*      Efficiency Analysis of Algorithms (6 hours)

*      Greedy Algorithms (6 hours)

*      Divide and Conquer (6 hours)

*      Dynamic Programming (6 hours)

*      Exploring Graphs (6 hours)

*      String-Searching Algorithms (4 hours)

*      Probabilistic Algorithms (4 hours)

*      Introduction to NP-Completeness (4 hours)

The seminar will mainly focus on object-oriented implementation of data structures and algorithms, including:

*      Abstract Data Types

*      Design Patterns (Containers, Iterators, Visitors, Adapters, Singletons)

*      Algorithmic Patterns and Problem Solvers

You will learn the latest object-oriented design patterns needed to create sound software design.

Prerequisites:

*      Discrete Mathematics

*      Object-Oriented Programming

Bibliography:

Essential reading:

*      Andonie, R., Garbacea, I. Algoritmi fundamentali; o perspectiva C++. Editura Libris, Cluj-Napoca, 1995. This is the basic textbook. You can download the html and pdf versions, and the source code.

*      Preiss, B.R. Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, New York, 1999. This is the additional textbook for the seminar & lab. You can download the html version and the source code.

*      Andonie, R. Other Chapters (notes in Romanian): String Searching and NP-Completeness. Can be downloaded as PDF file.

Additional reading:

*      Brassard, G., Bratley, P. Fundamentals of Algorithmics. Prentice-Hall, Englewood Cliffs, 1996.

*      Brassard, G., Bratley, P. Algorithmics - Theory and Practice. Prentice-Hall, Englewood Cliffs, 1988.

*      Cormen, T.H., Leiserson, C.E., Rivest, R.L. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1992 (eighth printing).

*      Horowitz, E., Sahni, S. Fundamentals of Computer Algorithms. Computer Science Press, Rockville, 1978.

*      Knuth, D.E. The Art of Computer Programming, Vol 1-3, Addison-Wesley, 1977-1988.

*      Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns - Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, Massachusetts, 1995.

*      Sahni S. Data Structures, Algorithms, and Applications in C++, Mc Graw Hill, Boston, 1998.

*      Weiss M.A. Data Structures & Algorithms in Java, Addison-Wesley, Reading, Massachusetts, 1999.

*      Baase S. Computer algorithms - Introduction to Design and Analysis, Addison-Wesley, Reading, Massachusetts, 2000 (Third Edition).

*      Horiwitz E., Sahni S., Ranjasekaran S. Computer Algorithms C++, Computer Science Press, New York, 1997.

*      Bornemann, F. PRIMES Is in P: A Breakthrough for “Everyman”. Notices of the AMS, May 2003, 545-552. Three Indian mathematicians (Agrawal, Kayal, and Saxena) have presented in August 2002 a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite. The article is about this amazing result.

Links:

*      A Compendium of NP Optimization Problems

*      Open Problems in Combinatorial Optimization

*      Courses on WWW