SF2715 Applied Combinatorics 6.0 hp, vt11

SF2715 Tillämpad kombinatorik 6,0 hp, vt11
URL: http://www.math.kth.se/math/GRU/2010.2011/SF2715/

Course start: March 23, 8.15 in room D41.
Location: See schedule
Examiner: Svante Linusson, 08-790 9444, epost:linusson (followed by the usual sign and then) math.kth.se
Level: Advanced level.(C)

Solutions to the exam on Aug 17, 2011

The solutions to the exam on Aug 17, 2011. Observe that the examiner for this particular exam is Jakob Jonsson (jakobj@kth.se).

The exam is graded, and you can get the exam back from the student office at the Math department. Grades were assigned according to the following table.

Grade A B C D E Fx
Number of points
(including bonus points)		 ≥21 18-20 16-17 14-15 11-13 10

Solutions to the exam on May 25, 2011

The solutions to the exam on May 25, 2011.
The exam is graded and you can get the exam back from the students office at the Math department. Next exam will be on August 17.

Course description

The course will cover several topics of modern combinatorics. One important question is how many are there of a certain object? We will learn techniques, such as recursions, power series and tools from algebra, to answer this question. Important objects will be permutations and partitions. We will also study some applications of graph theory, in particular flows in networks. An other interesting area is error correcting codes, where we will learn som of the basic theory. Finally we will also discuss some mathematics of voting procedures.

Förkunskapskrav (prerequisites)

Diskret Matematik SF1630 or SF1631 or SF2714 or SF2736 or the equivalent.

Lecture Plan

Preliminär kursplanering.

Exam

The final exam will be on Wednesday May 25. Please make sure to register for the exam between April 18 and May 8. There will be three handin problem sets that you can do to get bonus points on the exam. The due dates for these three sets of hand-in problems will be: April 7, April 29 and May 17 respectively. The problem sets will be available here a few days before due date.
First set of Hand-in problems.
Second set of Hand-in problems. The problems are due before class April 29.
Third set of Hand-in problems. The problems are due before class May 17.

Old Exams.

Here is a list of old exams. They are all in Swedish (ask me if you don't understand).
The Exams below illustrate well the level of difficulty you can expect from the exam.
Remember that the course has changed slightly. Therefore I ask you to ignore some problems.
There are also areas that are not covered in these old exams, in particular parts of the handouts called HHM1, HHM2, W, G1, AE and valmatematik.
January 2010. Ignore problem 5. Suggested solutions.
August 2009, solutions included. Ignore problem 5 and 7.
May 2009. Ignore problem 4. (The heading 7,5hp is wrong.) Suggested solutions.
Modeltenta 2009, solutions included. Ignore problem 7.
VT 2007, solutions included. Ignore problem 2. In problem 7 pretend that the the triangular shaped hole cannot be rotated in itself. Problem 8 is probably very difficult to solve if you have not seen this before.
May 2007, solutions included. Ignore problem 1 and 5.

Literature

Combinatorics: Topics, Techniques, Algorithms, by Peter J. Cameron, Cambridge University press.
There will also be occasional handouts with supplementary material and exercises.
The first handout: Notes 1. The exercises again with Solutions (in Swedish).
The second handout: Notes 2. The exercises again with Solutions (in Swedish).
The third handout: Notes 3. The exercises again with Solutions (in Swedish).
The fourth handout: Notes 4. The exercises again with Solutions (in Swedish).
The fifth handout: Notes 5.The exercises again with Solutions (in Swedish).

The slides I used in class for mathematics of elections.
To get the handouts called HHM1, HHM2, W, G1 and AE, please come to class.

Last changed May 25, 2011.