Catalog Description: Introduction to graph theory and combinatorial analysis. The emphasis is on solving applied problems rather than on theorems and proofs. Techniques used in problem solving will include generating functions, recurrence relations, and network flows. This course develops the type of mathematical thinking that is fundamental to computer science and operations research.
Prerequisites: AMS 210 or MAT 210 or AMS 361 or MAT303.
3 credits
Text: Applied Combinatorics, by Alan Tucker, 5th edition, John Wiley & Sons
Fall 2009 Sections
92693 LEC 01 TUTH 11:20-12:40PM Loc: Physics P118 Inst: Alan Tucker AMS 301.1 Webpage
92691 LEC 03 MW 02:20-03:40PM Loc: Physics P118 Inst: Estie Arkin
Spring 2010 Sections
52488 LEC 01 MWF 09:35-10:30PM Loc: SB Union 123 Inst: Ning Sun
52489 LEC 02 TUTH 03:50-05:10PM Loc: Physics P118 Inst: Estie Arkin
AMS 301 IS ALSO OFFERED DURING SUMMER SCHOOL. CHECK THE SUMMER SCHOOL BULLETIN FOR TIMES.
Topics
1. Basic concepts of graphs, graph models and isomorphism - 4 class hours.
2. Euler and Hamilton circuits and their applications - 3 class hours.
3. Graph coloring and its applications - 3 class hours.
4. Trees, their use in searching - 5 class hours.
5. Problems with permutations and combinations - 8 class hours.
6. Generation Functions - 5 class hours.
7. Recurrence Relations - 4 class hours.
8. Inclusion-Exclusion principle - 5 class hours
9. Examinations and Review – 5 class hours.