| 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.
"I need to hear from anyone who has a disability which may require some modification of seating, testing, or other class requirements so that appropriate arrangements may be made. Please see me after class or during my office hours."