The second lecture of the course will take place on:
Tuesday 4 February 2020 from 14:00 to 17:30 in Room ICT-411
The lecture will take place in any case, independently of the
number of students who will have registered by the 3 February
deadline.
During it, we will discuss how (and if) the course will take
place.
At the end of the course, the successful students:
Silvio Capobianco, contact: firstname.familyname(at)taltech.ee
Ronald Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics: a Foundation for Computer Science. Second edition. Addison-Wesley 1994.
The final version of the syllabus is available HERE
Original lecture slides 2010--2014 Jaan Penjam; revised 2016--2020 Silvio Capobianco
| Week | Subject | Lecture | Exercises | Talks |
| 27.01-02.02 | Introduction to the course. | Lecture of Week 1 | Exercises for Week 1 | |
| 03.02-09.02 |
Recurrent problems. Tower of Hanoi. Lines in the plane. The
Josephus problem.
Chapter 1, pages 1--12. |
Lecture 2 | Exercise session 2 | |
| 10.02-16.02 |
Recurrent problems. Generalization of the Josephus
problem. The repertoire method.
Sums. Notation. Sums and recurrences. The perturbation method. Summation factors. Chapter 1, pages 12--16; Chapter 2, pages 21--27. |
Lecture 3 | Exercise session 3 | |
| 17.02-23.02 |
Sums. Summation factors. Efficiency of
quicksort. Manipulation of sums. Multiple sums. General
methods.
Chapter 2, pages 28--46. |
Lecture 4 | Exercise session 4 | |
| 24.02-01.03 |
Sums. Finite and infinite calculus. Infinite sums.
Integer functions. Floors and ceilings. Floor and ceiling applications. Floor and ceiling recurrences. The binary operator "mod". Floor and ceiling sums. Chapter 2, pages 47--62; Chapter 3, pages 67--94. |
Lecture 5
Lecture 6 |
Exercise session 5
Self-evaluation exercises, set 1 |
|
| 02.03-08.03 | 24th Estonian Winter School in Computer Science | |||
| 09.03-15.03 |
Number theory. Prime and composite
numbers. Divisibility. Greatest common divisor. The
Euclidean algorithm. Prime numbers. The Fundamental Theorem
of Arithmetics. The distribution of prime numbers.
Chapter 4, pages 102--111, 115--123. |
Lecture of Week 7 |
Exercise session 6
Exercise session 7 |
|
| 16.03-22.03 |
Number theory. Modular arithmetics. Primality
tests. Fermat's test. Rabin-Miller test. Euler and
Möbius functions.
Chapter 4, pages 123--144. |
Lecture of Week 8 |
Exercise session 8
Midterm from 2016 Midterm recovery from 2016 |
|
| 23.03-29.03 |
Binomial coefficients. Basic identities. Basic
practice. Generating functions. Intermezzo: analytic
functions.
Chapter 5, pages 153--175, 196--197. |
Lecture of Week 9 | Exercise session 9 | |
| 30.03-05.04 |
Binomial coefficients. Generating functions. Operations on
generating functions. Building generating functions that
count. Identities in Pascal's triangle.
Chapter 5, pages 153--175, 196--197. |
Lecture of Week 10 | Exercise session 10 | |
| 06.04-12.04 |
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. |
Lecture of Week 11 | Exercise session 11 | |
| 13.04-19.04 |
Special numbers. Fibonacci numbers. Cassini's
identity. Harmonic numbers. Harmonic summations. Bernoulli
numbers.
Chapter 6, pages 272--290, 292--297. |
Lecture of Week 12 | Exercise session 12 | |
| 20.04-26.04 |
Generating functions. Solving recurrences with generating
functions. Partial fraction expansion. The Rational
Expansion Theorem.
Chapter 7, pages 331--341. |
Lecture of Week 13 | Exercise session 13 | |
| 27.04-03.05 |
Generating functions. Use of
derivatives. Convolutions. Catalan numbers. Exponential
generating functions.
Chapter 7, pages 341--369. |
Lecture of Week 14 |
Exercise session 14
Final exam 2016, first date Final exam 2016, second date |
|
| 04.05-10.05 |
Asymptotics. A hierarchy. Big-O notation. Big-O manipulation.
Chapter 9, pages 439--457. |
Lecture of Week 15 | Exercise session 15 | |
| 11.05-17.05 |
Asymptotics. Big-O 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. |
Lecture of Week 16 | Exercise session 16 |
Last updated: 31.01.2020 Silvio Capobianco