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.
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.
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.
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.