|
This material was developed over a ten year period (1975-85) from a graduate seminar in algorithmic combinatorics given by the author in the Department of Mathematics, University of California, San Diego. We have divided the material into two parts. Part I consists of an introductory Chapter 1, Basic Concepts of Linear Order, followed by four topic areas: Chapter 2, Sorting; Chapter 3, Basic Combinatorial Lists; Chapter 4, Orbit Enumeration and Orderly Algorithms; and Chapter 5, Some Classical Combinatorics. Part II consists of an introductory Chapter 6, Basic Concepts in Graphs, Trees and Recursion, followed by four topic areas: Chapter 7, Depth First Search and Planarity; Chapter 8, Depth First Search and Nonplanarity; Chapter 9. Triconnectivity; and Chapter 10, Matroids. All chapters are downloadable in pdf format. In addition, there is a comprehensive table of contents and index. Using this index, one may pick and choose between these various chapters, ordering their presentation in many ways. References used at the time of the seminar are given for both Part I and Part II. For current references, search for the various topics in Google or your preferred search engine.
Chapters 1 and 6 present material important for students of modern computer science or combinatorial mathematics. Chapters 2 and 3 are slightly more specialized but will be of value to any student interested in the design of useful algorithms. The geometric approach we develop in these chapters for visualizing what algorithms actually do is especially useful. Chapter 4 is next in contemporary importance as it discusses how to make use of symmetry in designing algorithms. Chapter 5 may repeat material seen by graduate students in other courses -- skim it to look for new ideas. Finally, Chapters 7, 8, and 9 are very specialized, but they solve some hard problems using our methods. Chapter 9 presents the theory of matroids in terms of representable matroids, developing the student's intuition by using familiar ideas from matrix theory.
|
|
