TOP

SEMINAR IN ALGORITHMIC COMBINATORICS

S. Gill Williamson

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

SELECTED UNITS

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!

Unit1Cov Unit23Cov Unit4Cov Unit67Cov
UNIT 1 PDF UNITS 2-3 PDF UNIT 4 PDF UNIT 6-7 PDF

Free PDF

Free PDF

Free PDF

Free PDF

ALL CHAPTERS

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

Creative Commons

Contents, Preface, Study Guide pdf

The book, Combinatorics for Computer Science, contains the topics in this seminar.

CCS
GraphicCCS

Comprehensive Index pdf

PART I: Linear Order

CCS Book 536 pp

References Part I pdf

Chapter 1-- Basic Concepts of Linear Order

Fig113

Chapter 2 -- TOPIC I: Sorting pdf

Fig271

Chapter 3 -- TOPIC II: Basic Combinatorial Lists pdf

Fig378

Chapter 4 -- TOPIC III: Symmetry - Orbit Enumeration and Orderly Algorithms pdf

Fig4140

Chapter 5 -- Some Classical Combinatorics pdf

Fig5208

PART II: Graphs, Trees and Recursion

References Part II pdf

Chapter 6 -- Basic Concepts of Graphs, Trees and Recursion pdf

Fig6274

Chapter 7 -- TOPIC I: Depth First Search and Planarity pdf

Fig7305

Chapter 8 -- TOPIC II: Depth First Search and Nonplanarity pdf

Fig8319

Chapter 9 -- TOPIC III: Triconnectivity pdf

Fig9327

Chapter 10 -- TOPIC IV: Matroids pdf

FIG10369

TO TOP