At the end of the course, the successful students will:
From 29 August to 18 December 2022.
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
These are the topics covered in the 2021 edition of the course.
For the first four weeks, lecture slides, classroom exercises,
and self-evaluation exercises are available.
For the fifth week, the text of the first midterm of 2021 is
available.
Week | Subject | Lecture | Exercises | Self-evaluation tests | Midterms and finals |
29.08-04.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, 2021 edition | Exercise session 1, 2021 edition | Self-evaluation exercises set 1, 2021 edition | |
05.09-11.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, 2021 edition | Exercise session 2, 2021 edition | Self-evaluation exercises set 2, 2021 edition | |
12.09-18.09 |
Equivalence. Validity and satisfiability. The algebra of
propositions. The SAT problem. Predicative formulas.
Chapter 3, pages 54-68. |
Lecture 3, 2021 edition | Exercise session 3, 2021 edition | Self-evaluation exercises set 3, 2021 edition | |
19.09-25.09 |
Mathematical data types. Sets. Sequences. Functions. Binary
relations. Finite sets.
Chapter 4, pages 103-118. |
Slides for Lecture 4, 2021 edition | Exercise session 4, 2021 edition | Self-evaluation exercises set 4, 2021 edition | |
26.09--02.10 |
Induction. Ordinary induction. Strong induction. Comparison
with well-ordering principle.
Chapter 5, pages 137-154. First midterm test |
First midterm test, 2021 edition | |||
03.10-09.10 |
State machines. States and transitions. The Invariant
Principle. Partial correctness and termination. The Stable
Marriage Problem.
Chapter 6, pages 173-193. |
||||
10.10-16.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. |
||||
17.10-23.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. |
||||
24.10-30.10 |
Number theory. Divisibility. Greatest common divisor. Prime
numbers. The Fundamental Theorem of Arithmetics. Alan
Turing.
Chapter 9, pages 341-362. Second midterm test |
||||
31.10-06.11 |
Modular arithmetics. Multiplicative inverses in modular
arithmetics. Euler’s theorem. RSA public key encryption.
Chapter 9, pages 362-382 |
||||
07.11-13.11 |
Directed graphs and partial orders. Walks and
paths. Adjacency matrix. Scheduling.
Chapter 10, pages 421-431 |
||||
14.11-20.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. |
||||
21.11-27.11 |
Simple graphs. Handshaking lemma. Graph
isomorphisms. Bipartite graphs. Matchings.
Chapter 12, pages 501-514. Third midterm test |
||||
28.11-04.12 |
Coloring. Simple walks. Connectivity. Forests and trees.
Chapter 12, pages 514-535. |
||||
05.12-11.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. |
||||
12.12-18.12 |
Open questions session.
Final exam, first date |
Last updated: 23 August 2022 by Silvio Capobianco