ITB8832 -- Mathematics for Computer Science

2023 Autumn Semester

Goals of the course

At the end of the course, the successful student:

Applies the principles and techniques of rigorous reasoning.
Employs recursive data structures and algorithms to problem solving, game theory, and software testing.
Understands the intrinsic limitations of computers’ ability to solve problems.
Employs notions and methods from the mathematical foundations of modern cryptography.
Applies the concepts and techniques of graph theory to scheduling and resource management.

Click HERE for a more detailed description of the course.

Schedule

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

Lectures: Mondays from 10:00 to 11:30 in Room ICO-219 (IT College).
Exercises: Wednesdays from 12:00 to 13:30 in Room U06A-204.

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

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