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.

Back to home page

Last updated: 03.02.2023 Silvio Capobianco