ITB8832 -- Mathematics for Computer Science

2023 Autumn Semester

Goals of the course

At the end of the course, the successful student:

Click HERE for a more detailed description of the course.


Autumn semester 2023, 16 weeks, 2 days per week, 2 hours per day.


Silvio Capobianco, contact: firstname.familyname(at)


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 2022 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
04.09-10.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, 2022 edition Exercise session 1, 2022 edition Self-evaluation exercises set 1, 2022 edition
11.09-17.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, 2022 edition Exercise session 2, 2022 edition Self-evaluation exercises set 2, 2022 edition
18.09-24.09 Equivalence. Validity and satisfiability. The algebra of propositions. The SAT problem. Predicative formulas.
Chapter 3, pages 54-68.
Lecture 3, 2022 edition Exercise session 3, 2022 edition Self-evaluation exercises set 3, 2022 edition
25.09-01.10 Mathematical data types. Sets. Sequences. Functions. Binary relations. Finite sets.
Chapter 4, pages 103-118.
Slides for Lecture 4, 2022 edition Exercise session 4, 2022 edition Self-evaluation exercises set 4, 2022 edition
02.10-08.10 Induction. Ordinary induction. Strong induction. Comparison with well-ordering principle.
Chapter 5, pages 137-154.
First midterm test
First midterm test, 2022 edition
09.10-15.10 State machines. States and transitions. The Invariant Principle. Partial correctness and termination. The Stable Marriage Problem.
Chapter 6, pages 173-193.
16.10-22.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.
23.10-29.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.
30.10-05.11 Number theory. Divisibility. Greatest common divisor. Prime numbers. The Fundamental Theorem of Arithmetics. Alan Turing.
Chapter 9, pages 341-362.
Second midterm test
06.11-12.11 Modular arithmetics. Multiplicative inverses in modular arithmetics. Euler’s theorem. RSA public key encryption.
Chapter 9, pages 362-382
13.11-19.11 Directed graphs and partial orders. Walks and paths. Adjacency matrix. Scheduling.
Chapter 10, pages 421-431
20.11-26.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.
27.11-03.12 Simple graphs. Handshaking lemma. Graph isomorphisms. Bipartite graphs. Matchings.
Chapter 12, pages 501-514.
Third midterm test
04.12-10.12 Coloring. Simple walks. Connectivity. Forests and trees.
Chapter 12, pages 514-535.
11.12-17.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.
18.12-24.12 Open questions session.
Final exam, first date: 20 December 2023
Final exam, second date: 3 January 2024
Final exam, third date: 15 January 2024

Last updated: 5 September 2023