Syllabus for 22C:196, Computational Combinatorics
Professor Sriram Pemmaraju
Class Room and Timing 105 MLH, 2:30-3:45 pm, TTh
Office and Office Hours 101G MLH, 3:45-4:45 pm, MT
E-mail and phone sriram@cs.uiowa.edu, 319-353-2596
Course page http://www.cs.uiowa.edu/~sriram/196/fall01/index.html
Grading 6 homeworks at 10% each, 1 exam at 20%, and 1 project at 20%
Prerequisites Grades C- or above in 22C:34 and 22C:44

Introduction

Combinatorics is the study of counting. Traditional Combinatorics involves deriving formulae for counting arrangements of one sort or another. Since the 70's, Combinatorics has expanded to include the notion of enumeration as well. We not only want to count, but we want to be able to list the objects being counted, as well. Combinatorial numbers are typically huge and so it is crucial that our procedures for enumeration be efficient. This is where algorithmic techniques from computer science become relevant.

Two questions are central to this course (a) how do we efficiently generate all members of some class of combinatorial objects? (b) how do we efficiently select an object uniformly at random from a class of combinatorial objects? For example, how do we efficiently generate all unlabeled binary trees or select an unlabeled binary tree uniformly at random? There are many applications of combinatorial generation, for example, to circuit testing, to theorem proving, to solving popular puzzles, and to statistical computation. There is a great beauty to the subject and many interesting and accessible problems remain open - these will be presented throughout the course.

Tools from discrete mathematics such as generating functions, elementary theory of finite groups, and Polya theory will be developed along with tools from algorithms such as backtracking, branch-and-bound, and dynamic programming. Using these tools we will study the enumeration and selection of combinatorial objects such as permutations, combinations, set partitions, integer partitions, free trees, binary trees, spanning trees, graph colorings etc.

Combinatorica

To understand concepts, test conjectures, and generally play around with, we will use the Mathematica based software package called Combinatorica. This package contains over 400 built-in functions to count, enumerate, and select combinatorial objects. Since the package is Mathematica based, we get the considerable power of Mathematica for free. Students will also be expected to develop some amount of competence in Mathematica programming and will use this to code algorithms not already in Combinatorica. To learn more about Combinatorica go here and to learn more about Mathematica go here.

List of Topics

Permutations 
	Lexicographic Permutations
		Generation
		Ranking and Unranking
	Random Permutation
	Mininum Change Permutations
		Johnson-Trotter Algorithm
		Ranking and Unranking
	
Cycle Structure of Permutations
	To and From Cycles
	Stirling Numbers of the First Kind
	Generating Permutations with k-cycles
		Hiding and Revealing Cycles
	Random Permutation with k-cycles

Subsets
	Lexicographic Subsets
		Generation
		Ranking and Unranking
	Gray Codes
	Hamiltonian Cycles in Graphs
	k-subsets
		Lexicographic k-subsets
			Generation
			Ranking and Unranking
		Gray Code k-subsets

Integer Partitions
	Reverse Lexicographic Ordered
		Generation
		Ranking and Unranking
	Random Partitions
	Counting Integer Partitions
	Gray Code Integer Partitions
	Introduction to Generating Functions
		Examples: Fibonacci Numbers, Coin Changing
		Applications of Generating Functions to Integer Partitions
	
Set Partitions
	Generating Set Partitions
	Stirling Numbers of the Second Kind and Bell Numbers
	Ranking, Unranking, and Random Set Partitions
	Restricted Growth Functions
		Bijection between Set Partitions and Restricted Growth Functions
		Generating, Ranking, and Unranking Restricted Growth Functions

Young Tableaux
	Young Tableaux and Involutions
		Insertion into and Deletion from a Tableaux
		Robinson-Schensted-Knuth Correspondence
		The Hook Formula
	Generating Young Tableaux
	Counting Tableaux by Shape
	Generating Random Tableaux

Trees
	Cayley's Theorem
	Prufer's Correspondence and Labeled Trees
	Generating Unlabeled Rooted Trees
	Generating Unlabeled Free Trees
	Random Unlabeled Trees
	Counting Spanning Trees of Graphs: Matrix Tree Theorem
	

Groups and Symmetry
	Elementary Theory of Permutation Groups
	Automorphism Groups of Graphs
	Vertex Transitive Graphs: Lovasz's Hamiltonian Cycle Conjecture
	Symmetries of other combinatorial objects: necklaces, polyhedra
	Simple Approaches to the Graph Isomorphism Problem
	Computing Certificates
		Tree Isomorphism
		Graph Isomorphism	

Polya Theory
	Cycle Index of Permutation Groups
	Burnside's Lemma
	Polya's Theorem: Proof
	Polya's Theorem: Applications
	Generating Random Graphs using Polya Theory

Books

Here is a list of books I have often referred to in learning this material. Most of the books are in the library and I own a copy of all of these books, except for the one by Nijenhuis and Wilf. I'll provide typed notes for the course as we go along. My hope is that these will be sufficient and you will not to read far beyond what I provide. If you do want additional reading material get a copy of East Side, West Side,..., the lecture notes provided by Herbert Wilf. If you do want to spend money on a book and want my recommendation from among the list below, Combinatorial Algorithms : An Update by Herbert Wilf would be my choice.

East Side, West Side...
Herbert S. Wilf, 1999

Introduction to Graph Theory
Douglas B. West
Prentice-Hall, 1996

Combinatorial Algorithms: Generation, Enumeration, and Search
Donald L. Kreher and Douglas R. Stinson
CRC Press, 1999

Concrete Mathematics : A Foundation for Computer Science
Ronald Graham, Oren Patashnik, Donald E. Knuth
Addison-Wesley, 1990

The Art of Computer Programming : Fundamental Algorithms
(Art of Computer Programming, Vol 1, 2nd Ed)
Donald E. Knuth
Addison-Wesley, 1999

The Art of Computer Programming : Sorting and Searching
(Art of Computer Programming, Vol 3, 2nd Ed)
Donald E. Knuth
Addison-Wesley, 1999

Constructive Combinatorics
Dennis Stanton and Dennis White
Springer-Verlag, 1986

Combinatorial Algorithms, 
Albert Nijenhuis and Herbert S. Wilf
Academic Press, 1978,

Combinatorial Algorithms : An Update 
Herbert S. Wilf
CBMS-NSF Regional Conference Series in Applied Mathematics, 1989

Miscellaneous Announcements: The University of Iowa Policies.

Sriram Pemmaraju
8/22/2001