| Logistics: | MW 2:00 - 3:30,
GDC 1.406 (in person only) Unique Number: 52530 Course web page: http://www.cs.utexas.edu/~diz/388C |
|||||||||||||||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 512-471-9729 Office Hours: MTh 3:30 - 4:30 | |||||||||||||||||||||||||||||||||||||||
| TA: |
Vinayak Kumar Email: vmkumar@utexas.edu Office Hours: TuF 3:30 - 4:30 in GDC 1.302, Desk 5. |
|||||||||||||||||||||||||||||||||||||||
| 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 Y. Zhao, Graph Theory and Additive Combinatorics Videos of my lectures on Extractors and Expanders at the Simons Pseudorandomness Boot Camp. |
|||||||||||||||||||||||||||||||||||||||
| 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.
Often our objects of interest will be pseudorandom,
in the sense that they are fixed, deterministic objects with random-like properties.
A related theme will be the interplay between structure and randomness.
This course should be similar to the 2019 version
of the course.
A tentative 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. See also Section 3.1 of the text.
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
Familiarity with finite fields is extremely useful. We will also use some elementary linear algebra, succinctly reviewed in Section 13.1 of the text. 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 Saturday, April 29, from 1:00 pm - 3:00 pm in RLP 1.104. 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 credit/NC and scored at least 60% on the homework, then you can pass the course without taking the final exam. | |||||||||||||||||||||||||||||||||||||||
| 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: 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. The weekend doesn't count, so Friday to Monday counts as one day. I may not allow late days for certain assignments. | |||||||||||||||||||||||||||||||||||||||
| Canvas: | We will use Canvas, which contains Ed Discussion. Homeworks and grades will be posted on Canvas. We will use Ed Discussion for class discussion. Instead of emailing questions to the teaching staff, please post your question to Ed Discussion. | |||||||||||||||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited, but I will allow the use of tablets if you use them only for class-related purposes. 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. |