 |
|
|
SEMINAR IN ALGORITHMIC COMBINATORICS |
||
|
|
|
|
|
|
From 1970 to 1990 I ran a graduate seminar on algebraic and algorithmic combinatorics in the Department of Mathematics, UCSD. From 1972 to 1990 algorithmic combinatorics became the principal topic. The seminar notes from 1970 to 1985 were combined and published as a book, Combinatorics for Computer Science (CCS), published by Computer Science Press. Each of the "units of study" from the seminar became a chapter in this book. SELECTED UNITS contains the most basic units of study from CCS in workbook form and also as free pdf files - each with its own index. ALL CHAPTERS contains all of the material in CCS broken down into chapters, references and index (Creative Common CC0 1.0). |
||
|
|
|
|
|
|
The units with covers shown below contain the most basic ideas useful for programming problems of a combinatorial nature. Unit 1 (methods for linearly ordering complex sets) is the most basic. Unit 2 (sorting and listing) is next. Unit 6 (graph algorithms) gives the intuition and formal understanding for programming graph algorithms. Unit 4 developes techniques for dealing with symmetries in combinatorial algorithms. The workbooks shown below are sturdy and designed with wide margins for taking notes with pen or pencil for a break from sitting at the computer. They are inexpensive and available at Amazon Books. Below each cover image is a link to the same material as a free pdf file. This stuff is great fun! |
||
|
|
|
 |
 |
 |
 |
|||||
|
|
|
|
|
|
|
|
|
| UNIT 1 PDF | UNITS 2-3 PDF | UNIT 4 PDF | UNIT 6-7 PDF | |||||
|
|
|
|
|
|
|
|
|
Free PDF |
Free PDF |
Free PDF |
Free PDF |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
The material in CCS is divided 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 free (Creative Commons) and 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. |
||
|
|
|
Used Dover Edition |
||||||||||||||||
Contents, Preface, Study Guide pdf |
||||||||||||||||
The book, Combinatorics for Computer Science, contains the topics in this seminar. |
||||||||||||||||
 |
||||||||||||||||
 |
||||||||||||||||
Comprehensive Index pdf |
||||||||||||||||
PART I: Linear Order |
||||||||||||||||
References Part I pdf |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chapter 1-- Basic Concepts of Linear Order |
||
|
|
|
 |
||
|
|
|
Chapter 2 -- TOPIC I: Sorting pdf |
||
|
|
|
 |
||
|
|
|
Chapter 3 -- TOPIC II: Basic Combinatorial Lists pdf |
||
|
|
|
 |
||
|
|
|
Chapter 4 -- TOPIC III: Symmetry - Orbit Enumeration and Orderly Algorithms pdf |
||
|
|
|
 |
||
|
|
|
Chapter 5 -- Some Classical Combinatorics pdf |
||
|
|
|
 |
||
|
|
|
PART II: Graphs, Trees and Recursion |
||
|
|
|
References Part II pdf |
||
|
|
|
Chapter 6 -- Basic Concepts of Graphs, Trees and Recursion pdf |
||
|
|
|
 |
||
|
|
|
Chapter 7 -- TOPIC I: Depth First Search and Planarity pdf |
||
|
|
|
 |
||
|
|
|
Chapter 8 -- TOPIC II: Depth First Search and Nonplanarity pdf |
||
|
|
|
 |
||
|
|
|
Chapter 9 -- TOPIC III: Triconnectivity pdf |
||
|
|
|
 |
||
|
|
|
Chapter 10 -- TOPIC IV: Matroids pdf |
||
|
|
|
 |
||
|
|
|
|
|
|
|
|
|