# ITT9132 -- Concrete Mathematics

### Goals of the course

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

### Schedule

Spring semester 2023
• Lectures: Tuesdays 10:00-11:30 SOC-310
• Exercise sessions: Thursdays 12:00-13:30 SOC-415

### 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 2021 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 -- updated to 2023 edition Exercise session 1 -- updated to 2023 edition Week 2 Recurrent problems. Tower of Hanoi. Lines in the plane. The Josephus problem. Binary representation. The repertoire method. Chapter 1, pages 1--15. Lecture 2 Exercise session 2 Week 3 Recurrent problems. Generalization of the Josephus problem. The repertoire method. Sums. Notation. Sums and recurrences. The perturbation method. Summation factors. Chapter 1, pages 15--16; Chapter 2, pages 21--26, 32--33. Lecture 3 Exercise session 3 Week 4 Sums. Summation factors. Efficiency of quicksort. Manipulation of sums. Multiple sums. General methods. Chapter 2, pages 28--46. Lecture 4 Exercise session 4 Week 5 Sums. Finite and infinite calculus. Infinite sums. Cesàro and Abel summations. Chapter 2, pages 47--62. Lecture 5 Exercise session 5 Week 6 Integer functions. Floors and ceilings. 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. Relative primality. Modular arithmetics. Additional applications. Primality tests. Fermat's test. Rabin-Miller test. Euler and Möbius functions. Chapter 4, pages 119--122, 123--126, 129--136. Week 9 Binomial coefficients. Basic identities. Basic practice. Generating functions. Intermezzo: analytic functions. Chapter 5, pages 153--175, 196--197. 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, 290--292, 297--299. Week 12 Special numbers. Fibonacci numbers. Cassini's identity. Harmonic numbers. Harmonic summations. Bernoulli numbers. Chapter 6, pages 272--284, 292--297. Week 13 Generating functions. Solving recurrences with generating functions. Partial fraction expansion. The Rational Expansion Theorem. Chapter 7, pages 331--341. Week 14 Generating functions. Use of derivatives. Convolutions. Catalan numbers. Exponential generating functions. Chapter 7, pages 343--368. Week 15 Asymptotics. A hierarchy. Big-O notation. Big-O manipulation. Chapter 9, pages 439--457. Week 16 Asymptotics. Big-O manipulation. Two asymptotic tricks. Euler's summation formula. Stirling's approximation for the logarithm of the factorial. Chapter 9, pages 463--475, 481--489.