Course teacher(s)
Samuel FIORINI (Coordinator)ECTS credits
5
Language(s) of instruction
french
Course content
Mathematical proofs: techniques. Elementary arithmetic. Graphs and trees. Orders and relations. Elementary counting: factorials, binomial and multinomial coefficients. Inclusion-exclusion formula. Linear recurrences. Non-linear recurrences, including "divide-and-conquer" recurrences and the Master Theorem. Generating functions. Asymptotics, including Stirling's formula. Fibonacci, Catalan, Bernouilli and harmonic numbers.
Objectives (and/or specific learning outcomes)
After completing this teaching unit, the student will be able to:
- write proofs of mathematical statements;
- solve counting problems;
- estimate the asymptotic behavior of series, including in particular the solution of a "divide-and-conquer" equation.
- think formally about (or using) graphs and relations.
Prerequisites and Corequisites
Required and Corequired knowledge and skills
Required and corequired courses
Courses requiring this course
Cours ayant celui-ci comme co-requis
Teaching methods and learning activities
Lectures. Exercise sessions.
References, bibliography, and recommended reading
- Lehman, Leighton and Meyer. Mathematics for Computer Science, 2018.
- Graham, Knuth and Patashnik, Concrete mathematics. Addison-Wesley, 1989.
- Cameron, Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994.
- Van Lint and Wilson, A Course in Combinatorics. Cambridge University Press 2001.
- Flajolet and Sedgewick, Analytic Combinatorics. Cambridge University Press 2009.
Course notes
- Syllabus
- Université virtuelle
Other information
Additional information
Contacts
Samuel Fiorini <Samuel.Fiorini@ulb.be>
Campus
Plaine
Evaluation
Method(s) of evaluation
- Other
Other
A written exam will be held during the January exam period.
For students who have not passed the course by the end of the January exam period, a written exam will be held during the second exam period, in August–September.
These written exams will last approximately 3 hours and will cover the course theory and exercises.
The instructor reserves the right to invite any student to a supplementary oral interview to verify their personal mastery of the exam content, particularly when inconsistencies in the exam prevent the instructor from accurately assessing the student’s level of mastery of the knowledge and skills covered in the course.
Language(s) of evaluation
- french