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.

Join the "ICY0001 Logic and Discrete Mathematics" Slack workspace Sign up

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 2018

  • Week 1. 04.09.18

  • Week 2. 11.09.18

  • Week 3. 18.09.18

  • Week 4. 25.09.18

  • Week 5. 02.10.18

    • Lecture 5. Set theory
    • Practicum 5. Quiz 4. Homework 5
  • Week 6. 09.10.18

    • Lecture 6. Relations and functions
    • Practicum 6. Quiz 5. Homework 6
  • Week 7. 16.10.18

    • Lecture 7. Combinatorial tools, Binomial Coefficients and Pascal's Triangle
    • Practicum 7. Quiz 6. Homework 7
  • Week 8. 23.10.18

    • Lecture 7. Combinatorial tools, Binomial Coefficients and Pascal's Triangle
    • Practicum 8. Homework 8
    • Mid-term test (1.5 h): propositional logic, predicate logic, mathematical induction, set theory
  • Week 9. 30.10.18

    • Lecture 8. Solving linear recurrence relations
    • Practicum 9. Quiz 7. Homework 10
  • Week 10. 06.11.18

    • Lecture 8. Solving linear recurrence relations
    • Practicum 10. Quiz 8. Homework 11
  • Week 11. 13.11.18

    • Lecture 9. Graphs: basic definitions and examples
    • Practicum 11. Quiz 9. Homework 11
  • Week 12. 20.11.18

    • Lecture 10. Trees
    • Practicum 12.
  • Week 13. 27.11.18

    • Lecture 11. Eulerian and Hamiltonian graphs, Dijkstra’s algorithm, TSP
    • Final test (1.5 h): relations, combinatorial tools, binomial Coefficients and Pascal's Triangle, solving linear recurrence relations, graphs
  • Week 14. 04.12.18

    • Lecture 12. Planar graphs and Euler's formula. Graph coloring
    • Practicum 7. Quiz 6. Homework 7
  • Week 15. 11.12.18

    • Makeup test: Mid-term test (1.5 h)
    • Makeup test: Final test (1.5 h)
  • Week 16.

    • Exam 17.12.18
    • Exam 18.12.18

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