ITT9132 -- Concrete Mathematics
2018/2019 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: Mondays from 16:00 to 18:00 in Room ICT-315
-
Exercises: Wednesdays from 16:00 to 18:00 in Room ICT-638
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. Big-O notation. Big-O
manipulation. Bootstrapping. Trading tails. Euler's summation
formula.
The language of the course is English.
The course gives 6 ECTS credits.
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.
First-year 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 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.
The final grade for the course will be determined by the
following:
-
Two classroom presentations of the students' own solutions of
problems from the book chosen with the instructor. Each talk
contributes to 10% of the final score.
-
One midterm test, contributing to 25% of the final score.
-
A final exam, contributing to 55% of the final score.
The following rules apply:
-
To be admitted to the final exam, students need to:
-
Have earneded at least 21 attendance tokens between
lectures and exercise sessions, of which at least 8
from lectures and at least 8 from exercises.
Attendance is verified via signature at the beginning of
the class.
In case of motivated serious impediments (e.g., a sick
leave) up to one week can be discounted.
-
Have given at least one of the two classroom
presentations.
-
Have completed at least 50% of the midterm exam.
-
Only handwritten notes are allowed. Printouts,
textbooks, and similar are forbidden.
-
Electronic devices, with the exception of a pocket or tabletop
calculator, are forbidden. The students will be required to
take out their cell phones, turn them off, and put them on the
desk in front of them.
-
Students can take the final exam on both dates: in this case,
the last returned assignment will determine the final grade.
-
Student who do not take the final exam, or do not return the
assignment, will receive a “no show” mark.
-
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: 01.02.2019