| Logistics: | TTh 11-12:30 TAY 3.144 Unique Number: 56780 Course web page: http://www.cs.utexas.edu/~diz/388C |
||||||||||||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 Office Hours: WF 2:30-3:30, or by appointment. | ||||||||||||||||||||||||||||||||||||
| TA: | Xin Li Email: lixints@cs.utexas.edu Office (for office hours): ENS 31NQ Desk #1 Office (for all other purposes): TAY 3.108 Phone: 471-9520 Office Hours: M 2-3 |
||||||||||||||||||||||||||||||||||||
| Required Text: | Stasys Jukna, "Extremal Combinatorics, with applications in computer science" | ||||||||||||||||||||||||||||||||||||
| Optional Texts: |
N. Alon and J. H. Spencer,
"The Probabilistic Method"
(
ebook
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.
A list of topics follows.
|
||||||||||||||||||||||||||||||||||||
| Prerequisites: |
Graduate standing or consent of instructor.
Many students find this course difficult, so a strong math
background is highly recommended.
In particular,
a good 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 strong 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." |
||||||||||||||||||||||||||||||||||||
| Grading: | 30%: Homework 25%: Midterm 45%: Final exam |
||||||||||||||||||||||||||||||||||||
| Exams: | The midterm will be held in class on October 11. The final exam will be cumulative and held on Monday, December 17 from 9am-noon. No make-up exams will be given, so plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides); for the final you may bring two such sheets. No calculators are allowed (they won't be necessary). | ||||||||||||||||||||||||||||||||||||
| Homework policy: |
Collaboration policy: I encourage you to discuss homework
problems with your classmates.
However, you must write up your own solutions.
Furthermore, you must acknowledge any collaboration by writing the
names of your collaborators on the front page of the assignment.
Citation policy: If you use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. Submission policy: Homeworks are due at the beginning of class. Late homeworks should be submitted directly to the TA. Late policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late or two assignments one day late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours (so it begins and ends at 11am). However, an assignment due Thursday may be handed in Monday by 11am for two late days. | ||||||||||||||||||||||||||||||||||||
|
Students with Disabilites: |
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. |