At the end of the course, the successful student:
Click HERE for a more detailed description of the course.
Autumn semester 2025, 16 weeks, 2 days per week, 2 hours per day. All times are Tallinn times.
Silvio Capobianco, contact: firstname.familyname(at)taltech.ee
E. Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Computer Science. Revision of 6 June 2018.
Available under the terms of the Creative Commons Attribution-ShareAlike 3.0 license.
Download from this page: HERE
This is the tentative program for the course, which is based on
the 2024 edition.
Some course materials from past edition are provided.
To let the students attempt the exercises on their own, the
solutions are provided after two blank pages.
| Week | Subject | Lecture | Exercises | Self-evaluation tests | Midterms and finals |
| 01.09-07.09 |
Introduction to the course. Proofs. The axiomatic
method. Proving an implication. Proving an "if and only
if". Proof by cases.
Chapter 1, pages 5-13. |
Lecture 1, 2024 edition | Exercise session 1, 2024 edition | Self-evaluation exercises set 1, 2024 edition | |
| 08.09-14.09 |
Proof by contradiction. The Well Ordering Principle. Proofs
by well ordering. Logic. Propositions from
propositions. Truth tables.
Chapter 1, pages 13-19; Chapter 2, pages 29-35; Chapter 3, pages 27-54. |
Lecture 2, 2024 edition | Exercise session 2, 2024 edition | Self-evaluation exercises set 2, 2024 edition | |
| 15.09-21.09 |
Equivalence. Validity and satisfiability. The algebra of
propositions. The SAT problem. Predicative formulas.
Chapter 3, pages 54-68. |
Lecture 3, 2024 edition | Exercise session 3, 2024 edition | Self-evaluation exercises set 3, 2024 edition | |
| 22.09-28.09 |
Mathematical data types. Sets. Sequences. Functions. Binary
relations. Finite sets.
Chapter 4, pages 103-118. |
Lecture 4, 2024 edition | Exercise session 4, 2024 edition | Self-evaluation exercises set 4, 2024 edition | |
| 29.09-05.10 |
Induction. Ordinary induction. Strong induction. Comparison
with well-ordering principle.
Chapter 5, pages 137-154. First midterm test: Friday 3 October 2025 |
First midterm test, 2024 edition | |||
| 06.10-12.10 |
State machines. States and transitions. The Invariant
Principle. Partial correctness and termination. The Stable
Marriage Problem.
Chapter 6, pages 173-193. |
||||
| 13.10-19.10 |
Recursive data types. Recursive definition. Structural
induction. Strings of matched brackets. Recursive functions
of nonnegative integers. Parenthesizing arithmetic
expressions. Games as a recursive data type. Induction in
Computer Science.
Chapter 7, pages 217-238, 257-258. |
||||
| 20.10-26.10 |
Infinite sets. Infinite cardinality. Countable and
uncountable sets. Diagonal arguments. The Halting
Problem. Russell’s Paradox and the ZFC axioms.
Chapter 8, pages 295-316. |
||||
| 27.10-02.11 |
Number theory. Divisibility. Greatest common divisor. Prime
numbers. The Fundamental Theorem of Arithmetics. Alan
Turing.
Chapter 9, pages 341-362. Second midterm test: Friday 31 October 2025 |
Second midterm test, 2024 edition | |||
| 03.11-09.11 |
Modular arithmetics. Multiplicative inverses in modular
arithmetics. Euler’s theorem. RSA public key encryption.
Chapter 9, pages 362-382 |
||||
| 10.11-16.11 |
Directed graphs and partial orders. Walks and
paths. Adjacency matrix. Scheduling.
Chapter 10, pages 421-431 |
||||
| 17.11-23.11 |
Partial orders. Representing partial orders by set
containment. Linear orders. Product orders. Equivalence
relations. Summary of relational properties. Appendix: a
proof of the Schröder-Bernstein theorem (reading, from
the slides).
Chapter 10, pages 431-449. |
||||
| 24.11-30.11 |
Simple graphs. Handshaking lemma. Graph
isomorphisms. Bipartite graphs. Matchings.
Chapter 12, pages 501-514. Third midterm test: Friday 28 November 2025 |
Third midterm test, 2024 edition | |||
| 01.12-07.12 |
Coloring. Simple walks. Connectivity. Forests and trees.
Chapter 12, pages 514-535. |
||||
| 08.12-14.12 |
Planar graphs. Drawing graphs in the plane. Definition of
planar graphs. Euler’s formula. Bounding the number of edges
in a planar graph. Returning to K5 and K3,3. Coloring planar
graphs. Classifying polyhedra. Another characterization for
planar graphs.
Chapter 13, pages 575-594. |
||||
| 15.12-21.12 |
Final exam, first date: Thursday 18 December 2025
Final exam, second date: Thursday 8 January 2026 Final exam, third date: Monday 19 January 2026 |
First date of the final exam, 2024 edition |
Last updated: 31 July 2025.