Syllabus
Preliminary Examination
in Mathematical Computer Science
Combinatorics Cluster
This is one of four possible preliminary exams in computer science. Students
are requested to solve 5 out of 8 or 9 problems. Past exams should be
available from the Mathematics Library or the office of the Director of
Graduate Studies or the MCS web home page.
Questions are drawn from the following courses and their prerequisites.
MCS 521 Combinatorial Optimization: The course can cover different
topics each time it is offered from among the following. Network
optimization (shortest paths, maximum flows, minimum-cost flows,
matching problems), matroid theory (elementary properties, duality,
greedy algorithm, matroid sum and matroid intersection), polyhedral
combinatorics (theorems of the alternatives and linear programming
duality, faces, extreme points and facets of polyhedra, integral
polyhedra).
Texts:
E. L. Lawler, Combinatorial Optimization: Networks and Matroids,
Holt, Rinehart and Winston, 1976.
R. K. Ahuja, T. L. Magnanti and J. B.
Orlin, Network Flows, Prentice Hall, 1993.
G. Nemhauser and L. Wolsey,
Integer and Combinatorial Optimization, Wiley 1988.
MCS 531 Introduction to Error-Correcting Codes: Basic concepts in coding
such as weight distribution, covering radius, questions about minimum
distance, various families of codes such as greedy codes, self-dual
codes, perfect codes.
Text:
V. Pless, The Theory of Error-Correcting Codes, Wiley
Interscience, Second ed., 1989.
MCS 591 Advanced Topics in Combinatorial Theory:
The course can cover
different topics each time it is offered from among the following.
Graphs and trees, coloring of graphs and Ramsey theory, combinatorial
designs, systems of distinct representatives, Moebius inversion,
Stirling and Gaussian numbers, recursions and generating functions, Polya
theory of counting, Dilworth theorem and extremal set theory.
Texts:
J. H. Van Lint and R. M. Wilson: A Course in Combinatorics,
Cambridge University Press, 1992.
R. A. Brualdi, Introductory
Combinatorics, Second ed., Prentice Hall, 1992.