Concrete Mathematics

Selected topics of discrete mathematics that support advanced computer programming and the analysis of algorithms. Selection is made from the following topics according to interests and preliminary knowledge of students. 1) Sums: Sums and recurrences, Manipulation of sums, Multiple Sums, General methods of summation Finite and Infinite calculus, Infinite sums; 2) Integer Functions: Floors and ceilings, Floor/Ceiling applications, Floor/Ceiling recurrences, Floor/Ceiling sum; 3) Binomial Coefficients: Basic Identities, Applications, Generating functions for binomial coefficients; 4) Generating Functions: Basic manoeuvres, Solving recurrences, Convolutions, Exponential generating functions; 5) Asymptotics : O notation, O manipulation, Bootstrapping, Trading tails, Eulers summation formula.

NB! This course will take place in spring semester 2024/2025 which starts on 3rd of February and ends on 16th of June (you can find that information under Start date section). The real course start and end dates will be announced at the beginning of February at the latest.

Understanding of the concrete mathematics topics covered and the necessary skills for solving a range of concrete mathematics problems encountered in computing and information technology.

Final assessment can consist of one test/assignment or several smaller assignments completed during the whole course. After declaring a course the student can re-sit the exam/assessment once. Assessment can be graded or non-graded. For specific information about the assessment process please get in touch with the contact person of this course. For specific information about grade transfer please contact your home university

The course is aimed at PhD and Master students in Computer Science, Information Technology, and related subjects. Its topics are recurrence equations and methods for their solutions, combining notions from continuous and discrete mathematics. Successful completion gives 6 ECTS credits. Prerequisites are udergraduate algebra and calculus, plus the basics of combinatorics (binomial theorem). The final grade is based on the outcome of two classroom talks, one midterm test, and one final exam, with an option for a third classroom talk for extra credit. For further information consult the web page https://www.cs.ioc.ee/~silvio/ITT9132/index.html or contact the instructor at the email address silvio.capobianco@taltech.ee

• 1. Graham, R. M., D. E., Knuth & 0 . Patashnik Concrete Mathematics, A Foundation for Computer Science, Addison
• Wesley, 1994.
• 2. Kursuse koduleht on aadressil: http://www.cs.ioc.ee/cm/

lectures, exercises