| Logistics: | TTh 2:00 - 3:30 GDC 2.210 Unique Number: 50675 Course web page: http://www.cs.utexas.edu/~diz/388C |
|||||||||||||||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 471-9729 Office Hours: TTh 3:30 - 4:30 | |||||||||||||||||||||||||||||||||||||||
| TA: | Yan Zheng Email: yanzheng@utexas.edu Office (for office hours): TA Station (GDC 1.302), Desk 2 Office Hours: MW 5:00 - 6:00. |
|||||||||||||||||||||||||||||||||||||||
| Required Text: | Stasys Jukna, Extremal Combinatorics, with applications in computer science (2nd edition) | |||||||||||||||||||||||||||||||||||||||
| 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 L. Guth, Polynomial Methods in Combinatorics S. Vadhan, Pseudorandomness survey/monograph. J.H. van Lint and R.M. Wilson, A Course in Combinatorics |
|||||||||||||||||||||||||||||||||||||||
| 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, except I've added some time for Boolean functions and the recent resolution of the sensitivity conjecture.
A list of topics follows.
|
|||||||||||||||||||||||||||||||||||||||
| Prerequisites: |
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.
In particular,
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. |
|||||||||||||||||||||||||||||||||||||||
| Grading: | 50%: Homework 50%: Final exam |
|||||||||||||||||||||||||||||||||||||||
| Final Exam: | The final exam will be held on Wednesday, December 18 from 2:00 pm-5:00 pm. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). If you're taking the course pass/fail, then you do not need to take the final exam. Instead, I will count your homework grade as your final exam grade. | |||||||||||||||||||||||||||||||||||||||
| Homework policy: |
Collaboration policy:
While you should first think about the problems on your own,
you are encouraged to discuss the problems with your classmates.
Please limit your collaborations on any particular homework to
at most three other students.
Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed.
You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment.
You don't lose points by having collaborators.
Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do 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. You will get at most half credit for solutions found in the literature or on the web. Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted. | |||||||||||||||||||||||||||||||||||||||
| Canvas: | We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza. | |||||||||||||||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and only use them for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced. | |||||||||||||||||||||||||||||||||||||||
|
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. | |||||||||||||||||||||||||||||||||||||||
|
Additional Class Policies
|
This class will follow the standard policies described in the CS Department Code of Conduct. |