ITB8832 -- Mathematics for Computer Science

2022 Fall Semester

Goals of the course

At the end of the course, the successful students will:

Click here for a more detailed description of the course.

Schedule

From 29 August to 18 December 2022.

Instructor

Silvio Capobianco, contact: firstname.familyname(at)taltech.ee

Textbook

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

COURSE CONTENT

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