ITT9132 -- Concrete Mathematics

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.
Click here for a more detailed description of the course.

Schedule

Spring semester 2025

Instructor

Silvio Capobianco, contact: firstname.familyname(at)taltech.ee

Textbook

Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics: a Foundation for Computer Science. Second edition. Addison-Wesley 1994.

Course content

These are the topics covered in the 2023 edition of the course.
For the first five weeks, lecture slides and classroom exercises (without solutions) are available.

Week Subject Lecture Exercises Talks
Week 1 Introduction to the course. Lecture 1 Exercise session 1
Week 2 Recurrent problems. Tower of Hanoi. Lines in the plane. The Josephus problem.
Chapter 1, pages 1--12. 		Lecture 2 Exercise session 2
Week 3 Recurrent problems. Binary representations. Generalization of the Josephus function. The repertoire method.
Sums. Notation. Sums and recurrences. The perturbation method. Summation factors. Efficiency of quicksort. Manipulation of sums.
Chapter 1, pages 12--16; Chapter 2, pages 21--34. 		Lecture 3 Exercise session 3
Week 4 Sums. Summation factors. Efficiency of quicksort. Manipulation of sums. Multiple sums. General methods. Finite and infinite calculus.
Chapter 2, pages 34--56. 		Lecture 4 Exercise session 4
Week 5 Sums. Infinite sums. Cesàro and Abel summations.
Integer Functions. Floor/ceiling applications.
Chapter 2, pages 56--62; Chapter 3, pages 67--74. 		Lecture 5 Exercise session 5
Week 6 Integer functions. Floor/ceiling applications. Floor/ceiling recurrences. "mod": the binary operation. Floor/ceiling sums.
Chapter 3, pages 67--78, 81--85.
Week 7 Number Theory. Divisibility. Primes. Prime examples. Factorial factors. Relative primality.
Chapter 4, pages 102--114, 115--118.
Week 8 Number theory. Modular arithmetics. Additional applications. Primality tests. Fermat's test. Rabin-Miller test. Euler and Möbius functions.
Chapter 4, pages 123--144.
Week 9 Binomial Coefficients. Basic identities. Basic practice. Generating functions. Intermezzo: analytic functions.
Chapter 5, pages 153--175, 196--197.
Midterm test. 		Midterm test
Week 10 Binomial Coefficients. Generating functions. Operations on generating functions. Building generating functions that count. Identities in Pascal's triangle.
Chapter 5, pages 196--204.
Week 11 Special Numbers. Stirling numbers of the first and second kind. Stirling's inversion formula. Generating function of falling and rising factorials. Fibonacci numbers. Generating function of Fibonacci numbers.
Chapter 6, pages 257--267, 292--2927.
Week 12 Special Numbers. Fibonacci numbers. Cassini's identity. Harmonic numbers. Harmonic summations. Bernoulli numbers.
Chapter 6, pages 272--290, 292--297.
Week 13 Generating Functions. Solving recurrences with generating functions. Partial fraction expansion. The Rational Expansion Theorem.
Chapter 7, pages 331--343.
Week 14 Generating functions. Use of derivatives. Convolutions. Catalan numbers. Exponential generating functions.
Chapter 7, pages 343--369.
Week 15 Asymptotics. A hierarchy. Big Oh notation. Big Oh manipulation.
Chapter 9, pages 439--457.
Week 16 Asymptotics. Big Oh manipulation. Two asymptotic tricks. Euler's summation formula. Stirling's approximation for the logarithm of the factorial.
Chapter 9, pages 452--453, 463--475, 481--489. 		First date of the final exam
Back to home page

Last updated: 22.11.2024 Silvio Capobianco