|Logistics:|| TTh 2:00 - 3:30
Unique Number: 54000
Course web page: http://www.cs.utexas.edu/~diz/388C
Office: GDC 4.508
Office Hours: TBD.
|Required Text:||Stasys Jukna, "Extremal Combinatorics, with applications in computer science" (2nd edition)|
N. Alon and J. H. Spencer,
"The Probabilistic Method"
available with UT EID)
L. Babai and P. Frankl, "Linear Algebra Methods in Combinatorics, with applications to geometry and computer science"
|Content:||This graduate course is an introduction to combinatorics and graph theory. We will survey a variety of topics, emphasizing those methods relevant to computer science. One underlying theme will be that it is often not hard to use the probabilistic method to show the existence of useful combinatorial objects; we will have to work harder to give efficient deterministic constructions of these objects. This course should be similar to the 2007 version.|
Graduate standing or consent of instructor.
Many students find this course difficult, so a first-rate math
background is highly recommended.
See the Review Sheet for material you're
expected to know.
a strong knowledge of elementary probability is essential.
For students wishing to review probability, I recommend the first
two chapters (except Section 2.6) of
R. Meester, A Natural Introduction to Probability Theory.
Equally important are problem-solving skills, an understanding of elementary proof techniques, and knowledge of basic counting. For general problem-solving and proof techniques, I recommend Chapters 2 and 3 of
P. Zeitz, The Art and Craft of Problem Solving,
and for basic counting I recommend Sections 6.1 and 6.2 of the same book. Finally, we will use some elementary linear algebra. This is succinctly reviewed in Section 14.1 of the text. Succinct review of the other topics above are available in the text in Sections 1.1, 17.1, and 17.2. Students outside of computer science should be familiar with the notion of polynomial-time computability, e.g., by reading Section 1.1 of C. Papadimitriou, "Computational Complexity."
|Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.|