ITB8832 -- Mathematics for Computer Science

2024 Autumn Semester

Moodle: https://moodle.taltech.ee/course/view.php?id=33464
ÕIS: https://ois2.taltech.ee/uusois/koduleht/ITB8832&oppejoud=11789
To be added to the Team of the course, send an email to the instructor.

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.
Recognizes the intrinsic limitations of computers' capabilities.
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 2024, 16 weeks, 2 days per week, 2 hours per day. All times are Tallinn times.

Lectures: Mondays from 10:00 to 11:30 in Room ICO-316 (IT College).
Exercises: Wednesdays from 14:15 to 15:45 in Room ICO-314 (IT College).

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 2023 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
02.09-08.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, 2023 edition	Exercise session 1, 2023 edition	Self-evaluation exercises set 1, 2023 edition
09.09-15.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, 2023 edition	Exercise session 2, 2023 edition	Self-evaluation exercises set 2, 2023 edition
16.09-22.09	Equivalence. Validity and satisfiability. The algebra of propositions. The SAT problem. Predicative formulas. Chapter 3, pages 54-68.	Lecture 3, 2023 edition	Exercise session 3, 2023 edition	Self-evaluation exercises set 3, 2023 edition
23.09-29.09	Mathematical data types. Sets. Sequences. Functions. Binary relations. Finite sets. Chapter 4, pages 103-118.	Slides for Lecture 4, 2023 edition	Exercise session 4, 2023 edition	Self-evaluation exercises set 4, 2023 edition
30.09-06.10	Induction. Ordinary induction. Strong induction. Comparison with well-ordering principle. Chapter 5, pages 137-154. First midterm test: 4 October 2024				First midterm test, 2023 edition
07.10-13.10	State machines. States and transitions. The Invariant Principle. Partial correctness and termination. The Stable Marriage Problem. Chapter 6, pages 173-193.
14.10-20.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.
21.10-27.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.
28.10-03.11	Number theory. Divisibility. Greatest common divisor. Prime numbers. The Fundamental Theorem of Arithmetics. Alan Turing. Chapter 9, pages 341-362. Second midterm test: 1st November 2024				Second midterm test, 2023 edition
04.11-10.11	Modular arithmetics. Multiplicative inverses in modular arithmetics. Euler’s theorem. RSA public key encryption. Chapter 9, pages 362-382
11.11-17.11	Directed graphs and partial orders. Walks and paths. Adjacency matrix. Scheduling. Chapter 10, pages 421-431
18.11-24.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.
25.11-01.12	Simple graphs. Handshaking lemma. Graph isomorphisms. Bipartite graphs. Matchings. Chapter 12, pages 501-514. Third midterm test: 29 November 2024				Third midterm test, 2023 edition
02.12-08.12	Coloring. Simple walks. Connectivity. Forests and trees. Chapter 12, pages 514-535.
09.12-15.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.
16.12-22.12	Open questions session. Final exam, first date: 18 December 2024 Final exam, second date: 8 January 2024 Final exam, third date: 20 January 2024				First date of the final exam, 2023 edition

Last updated: 29 October 2024