SF2736 Discrete Matematics 7.5 credits, autumn 2015

URL: http://www.math.kth.se/math/GRU/2015.2016/SF2736/

Course responsible: Bengt Ek, 08-790 6951, bek@math.kth.se
Start: Monday 2 November 2015 at 10.15 in room M33.

The information on this page will be updated regularly.

News

The exam on April 5, 2018
The exam and suggested solutions can now be found down here.
Sorry they were late.
Your results should now be available on "Mina sidor" and the exams have been or will soon be scanned.
An error (hopefully obvious) found its way into the statement of problem 2 (corrected in the file below). Both A and B should be subsets of X. That made problems b and c simpler, but mostly the question seems to have been interpreted as it was intended. The mistake in the formulation was taken into account when points were given.
The exam on January 11, 2018
The exam and suggested solutions can now be found down here.
Sorry the solutions were late in appearing.
Your results should now be available on "Mina sidor" and the exams have been or will soon be scanned.
The exam on April 12, 2017
The exam and suggested solutions can now be found down here.
Sorry the solutions were so late in appearing.
The exam on January 12, 2017
The exam and suggested solutions can be found down here.
New! chance to obtain bonus for the exam
As stated in the next post, bonus from last year may be used for the exams this year (i.e. January and April 2017), but those who wish may also make use of this year's homework assignments (for SF1679) instead.
The rule will be that if you hand in a set of homework for course SF1679 (this year's course) all your bonus from last year, for both homework sets, disappear (so you can not change your mind and use last year's bonus instead).
The new assignments can be found here (pdf) (in Swedish; if you need a translation, please contact the teacher (Bengt) or ask someone to help).
No SF2736 autumn 2016
This course will not be given next year (and probably not later either).
There will be a new course, SF1679 Diskret matematik, with the same teacher and mostly the same contents, but it will be given in Swedish.
Exams for SF2736 will be given (twice every year) for the three coming years and bonus earned during autumn 2015 will be valid also (at least) for the two exams in 2016-17.
The exam on March 16
The exam and suggested solutions can be found down here.
Your results should be available on "Mina sidor" and the exams have been or will soon be scanned.
Course analysis
It is no longer possible to answer the questionnaire about the course. Thanks to all of you who did answer!
Here there is now a course analysis. In it you can also find the answers to the questionnaire.
The exam on 13 January
The exam and suggested solutions can now be found down here.
The marks have now (at last) been decided.
Your results should already or very soon be available on "Mina sidor" and the exams will soon be scanned.
Where is the exam?
The rooms for exams can be found here.
Our exam on 13 Jan will be in Q21 and Q22.
Concerning the exam
Since some (well, quite some) of the extra written material has still not appeared, there will be no problems on the exam on other things than what is covered in our sections of Biggs or in material that has appeared (summaries of lectures 1-4, 6, and 20, the Chinese remainder theorem, RSA and primality tests, induction and recursion, (planarity only what is in the summary of lecture 20)).
Further material (including summaries of lectures) will be posted later, also after the exam in January.
New appearances
There are now answers for all problem sessions and for both sets of homework.
They can be found here: problem sessions and homework.
Appearances
The summary of the lecture on graph colourings and planar graphs has appeared and so have answers for problem session 5.
They can be found here.
Homework set number 2 has appeared
The problems can be found here.
Application to participate in the exam in January
Note that to participate in exams, you must apply for it. Otherwise there is a risk that there is no room for you in the examination hall.
The last day for application is Sun 13 December.
For information on how to apply, see the web of the Student affairs office for Mathematics.
Concerning Homework set number 2
Since the second set of homework problems are so late, we will postpone the deadline for submitting them.
The new deadline is Mon 21 December.
Homework problem answers have appeared
Answers to the first set of homework problems have now been published (one misprint corrected 1 Dec), they can be found here.
We have a course board!
Mélanie and Elis were elected on the (second) lecture on Monday 9 November. See here.
Welcome to this course!
Under this heading important information concerning the course will appear.
Make it a habit to check for news regularly.
Course registration
To follow the course you must register for this semester (otherwise we can't enter your results in the computer system and the "CSN" won't know that you follow it).
To register, see the web of the Student affairs office for Mathematics.
It is now too late to register over the web. If you missed it and want to register, write to the course secretary, like those who re-register:
Those who want to re-register (i.e. have previously been registered on this course) should write to the course secretery, see below. State your name, your personal identity number ("personnummer") and the name and number of the course.

Important events and deadlines

Homework (see below under homework), deadlines:

Set 1: Mon 23 November at 17.00 in room L52,
Set 2: Mon 21 December by post or in the black letterbox on the wall inside the front door, Lindstedtsvägen 25.

Exams (for information on location and application (compulsory) see here):

exam: Wed 13 January 2016 at 14.00-19.00,
re-exam: Wed 16 Mar 2016 at 8.00-13.00.

Who is who

Teacher:: Bengt Ek (bek@math.kth.se), tel. 790 6951, office 3650 (Lindstedtsvsägen 25, 6th floor (the entrance is on the 5th floor)).
Comments and questions from course participants are welcome at the lectures or by e-mail, phone call or a personal visit. For a personal visit, to be on the safe side it is best to make an appointment by phone or e-mail.
Course secretery:: Anne Riddarström (annrid@kth.se), tel. 790 6297.
The secretery can answer questions concerning registration, reporting of results etc. Questions concerning the contents of the course should be addressed to the teacher.
Representatives on the course board (elected Monday the second week):: Mélanie Sedda (write her),
Elis Stefansson (write him).
The representatives are meant to listen to the views of the students and inform the teacher (you can of course also contact the teacher directly). The course board is planned to convene at least once during the course.

Description of the course

The importance of the subject

The importance of discrete mathematics (combinatorics, graph theory, number theory, abstract algebra and (elementary) logic) has increased tremendously since the middle of the twentieth century, both as a field (or fields) of research and because of its applications in computer science, physics, chemistry, biotechnology, economic modelling, etc.

To understand, analyse, and construct algorithms and data structures a sound knowledge of discrete mathematics is necessary, but discrete mathematics also gives opportunity to practice mathematical thinking and reasoning in ways which may be more accesible than mathematical analysis and geometry. At the same time, it can be used to model many everyday problems in ways that can be both important and entertaining.

Goals and contents of the course

See the description on the student web.

Eligibility

Elementary linear algebra, for example SF1604.

Course literature

Text book

Biggs, Norman L.: "Discrete Mathematics" (Second edition); Oxford University Press, 2002 (ISBN 9780198507178). (THS): A rather thick book (more than 400 pages, far from all of which are used in this course), but it is well written and usually popular with students.
Try to start reading as soon as possible!

Other course material (also mandatory!)

The Chinese remainder theorem pdf
RSA cryptography and primality tests pdf
On induction and recursion pdf
On planar graphs pdf (to appear)
On elementary logic and sets pdf (to appear)
Problems for the problem sessions can be found in the plan for the lectures, here (not all of them have yet appeared)
Summaries and comments on the lectures will appear in the plan for the lectures, here.
They will sometimes contain material that is not in the text book.

Further material

Here are solutions to the exercises in Biggs' book.
Before looking at the solutions, do try to solve the exercises yourself!
It is much more profitable to read a solution when you have really tried it on your own.

Examination

Exams

One written exam: TEN1, 7.5 credits, in January 2016. Re-exam in the middle of March.

Exams for 2017:
12 January 2018 pdf,    solutions pdf
5 April 2018 pdf,    solutions pdf
Exams for 2016:
12 January 2017 pdf,    solutions pdf
12 April 2017 pdf,    solutions pdf
Exams for 2015:
13 January 2016 pdf,    solutions pdf
16 March 2016 pdf,    solutions pdf   (some modifications done April 14)

Some old exams can be found here.

Homework

Twice during the course you may hand in written homework. The problems can be found here:
homework set 1, for 23 November, (pdf) (answers and hints: (pdf)),
homework set 2, for 21 December, (pdf) (answers and hints: (pdf)).
The homework can give at most 4 bonus points (2 points each) which are added to the result of Part I on the exam and re-exam in January and March 2016. The total number of points on part I can, however, not be more than 15.
Homework solutions must be handed in not later than the deadlines given here. Don't forget to enter your name and e-mail address on the solutions.
It is allowed to discuss the problems with classmates, but not to search help from others (such as fora on the internet). Everyone must write his/her own solutions, copying is not allowed and would be considered as cheating.
The solutions are to be delivered in handwritten form.

Marking

The mark on the course will be the same as the mark on the exam (A, B, C, D or E).

Tuition

Some of the lectures (on Monday mornings) will be used for problem sessions.
In the proper lectures theory and illustrating examples will be presented.
The problem sessions will be devoted to solving the problems found in the plan below.
Students are expected to have studied those problems in advance.

Plan for the lessons (provisional)
No.	Time	Room	Contents	To study before the lecture	Summary, comments
1	Mon 2 Nov 10-12	M33	Introduction to the course. Integers, divisibility, gcd, the Euclidean algorithm. headlines	Biggs 8.1-5	pdf
2	Mon 2 Nov 15-17	L52	The Diophantine equation ax+by=c. Prime factorization of integers. Modular arithmetic, Z_m. headlines	Biggs 8.5-6, 13.1-3	pdf
3	Wed 4 Nov 15-17	M33	Linear equations in Z_m, the Chinese remainder theorem, theorems of Fermat and Euler. headlines	The CRT (pdf), Biggs 13.3	pdf
4	Thu 5 Nov 10.20-12	M33	The RSA cryptosystem. Error correcting codes. headlines	On RSA (pdf) Biggs 24.1-4	pdf
5	Mon 9 Nov 10.20-12	M33	Problem session.	Problems pdf	.
6	Mon 9 Nov 15-17	L52	Sets. Equivalence relations, partitions. Partial orders. Well-orderings. headlines	Biggs 4.7, 7.2-3, 12.1-2	pdf
7	Wed 11 Nov 15-17	M33	Functions, injections, surjections, bijections. The pigeonhole principle. Cardinality of sets. headlines	Biggs 5, 6, 9.7	.
8	Thu 12 Nov 10-12	L51	Induction, recursion. Well-founded relations, ordinals. headlines	Biggs 4.3-6, On induction (pdf)	.
9	Mon 16 Nov 10-12	M33	Problem session.	Problems pdf	.
10	Mon 16 Nov 15-17	L52	Combinatorics: the addition and multiplication principles. Ramsey numbers. Ordered selections. Binomial numbers. headlines	Biggs 10.1-2, 10.4-5, 11.1, 11.3	.
11	Wed 18 Nov 15-17	L52	Multinomial numbers. Unordered selection with repetition. Stirling numbers (of the second kind). The sieve principle (the inclusion-exclusion principle). The functions ϕ(n) and μ(n). headlines	Biggs 10.3, 11.2, 11.4-5, 12.1, 12.3	.
12	Thu 19 Nov 10-12	M33	The Möbius inversion formula. Permutations. headlines	Biggs 10.6, 11.5, 12.4-6	.
13	Mon 23 Nov 10-12	Q33	Problem session.	Problems pdf	.
14	Mon 23 Nov 15-17	L52	Groups. Definition, examples. Elementary facts. headlines 17.00: deadline for homework set 1.	Biggs 20.1-5	.
15	Wed 25 Nov 15.20-17	M33	Cyclic groups. Subgroups. Cosets and Lagrange's theorem. headlines	Biggs 20.6-8	.
16	Thu 26 Nov 10-12	Q34	Groups acting on sets. Burnside's lemma. headlines	Biggs 21.1-6	.
17	Mon 30 Nov 10.20-12	M33	Problem session.	Problems pdf	.
18	Mon 30 Nov 15-17	L52	Generating functions (power series). Number of partitions of a positive integer. headlines	Biggs 25.1, 25.4, 26.1-4	.
19	Wed 2 Dec 15-17	L52	Graphs. Definitions. Elementary facts. Eulerian and Hamiltonian graphs. Trees. headlines	Biggs 15.1-5	.
20	Thu 3 Dec 10-12	M33	Graph colourings. Planar graphs. headlines	Biggs 15.6-7, Planar graphs (pdf), (to appear)	pdf
21	Mon 7 Dec 10-12	M33	Problem session.	Problems pdf	.
22	Mon 7 Dec 15-17	L52	Bipartite graphs, matchings. headlines	Biggs 17.1-6	.
23	Wed 9 Dec 15.20-17	M33	Digraphs. The max-flow min-cut theorem. headlines	Biggs 18.1-4	.
24	Thu 10 Dec 10-12	M33	A little about mathematical logic. Languages, structures, axiomatization, models. headlines	About logic (pdf), (to appear)	.
25	Mon 14 Dec 10-12	M33	Problem session. The deadline for homework set 2 is changed to 21 Dec.	Problems pdf	.
26	Wed 16 Dec 15-17	M33	Semantic consequence. Formal proofs. Gödel's completeness theorem. Gödel's incompleteness theorem. The compactness theorem. headlines slides	About logic	.
27	Thu 17 Dec 10-12	M33	Infinities. Ordinals and cardinals. The axiom of choice and well-ordering. Examples of transfinite recursion. headlines	About logic	.
Mon 21 Dec			Deadline for homework set 2 by post or in the black letterbox, Lindstedtsvägen 25, see also the text above the problems.
TEN1	Wed 13 Jan 2016 14.00-19.00	Q,V	Exam
TEN1	16/3-16 8.00-13.00	V	Re-exam