| Logistics: | TTh 11-12:30 TAY 3.144 Unique Number: 54225 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: W 3-4 and F 4-5, or by appointment. | |||||||||||||||||||||||||||||||||||||||
| TA: | Anup Rao Email: arao@cs.utexas.edu Office (for office hours): ESB 229, Desk 1 Office (for all other purposes): TAY 5.104 Phone: 471-9572 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"
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, and CS 336 or consent of instructor. An understanding of elementary proof techniques, as well as basic counting, probability, and linear algebra, is assumed. Students can brush up by reviewing Sections 1.1, 17.1, 17.2, and 14.1. Students outside of computer science should be familiar with the notion of polynomial-time computability, e.g. by reading Section 1.1 of Papadimitriou, "Computational Complexity." Many students find this course difficult, so a strong math background is highly recommended. | |||||||||||||||||||||||||||||||||||||||
| Grading: | 25%: Homework 30%: Midterm 45%: Final exam |
|||||||||||||||||||||||||||||||||||||||
| Exams: | The midterm will be held in class on October 25. The final exam will be cumulative and held on Saturday, December 17 from 7-10pm. 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 3:30pm). | |||||||||||||||||||||||||||||||||||||||
|
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. |