ITT9132 -- Concrete Mathematics

2019/2020 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

• First lecture: Tuesday 28 January 2020 from 14:00 to 15:30 in Room ICT-411
• First exercise session: Tuesday 28 January 2020 from 16:00 to 17:30 in Room ICT-411

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

• 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 30% of the final score.
• A final exam, contributing to 50% of the final score.

The following rules apply:

1. To be admitted to the final exam, students need to:
   1. 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.
   2. Have given at least one of the two classroom presentations.
   3. Have obtained at least 15 in 30 points at the midterm exam.
2. Only handwritten notes are allowed. Printouts, textbooks, and similar are forbidden.
3. Electronic devices, including mobile phones and smartwatches, are forbidden, with the only exception of a pocket or tabletop calculator. The students will be required to take out their cell phones, turn them off, and put them on the desk in front of them.
4. Students can take the final exam on both dates: in this case, the last returned assignment will determine the final grade.
5. Student who do not take the final exam, or do not return the assignment, will receive a "no show" mark.
6. 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: 27.01.2020