Mathematics for Computer Science

The course “Mathematics for Computer Science” follows the lines of the course of the same name taught at Massachusetts Institute of Technology. It is aimed at Master students of the School of Information Technology. The course covers a series of topics from logic, set theory, discrete mathematics, and theory of computation, chosen from the first half of the textbook. Among these:

1. Proofs. The axiomatic method. Proofs by cases. Proofs by contradiction. Well ordering principle. Propositional logic in computer programs. Propositional algebra. Induction. Application: satisfiability.

2. Mathematical data types. Sets and sequences. Functions and finitary relations. Recursive data types. Recursive functions. Application: games as a recursive data type.

3. State machines. Invariants. The stable marriage problem. The halting problem. Application: program verification.

4. Number theory. Divisibility. Prime numbers. Modular arithmetic. Application: the RSA public key encryption algorithm.

5. Directed and undirected graphs. Partial orders. Connectivity. Planar graphs. Application: scheduling.

NB! This course will take place in spring semester 2024/2025 which starts on 3rd of February and ends on 16th of June (you can find that information under Start date section). The real course start and end dates will be announced at the beginning of February at the latest.

After completing this course, the student:

• applies the principles and techniques of rigorous reasoning;
• employs recursive data structures and algorithms to problem solving, game theory, and software testing;
• knows 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.

Final assessment can consist of one test/assignment or several smaller assignments completed during the whole course. After declaring a course the student can re-sit the exam/assessment once. Assessment can be graded or non-graded. For specific information about the assessment process please get in touch with the contact person of this course. For specific information about grade transfer please contact your home university

The course is aimed at Master students in Computer Science, Information Technology, and related subjects. It covers topics from logic, set theory, discrete mathematics, and theory of computation, with applications to game theory, software testing, cryptography, scheduling, and resource management. Successful completion gives 6 ECTS credits. Prerequisites are algebra, calculus, and programming at the level of the first year of a BSc in Computer Science. The final grade is based on the outcome of three midterm tests and one final exam, plus non-mandatory group work for extra credit. For further information consult the web page https://www.cs.ioc.ee/~silvio/ITB8832/index.html or contact the instructor at the email address silvio.capobianco@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 from https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
• Additional references:
• Richard W. Hamming, Methods of Mathematics Applied to Calculus, Probability, and Statistics, Dover 2004.
• Ivan Niven, Mathematics of Choice, The Mathematical Association of America 1965.
• Raymond M. Smullyan, A Beginner’s Guide to Mathematical Logic, Dover 2014.
• Brian S. Thomson, Judith B. Bruckner and Andrew M. Bruckner, ElementaryReal Analysis, Second Edition, 2008. Available from http://www.classicalrealanalysis.com/
• Mati Abel and Ülo Kaasik, Matemaatikasõnaraamat, TEA 2002.

lectures, exercises