|Logistics:|| TTh 2:00 - 3:30
Unique Number: 50675
Course web page: http://www.cs.utexas.edu/~diz/388C
Office: GDC 4.508
Office Hours: TBD
|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 should be similar to the 2014 version of the course.|
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 13.1 of the text. Succinct review of the other topics above are available in the text in Sections 1.1 and 3.1. 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." Alternatively, you can read Chapters 1-3.4 of Avi Wigderson's book Mathematics and Computation.