Combinatorics with computer science applications, UvA course code MOLCCSA6

Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistant: Giannicola Scarpa (CWI)

Contents of the course:

This course provides an applied introduction to combinatorics. Combinatorics is the art of counting and analyzing discrete structures with various properties, such as graphs, systems of sets, matrices, algorithms, etc. It is the main branch of mathematics that one uses in theoretical computer science and related fields, and is full of beautiful techniques and results. Among the applications, we will describe a number of interesting and efficient algorithms, and analyze the limitations of computational systems such as Boolean circuits. The course will be self-contained, though some prior familiarity with discrete mathematics, probability theory, linear algebra, and computational complexity theory will be helpful.

Textbook:

We will cover selected chapters from this book, at a pace of about one chapter a week. Combinatorics is broad rather than deep, which allows us to deal with a new topic each week in a reasonably self-contained way.

Homework, exam, and grading:

This is a 6 ECTS course, which comes to roughly 10 hours of work per week. There will be homework exercises every week, to be handed in before or at the start of the next lecture. The answers should be in English. You can hand it in on paper, or email a readable file to Giannicola (G.Scarpa at cwi dot nl, with cc to rdewolf at cwi dot nl). Cooperation is allowed, but everyone has to hand in their own solution set in their own words. Each homework set will get a grade between 1 and 10; if you don't hand it in you'll score a 1 for that week. When determining the average grade for the homework we will ignore your two lowest scores. This is supposed to handle also all cases of illness, forgetfulness etc, so it's pointless to ask for exceptions or special treatment when you're late. There will be a midterm exam on March 29, covering the first 7 lectures. For the final exam (May 30), you can choose to do a version on the second half of the course or a version on the whole course. Use the latter if you missed the midterm or didn't like your midterm grade. Both exams are open book, meaning you can bring the book and whatever notes you have, but no electronic devices. The overall grade will be determined 50-25-25 by the homework, the midterm exam, and the final exam; or 50-50 by the homework and the final exam in case you chose to do the version of the final exam that covered the whole course.

Preliminary course schedule:

February 9 - May 24, 2012, Thursdays 15.00-19.00 (though we'll often stop around 18.00). No lecture on May 17.
Location: Science Park A1.08
  1. [Feb 9] Introduction and some basic counting techniques
    Book: Preface/Notation. Chapter 1.1, 1.4, 4.3
    Homework: Exercises 1.2, 1.5, 1.9, 1.10, 1.14, 1.15
  2. [Feb 16] More advanced counting
    Book: Chapter 1.2, 1.6, 2.6 [NB: equation 2.7 should be in the other direction]
    Homework: Exercises 1.13, 1.21, 1.32, 1.33, 1.36, 2.1
  3. [Feb 23] The pigeonhole principle
    Book: Chapter 4.1, 4.2, 4.4, and the lower bound for resolution
    Homework: Exercises 4.1, 4.4, 4.5, 4.7, 4.11, 4.20
  4. [Mar 1] Systems of distinct representatives and algorithms for matching
    Book: Chapter 5, except 5.2.1
    Homework: Exercises 5.1, 5.4, 5.6, 5.8, 5.9, 5.10
  5. [Mar 8] Sunflowers
    Book: Chapter 6.1, 6.2.2, 6.3.2
    Homework: Exercises 6.2, 6.3, 6.6, 6.8, 6.11, 6.12
  6. [Mar 15] Chains and antichains
    Book: Chapter 8.1, 8.3, 8.6, and Sections 1 and 2 of this application to data structures
    Homework: Exercises 8.1, 8.4, 8.5, 8.6, 8.8, 8.10
  7. [Mar 22] Blocking sets
    Book: Chapter 9.1, 9.2, 9.4
    Homework: Exercises 9.2, 9.6, 9.7, 9.8, 9.9 [insert "at least" after "depth"]

    [Mar 29] midterm exam 13.00-16.00 in G2.13 [NB: different time and room than the lectures]

  8. [Apr 5] The linear algebra method
    Book: Chapter 13.1, 13.3, 13.6
    Homework: Exercises 13.1, 13.9, 13.10, 13.17 [page 196, line 4: the mu_j indices should be mu_{I_j}, and order the |I_j| from small to large], 13.18
  9. [Apr 12] The probabilistic method I
    Book: Chapter 3.1, 3.2, 3.3, 18.1, 18.7
    Homework: Exercises 3.1, 3.6, 3.10, 3.11, 18.14 [assume here that k>3]
  10. [Apr 19] The probabilistic method II
    Book: Chapter 18.11, 21.1, 21.5, and Section 3 of this application to data structures
    Homework: Exercises 3.3, 3.5, 18.9, 18.11, 21.8, 21.9
  11. [Apr 26] Randomized algorithms, random walks
    Book: Chapter 16.1 and 23.1
    Homework: Exercises 16.2, 16.3, 16.4, 16.6, 16.7 [read "How large must N be" as "How large an N suffices"; ignore the last 4 words of the hint]
  12. [May 3] Expander graphs
    Book: Chapter 15.1, 15.2 and 23.3
    Homework: Exercises 15.1, 15.2, 15.4, 15.5 [additonal hint: write the trace of A^2 in two different ways], 15.6 [if you use Ex 13.21 here, so you should prove that too]
  13. [May 10] Information theory
    Book: Chapter 22
    Homework: Exercises 22.2, 22.3, 22.4, 22.5, 22.6, 22.8, 22.9

    [May 17] no class

  14. [May 24] Communication complexity
    Book: this introduction to communication complexity
    No homework, but probably one exam-question will be about communication complexity

    [May 30] final exam 13.00-16.00 in G4.15 [NB: different day, time, and room than the lectures]
Last update of this page: May 24, 2012.