|Logistics:|| TTh 2:00 - 3:30
Unique Number: 54000
Course web page: http://www.cs.utexas.edu/~diz/388C
Office: GDC 4.508
Office Hours: W 2:15-3:45.
Office (for office hours): GDC 1.302, Desk 1
Office (for all other purposes): GDC 4.504B
Office Hours: MF 10:00-10:45.
|Required Text:||Stasys Jukna, "Extremal Combinatorics, with applications in computer science" (2nd edition)|
N. Alon and J. H. Spencer,
"The Probabilistic Method"
available with UT EID)
L. Babai and P. Frankl, "Linear Algebra Methods in Combinatorics, with applications to geometry and computer science"
This graduate course is an introduction to combinatorics and
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 course should be similar to the
A list of topics follows.
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."
40%: Final exam
|Exams:||The midterm will be held in class on March 6. The final exam will be cumulative and held on Saturday, May 10 from 7-10pm in GDC 5.302. 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).|
While you should first think about homework problems on your own,
I encourage you to discuss the problems with your classmates.
However, you must write up your own solutions.
In particular, nobody should email partial or full solutions to
Furthermore, you must acknowledge any collaboration by writing the
names of your collaborators 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. 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 2pm). However, an assignment due Thursday may be handed in Monday by 11am for two late days.
|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.|
|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.|