ITB8832 -- Mathematics for Computer Science

2022 Fall Semester

Goals of the course

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

Applies the principles and techniques of rigorous reasoning.
Knows the mathematical structures at the base of computer science and their applications to problem solving, game theory, and software testing.
Knows the intrinsic limitations of computers’ ability to solve problems.
Knows the mathematical foundations of modern cryptography.

Click here for a more detailed description of the course.

Schedule

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

Lectures: Mondays from 10:00 to 11:30.
Exercises: Wednesdays from 14:00 to 15:30.

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: 17 April 2023 by Silvio Capobianco