ITT9132  Concrete Mathematics
Spring Semester
Index
To provide students with mathematical tools for the study of
recurrence equations and their applications to relevant to
computing and information technology.
At the end of the course, the successful students:

Know the fundamental concepts and methods of continuous
and discrete mathematics relevant to computing and
information technology.

Solve problems of discrete mathematics with the aid of
methods from continuous mathematics.

Apply mathematical methods to the analysis of algorithms.

Lectures: Tuesdays 10:0011:30 Room SOC310.

Exercise sessions: Thursdays 12:0013:30 Room SOC415.
The course "Concrete Mathematics" deals with topics in
both continuous and discrete mathematics (whence
the name) with a special focus on the solution of recurrence
equations. It is aimed at Master and Doctoral students of the
School of Information Technology. Students from other
departments who are interested in the course subject are also
encouraged to participate.
The course will discuss several topics which have important
applications in advanced computer programming and the analysis
of algorithms. Selection is made from the following topics
according to interests and preliminary knowledge of students:

Sums. Sums and recurrences. Manipulation of sums. Multiple
Sums. General methods of summation. Finite and Infinite
calculus. Infinite sums.

Integer Functions. Floors and ceilings. Floor/Ceiling
applications. Floor/Ceiling recurrences. Floor/Ceiling sums.

Number Theory. Divisibility. Prime numbers. Greatest common
divisor. Primality testing. The Euler and Möbius functions.

Binomial Coefficients. Basic
Identities. Applications. Generating functions for binomial
coefficients.

Special Numbers. Stirling numbers of the second and of the
first kind. Fibonacci numbers. Harmonic numbers. Bernoulli
numbers.

Generating Functions. Basic maneuvers. Solving
recurrences. Convolutions. Exponential generating functions.

Discrete Probability. Mean and variance. Probability
generating functions. Flipping coins. Hashing.

Asymptotics. BigO notation. BigO
manipulation. Bootstrapping. Trading tails. Euler's summation
formula.
The language of the course is English.
The course gives 6 ECTS credits.
Students who wish to get credit for the course must declare it in
ÕIS (Õppeinfosüsteem, Student Information
System) by the deadlines set in the academic calendar.
Firstyear university level of algebra and calculus, plus the
basics of combinatorics (Newton’s binomial theorem). Such
prerequisites can be provided, for example, by IAX0010 Discrete
Mathematics, or by ITT0030 Discrete Mathematics II.
Each week will include:
 Two hours of classroom lectures.
 Two hours of classroom exercises.
For each classroom hour the students must take into account at
least one hour of personal study. Ideally, each week, the
students will, in this order:

Attend the lecture.

Study the textbook material covered in the lecture.

Attempt the exercises related to those topics.

Participate in the exercise session.

Review the material discussed during the week.

Compile personal notes.
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 if tests and/or exams are
given in classroom, then only handwritten notes are admitted.
Lecture slides and solutions to exercises will be uploaded on
the course web page by noon of the following day.
The final grade for the course will be determined by the
following:

Two classroom talks, each contributing
to 10% of the final grade.
For each classroom presentation, the student will give a
10minutes talk discussing their original solution of an
exercise from the book, chosen together with the instructor.

One midterm test, contributing to 30%
of the final score.
Such test could take place either in classroom, or online. In
the first case, only handwritten notes are admitted.

A final exam, contributing to 50% of the
final score.
The exam could take place either in classroom, or online. In
the first case, only handwritten notes are admitted.
Each talk will consist in a 10minutes discussion of the
student's original solution of an exercise from the textbook,
chosen together with the instructor.
The textbook may contain hints to the solution, which the
student may follow.
If class attendance is not possible, the talk will be given
on Microsoft Teams.
The students will work on a series of exercises including, but
not limited to, problem solving and multiple choice questions.

If the test is given in classroom, only handwritten notes are
allowed; electronic devices, with the exception of a pocket or
tabletop calculator, are forbidden.
If the test is given on Moodle, it will remain available for a
limited time; only one attempt is possible, and the students
will have three hours to complete it.

Students caught cheating at the midterm test will receive 0
points for it and be deferred to the disciplinary department.
The students will work on a series of exercises including, but not
limited to, problem solving and multiple choice questions.

To be admitted to the final exam, students need to:

Have given at least one of the two classroom
presentations; and

Have obtained at least 15 in 30 points at the
midterm exam.

Student who are not admitted to the final exam, do not take
it, or do not return the assignment, will receive a "no
show" mark.

Students who want to improve their grade can retake the exam
once, in one of the established dates. In this case, the final
grade is determined by the last assignment returned.

If the exam is given in classroom, only handwritten notes are
allowed; electronic devices, with the exception of a pocket or
tabletop calculator, are forbidden.
If the exam is given on Moodle, it will remain available for a
limited time; only one attempt is possible, and the students
will have six hours to complete it.

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.
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.

Back to course home page
Last update: 12.10.2022