ICY0001 Logic and Discrete Mathematics

This course is designed to introduce students to the techniques, algorithms, and reasoning processes involved in the study of discrete mathematical structures. Students will be introduced to set theory, deductive and inductive reasoning, elementary counting techniques, ordering, functional and equivalence relations, graphs, and trees. The aim is to give them knowledge and skills that would enable to use the basic methods of discrete mathematics in subsequent courses, in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

Exam arrangement details and registration

Choose only one date. Please also register at ÕIS (corresponding date), otherwise registration is not valid.

Topics to be covered

  • Elementary set theory (basic definitions and set operations, the power set and Cartesian products);
  • Basic connectives in propositional logic and their properties with emphasis on some of the methods of proving mathematical results;
  • Quantifiers in predicate logic and in infinitely large domain sets;
  • Mathematical induction;
  • Binary relations and, in particular, the equivalence relation; partial order relations;
  • Basic counting techniques, combinations, permutations;
  • Binomial coefficients, Pascal’s triangle;
  • Graphs, vertices, edges, paths, cycles;
  • Eulerian and Hamiltonian graphs, travelling-salesman problem;
  • Basic definitions and properties of trees;
  • Planar graphs, graph colouring.

Schedule and lecture slides 2017

Week Date Topics, Lecture Excercises Quiz Homework
3 21.09.17 Introduction Practicum 1 HW1
Lecture 1. Propositional logic
Lecture 2. Predicate logic
4 28.09.17 Lecture 3. Introduction to proof techniques Practicum 2 Quiz 1 HW2
5 05.10.17 Lecture 4. Induction and recursion Practicum 3 Quiz 2 HW3
6 12.10.17 Lecture 5. Set theory Practicum 4 Quiz 3 HW4
7 19.10.17 Lecture 5. Set theory
Lecture 6. Relations and functions
Practicum 5 HW5
8 26.10.17 Lecture 7. Combinatorial tools, Binomial Coefficients and Pascal's Triangle Practicum 6 Quiz 4
9 02.11.17 Practicum 7 HW6
Mid-term test: propositional logic, predicate logic, mathematical induction, set theory (1.5 h) Variant A Variant B
10 09.11.17 Lecture 8. Solving linear recurrence relations Practicum 8 Quiz 5 HW7
11 16.11.17 Practicum 9 Quiz 6 HW8
12 23.11.17 Lecture 9. Graphs: basic definitions and examples Practicum 10 Quiz 7 HW9
13 30.11.17 Lecture 10. Trees Practicum 11
14 07.12.17 Lecture 11. Eulerian and Hamiltonian graphs, Dijkstra’s algorithm, TSP
Final test: relations, combinatorial tools, binomial Coefficients and Pascal's Triangle, solving linear recurrence relations, graphs (1.5 h)
15 14.12.17 Planar graphs and Euler's formula. Graph coloring Practicum 12
16 21.12.17
Makeup test: Mid-term test (1.5 h)
Makeup test: Final test (1.5 h)

Video recording of the lectures are here

Grading

The grading allocation is designed as follows:

The final ranking for the course will turn out by summarising the student’s individual results of quizzes, tests and exam (maximum sum of points is 100) and the final grade will be as follows:

Results

Study material

Primary material:

  • shaum

    S.Lipschutz and M.Lipson. Schaum's Outline of Discrete Mathematics, McGraw Hill 2007, Revised 3rd edition

  • rosen

    K. H. Rosen. Discrete Mathematics and Its Applications, WCB/McGraw Hill, 7th edition

Additional material:

  • pelikan

    L. Lovász, J. Pelikán, K. Vesztergombi. Discrete mathematics: elementary and beyond. Springer 2003

  • palm

    R. Palm. Diskreetse matemaatika elemendid. Tartu Ülikooli Kirjastus, Tartu, 2003. Avalik koopia TÜ Raamatukogust

  • vilenkin

    Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: ФИМА, МЦНМО, 2006 или старая версия Виленкин, Н. Я. Комбинаторика. Москва : Наука, 1969. Ester Tõlge: N. J.Vilenkin. Kombinatoorika. Tallinn : Valgus, 1975 Ester