Algorithms
and Complexity
Razvan Andonie
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,
Preiss, B.R. Data
Structures and Algorithms with Object-Oriented Design Patterns in C++,
John Wiley & Sons,
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,
Brassard, G., Bratley, P. Algorithmics
- Theory and Practice. Prentice-Hall,
Cormen, T.H., Leiserson, C.E., Rivest,
R.L. Introduction to Algorithms. The MIT Press,
Horowitz, E., Sahni, S. Fundamentals
of Computer Algorithms. Computer Science Press,
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,
Weiss M.A. Data Structures &
Algorithms in Java, Addison-Wesley,
Baase S. Computer algorithms -
Introduction to Design and Analysis, Addison-Wesley,
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