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

Aims and objectives

The purpose of this course is to provide students with powerful tools from continuous mathematics for the resolution of problems in discrete mathematics related to computing and information technology.

Learning outcomes

At the end of the course, the successful student:

1. Combines techniques from different branches of both continuous and discrete mathematics, including combinatorics and complex analysis.
2. Designs procedures to efficiently evaluate complex finite and infinite sums.
3. Understands the properties of several important families of numbers and applies them to solve problems of counting and estimate.
4. Determines explicit forms for numerical sequences defined implicitly by recurrence equations.
5. Provides accurate asymptotic estimates for sequences defined recursively.

Schedule

• Lectures: to be announced
• Exercise sessions: to be announced

Brief description of the course

The course "ITT9132 Concrete Mathematics" is focused on the study of recurrence equations and the methods for their solution and approximation. It is primarily addressed at Doctoral and Master students of the School of Information Technology. Students from other departments who are interested in the discussed subjects are welcome to join.

The course will cover several topics which have important applications in advanced computer programming and the analysis of algorithms:

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. Asymptotics. Big Oh notation. Big Oh 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).

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.
  The talks can also be given remotely on Teams.
• 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.
• An optional third classroom talk for extra credit.

Each talk is worth up to 10 points. The midterm test is worth up to 30 points.

To be admitted to the final exam, a student must have given at least one classroom presentation and obtained at least 15 points on the midterm test.

Classroom talks

For each classroom talk, the student will give a 10-minutes discussion of their 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.
The talks can also be given remotely on Microsoft Teams.

Midterm test

The students will work on a set 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.

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 set 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: 22.11.2024