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)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 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