ITT9132 -- Concrete Mathematics

2018/2019 Spring Semester

IMPORTANT: Dates of final exam

The following dates are set for the final exam:

  1. Wednesday 22 May 2019 from 16:00 to 19:00 in Room ICT-A1
    Access free, no need of registration.
    The solutions are available HERE (corrects an error in question 20)
    The results are available HERE (updated)
  2. Wednesday 5 June 2019 from 16:00 to 19:00 in Room ICT-A2
    Please register by sending an email to the instructor no later than Monday 3 June 2019.
    The solutions are available HERE (corrects an error in question 20)
    The results are available HERE (updated)
  3. Wednesday 12 June 2019 from 16:00 to 19:00 in Room ICT-A2
    Only for those students who took the exam in one of the first two dates but not both, and earned a final grade of 0, 1 or 2.
    Please register by sending an email to the instructor no later than Monday 10 June 2019.
    The solutions are available HERE
    The results are available HERE

Midterm test recovery

The results of the midterm test recovery of 12 April 2019 are available HERE
The solutions of the exercises are available HERE

Midterm test

The results of the midterm test of 29 March 2019 are available HERE
The solutions of the exercises are available HERE --- new version 31.03.2019, corrects an error

Goals of the course

At the end of the course, the successful students:

Click here for a more detailed description of the course.

Schedule

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 (updated weekly)

The final version of the syllabus is available HERE

Original lecture slides 2010--2014 Jaan Penjam; revised 2016--2019 Silvio Capobianco

Week Subject Lecture Exercises Talks
28.01-03.02 Introduction to the course. Lecture of Week 1 Exercises for Week 1 with a correction
04.02-10.02 Recurrent problems. Tower of Hanoi. Lines in the plane. The Josephus problem.
Chapter 1, pages 1--12. 		Lecture 2 Exercise session 2
11.02-17.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
18.02-25.02 Sums. Summation factors. Efficiency of quicksort. Manipulation of sums. Multiple sums. General methods.
Chapter 2, pages 28--46. 		Lecture 4 Exercise session 4
26.02-03.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
04.03-10.03 24th Estonian Winter School in Computer Science
11.03-17.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
18.03-24.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
25.03-31.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
01.04-07.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
08.04-14.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
15.04-21.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 update 17.04.2019 Exercise session 12
22.04-28.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
29.04-05.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
06.05-12.05 Asymptotics. A hierarchy. Big-O notation. Big-O manipulation.
Chapter 9, pages 439--457. 		Lecture of Week 15 Exercise session 15 Corrects an error in the text of Exercise 9.14 (and subsequent solution)
13.05-19.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: 12.06.2019 Silvio Capobianco