ITT9132 -- Concrete Mathematics

Spring Semester

Index

• Course aims/objectives
• Learning outcomes
• Schedule
• Brief description of the course
• Registration
• Prerequisites
• Learning process
• Evaluation criteria
• Final grade

Course aims/objectives

To provide students with mathematical tools for the study of recurrence equations and their applications to relevant to computing and information technology.

Learning outcomes

At the end of the course, the successful students:

1. Know the fundamental concepts and methods of continuous and discrete mathematics relevant to computing and information technology.
2. Solve problems of discrete mathematics with the aid of methods from continuous mathematics.
3. Apply mathematical methods to the analysis of algorithms.

Schedule

• Lectures: Tuesdays 10:00-11:30 Room SOC-310.
• Exercise sessions: Thursdays 12:00-13:30 Room SOC-415.

Brief description of the course

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:

1. Sums. Sums and recurrences. Manipulation of sums. Multiple Sums. General methods of summation. Finite and Infinite calculus. Infinite sums.
2. Integer Functions. Floors and ceilings. Floor/Ceiling applications. Floor/Ceiling recurrences. Floor/Ceiling sums.
3. Number Theory. Divisibility. Prime numbers. Greatest common divisor. Primality testing. The Euler and Möbius functions.
4. Binomial Coefficients. Basic Identities. Applications. Generating functions for binomial coefficients.
5. Special Numbers. Stirling numbers of the second and of the first kind. Fibonacci numbers. Harmonic numbers. Bernoulli numbers.
6. Generating Functions. Basic maneuvers. Solving recurrences. Convolutions. Exponential generating functions.
7. Discrete Probability. Mean and variance. Probability generating functions. Flipping coins. Hashing.
8. 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.

Registration

Prerequisites

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.

Learning process

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:

1. Attend the lecture.
2. Study the textbook material covered in the lecture.
3. Attempt the exercises related to those topics.
4. Participate in the exercise session.
5. Review the material discussed during the week.
6. 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.

Evaluation criteria

• Two classroom talks, each contributing to 10% of the final grade.
  For each classroom presentation, the student will give a 10-minutes 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.

Classroom talks

Each talk will consist in a 10-minutes 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.

Midterm test

The students will work on a series of exercises including, but not limited to, problem solving and multiple choice questions.

1. 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.
2. Students caught cheating at the midterm test will receive 0 points for it and be deferred to the disciplinary department.

Final exam

The students will work on a series of exercises including, but not limited to, problem solving and multiple choice questions.

1. To be admitted to the final exam, students need to:
   1. Have given at least one of the two classroom presentations; and
   2. Have obtained at least 15 in 30 points at the midterm exam.
2. 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.
3. 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.
4. 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.
5. 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:

Back to course home page

Last update: 12.10.2022