Discrete Mathematics (Autumn 2012)
Time and location
Event |
Time |
Location |
Lectures |
Thu 14:15 - 15:45 |
Liivi 2-405 |
Peeter Laud |
Practice sessions |
Thu 16:15 - 17:45 |
Liivi 2-202 |
Margus Niitsoo |
Mon 14:15 - 15:45 |
Liivi 2-207 |
Behind the scenes |
Reimo Palm |
1st test |
Sep 27th, 14:15 - 15:45 |
Liivi 2-405 |
Jan 10th, 9:15 - 12:00 |
Liivi 2-122 |
2nd test |
Nov 15th, 14:15 - 15:45 |
Liivi 2-405 |
Jan 21st, 9:15 - 12:00 |
Liivi 2-122 |
3rd test |
Dec 20th, 14:15 - 15:45 |
Liivi 2-405 |
Jan 28th, 9:15 - 12:00 |
Liivi 2-122 |
Grading: there will be three tests during the term. The
first one will be worth 15 points, the second and third both 30 points. It
is possible to collect up to 30 points from solving the home exercises, and
up to 7.5 points from checking the solutions of other students. The grade
limits will be computed as if the maximum number of points were equal to
100.
Homework submission and feedback: The homeworks must be
submitted electronically, by e-mailing them to Margus Niitsoo (firstname dot
lastname at ut dot ee). The deadline for submission is at the start of the
working day of the Thursday two weeks after the associated lecture. The
subject line of the submission e-mail should start with DM: and the
number of the homework. It is permitted to do the homeworks in groups, in
this case the other members of the group must be CC:'ed and their names must
be listed in the body of the e-mail.
The feedback will be given through Moodle.
The tasks in the tests will be similar in nature to the tasks considered in practice
sessions, hence it makes sense to visit at least the practice sessions
regularly.
The lectures will cover a number of topics from graph theory and
combinatorics. We plan to talk about
- Recap: sets, relations, functions
- Elements of graph theory
- Eulerian and Hamiltonian graphs
- Flows, covers, matchings
- Edge and vertex coloring
- Basics of counting
- Combinations, permutations, etc.
- Principle of inclusion and exclusion
- Generating functions
- Ramsey theory (ordered substructures of random structures)
- (if time: Polya theory of counting)
News:
- Dec 4th: Last Thursday, we agreed on the days of
second attempts for the three tests. Please see the schedule above.
- Oct 29th: The second test will take place on November
15th. The third test will take place on December 20th. Both will take place
instead of the lecture.
- Sep 14th: The process of homework submission has been
detailed.
- Sep 14th: The first test will take place on September
27th, instead of the lecture.
- Aug 30th: The first lecture will be on 6th of September. There is no practice
session on 3rd of September.
Slides of the lectures will appear below. As a rule, they will not
contain proofs of “simple” statements.
- September 6th and 13th
- Slides of the second lecture added on September 9th
- September 20th — Eulerian and
Hamiltonian graphs.
- October 4th — Network
flows and Ford-Fulkerson algorithm.
- October 11th — various theorems
somehow related to matchings in graphs. I believe these slides are suitable
as setting the pace of the lecture, but not as a material for independent
studies.
- On October 18th, we'll continue from where we stopped last time. After
that, we'll consider necessary and sufficient
conditions for the existence of perfect matchings in any graph (the
slides are in Estonian, an English version with significant bit-rot is
available here).
- On October 25th, we plan to cover two topics. First, we want to speak
about finding maximum matchings in arbitrary graphs (not just in bipartite
ones; we already know how to do this). There is a set of slides covering this topic, but
we hope to do the development mostly without them. Second, we look at the
number of colours we need to correctly colour
all edges of a graph.
- On November 1st, we again plan to cover two topics. We will discuss
planar graphs and the coloring of vertices of
graphs.
- November 8th, 22nd, 29th, December 6th,
containing
- permutations, combinations, and identities involving binomial
coefficients;
- generating functions;
- Polya theory of counting.
- On December 13th, we speak about Ramsey theory on regular
substructures and on the probabilistic method of proving the
existence of certain objects.