ITB8832 -- Mathematics for Computer Science

Fall semester 2022

Index


Course aims/objectives

Acquiring competence in areas of mathematics that are especially relevant to computer science and have applications in various fields, from programming to analysis of algorithms to network design.

Learning outcomes

At the end of the course, the successful students:

  1. Know standard techniques of computer science, and apply them in a variety of contexts.
  2. Know the main mathematical structures at the base of computer science, and understand their relevance and field of use.
  3. Use mathematics for problem solving and for design and testing of software.

Schedule

From 29 August 2022 to 18 December 2022.

Classroom hours are tentatively the same of the 2021 edition, which were:

Brief description of the course

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 encription scheme.
  5. Directed and undirected graphs. Partial orders. Connectivity. Planarity. Application: scheduling.

The language of the course is English.

The course gives 6 ECTS credits.

Registration

Students who would like to take the course should declare the course in ÕIS (Õppeinfosüsteem, Student Information System) by the deadlines set in the academic calendar.

Prerequisites

Calculus and algebra, first-year BSc level. Basic combinatorics and probability are a useful addition.
Some introductory textbooks are:

Learning process

Each week will include:

For each classroom hour the students must take into account at least one hour of personal study. Ideally, the students will, in this order:

  1. Attend the lecture.
  2. Study from the textbook the topics discussed in the lecture.
  3. Attempt the exercises related to those topics.
  4. Participate in the exercise session.
  5. Review the topics and the exercises.

The students are warmly encouraged to take handwritten notes during the lectures and the exercise sessions. Taking electronic notes in classroom is also fine, but only handwritten notes will be admitted during the tests and the final exam.

Lecture slides and solutions to exercises will be uploaded on the course web page by noon of the following day.

Evaluation criteria

The final grade for the course will be determined by the following:

The following rules apply:

  1. To be admitted to the final exam, students need to have attended at least 21 in 45 points from the midterm tests. Every point in addition to the first 30 counts as a bonus point for the first date of the final exam only.
  2. Students caught cheating at a test will receive 0 points for the test, be deferred to the disciplinary department, and get a 10 points penalty on their score for the final exam.
  3. Student who do not take the final exam, or do not return the assignment, will receive a "no show" mark.
  4. Students caught cheating at the final exam will receive a final grade of 0 for the course and will be deferred to the disciplinary department.

Final grade

From 5 (maximum) down to 0 (minimum).

The total of points from the final exam, together with the bonuses given by the classroom tests, is converted into the final grade according to the following table:

Grade Judgement Score Interpretation
5 Excellent 91% or more The student commands the subject.
4 Very good 81%-90% The student has a good grasp on the subject, with some small mistakes or imprecisions.
3 Good 71%-80% The student understands most of the subject, but there are some evident major issues.
2 Satisfactory 61%-70% The student manages the bulk of the subject, but also shows serious lacks or misunderstandings.
1 Poor 51%-60% The student achieved the bare minimum. Maybe the approach to the course was flawed.
0 Fail 50% or less At the end of the course the student did not display an appreciable knowledge of the subject.

Example of grading

Consider the case of a student who obtains 12, 9, and 15 points in the three tests of continuous assessment. The total is 36, so the student is admitted to the final exam.

If the student takes the exam on the first date, and obtains 55 points, then the final score is 36+55=91 points, for a final grade of 5; if they earn 15 points, then the final score is 36+15=51 points, for a final grade of 1.

If the same student takes or retakes the exam on the second or third date, and obtains 60 points, then the final score is 30+60=90 points, for a final grade of 4; if they earn 20 points, then the final score is 30+20=50 points, for a final grade of 0.


Back to course home page

Last update: 28 June 2022.