0;115;0c Algorithmic Combinatorics 2021S

Algorithmic Combinatorics

This semester the course is held online in asynchronous mode. Videos, lecture notes, and exercises are posted here during the semester. If there are open questions, please email to Veronika Pillwein. Questions and answers will be posted here anynomously for everyone to share. The lecture will be in English. There will be a written exam at the end of the semester. The final exam will be held online and the exam will be made available at the course's Moodle page.

On Monday, June 14, 2021 from 15:30-17:00 Thursday, July 2, 2021, from 15:00-16:00 I will be in the ZOOM room

https://jku.zoom.us/j/96735211847?pwd=NWVaMmx1OStrV3laQjlhNjdQNjgvUT09, Meeting-ID: 967 3521 1847, Password: 485784
to answer questions on the lecture, exam, etc.

The final exam is scheduled on Monday, July 5, 2021 from 15:30-17:00. There will be extra time to scan and upload the exam. Registration for the exam is mandatory until Friday, July 2, 2021 midnight.

The second appointment for the final exam is on Thursday, September 16, 2021 from 14:00-15:30 in HS5. Registration for the exam is mandatory until September 14, 2021. Since this is an in-person exam, the standard "3G" proofs (Covid-testing result, -vaccination proof) needs to be presented. Please come to the lecture room in time to be able to conduct this procedure. Lecture notes and hand written notes can be brought to the exam.

On the exam day: If no exam is handed in before the time expires, there is no grade and no consequence. Every submitted exam will be graded.

The upload has to be a single pdf-file that is named "Lastname-Matrikelnummer.pdf".

The two basic rules for submissions are: don't cheat and show all your work (answers without derivation and/or explanation will not be counted).

During the exam time, I will be available in the ZOOM room mentioned above to answer questions.

Update in lecture notes:

The learning goal is to develop basic skills and techniques which are relevant to problem solving when dealing with formulas related to enumeration, in particular, for the analysis of algorithms.

The course follows the book "The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates" by Manuel Kauers and Peter Paule. Its preface starts with

There are problems in mathematics which are so hard that they remain open for centuries. But many problems are not of this type. Often, being able to solve a problem just depends on knowing the right technique. This book is a book on techniques. More precisely, it is a book on techniques for solving problems about infinite sequences. Some of these techniques have belonged already to the repertoire of Euler and Gauss, others have been invented only a couple of years ago and are best suited for being executed in a computer algebra system.
A major emphasis of the lecture is on putting computer algebra into action. Recently developed algorithms will be discussed, for instance, the Steele-prized summation algorithm by Zeilberger. Many of the topics discussed in the lecture can also be found in the book "Concrete Mathematics - A Foundation for Computer Science" by R.L.Graham, D.E.Knuth und O.Patashnik (Addison-Wesley, 1994). A citation from its preface:
...But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics. More concretely, it is the controlled manipulation of mathematical formulae, using a collection of techniques for solving problems. Once you ... have learned the material in this book, all you will need is a cool head, a large sheet of paper, and fairly decent handwriting in order to evaluate horrendous-looking sums, to solve complex recurrence relations, and to discover subtle patterns in data. You will be so fluent in algebraic techniques that you will often find it easier to obtain exact results than to settle for approximate answers that are valid only in a limiting sense.
The major topics in these book include sums, recurrences, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods. The emphasis is on manipulative technique rather than on existence theorems or combinatorial reasoning; the goal is for each reader to become as familiar with discrete operations (like the greatest-integer function and finite summation) as a student of calculus is familiar with continuous operations (like the absolute-value function and infinite integration)."

Requirements: Basic knowledge from analysis and linear algebra.
Note: Within the frame of this lecture various topics for a diploma thesis are offered.

Veronika Pillwein


  1. Introduction, Selection Sort
  2. Quick Sort, part 1
  3. Quick Sort, part 2
  4. Quick Sort, generating function
  5. Quick Sort, asymptotics
  6. Formal power series
  7. Formal power series: derivation
  8. Formal power series: integration and division
  9. Formal power series: convergence and composition
  10. Formal power series: factorials, transfer principle, exponential generating function
  11. Formal power series: bivariate formal power series
  12. Formal power series: Stirling numbers of the first and second kind
  13. C-finite sequences: definition, Fibonacci numbers: definition and generating function
  14. Fibonacci numbers: matrix recursion, Cassini's identity, Euler-Binet formula
  15. Properties of C-finite functions: closed form and generating function
  16. Closure properties satisfied by C-finite functions
  17. Hypergeometric sequences: definition, generating function, asymptotics
  18. Holonomic universe: definition, properties, part 1
  19. Holonomic universe: definition, properties, part 2
  20. Holonomic universe: plane binary trees, Catalan numbers
  21. Mathematica software demo: closure properties, guessing accompanying files: Mathematica Notebook pdf-version of MMA-nb
  22. Polynomial solutions of holonomic recurrences: derivation of the algorithm, part 1
  23. Polynomial solutions of holonomic recurrences: algorithm and example, part 1
  24. Polynomial solutions of holonomic recurrences: example, part 2
  25. Summation: polynomial sequences
  26. Summation: C-finite sequences, part 1
  27. Summation: C-finite sequences, part 2
  28. Summation: C-finite sequences, example
  29. Summation: C-finite sequences, example dominoe covering
  30. Summation: hypergeometric sequences, part 1
  31. Summation: hypergeometric sequences, part 2
  32. Summation: Gosper's algorithm and example
  33. Summation: Zeilberger's algorithm - introduction
  34. Summation: Zeilberger's algorithm - derivation part 1
  35. Summation: Zeilberger's algorithm - derivation part 2
  36. Mathematica software demo: Gosper's algorithm
  37. Mathematica software demo: Zeilberger's algorithm accompanying files: Mathematica Notebook pdf-version of MMA-nb
  38. Hypergeometric solutions to holonomic recurrences: algorithm
  39. Hypergeometric solutions to holonomic recurrences: example
  40. Hypergeometric solutions to holonomic recurrences: factorization of operators
  41. Mathematica software demo: Hyper (Petkovsek's algorithm) accompanying files: Mathematica Notebook pdf-version of MMA-nb
  42. Rook walks: a bivariate example, part 1
  43. Rook walks: a bivariate example, part 2
  44. Asymptotics of holonomic sequences
  45. Mathematica software demo: Asymptotics accompanying files: Mathematica Notebook pdf-version of MMA-nb
  46. Summary: recurrences, generating function, example
  47. Summary: non-holonomic, Bell numbers
  48. Summary: summation


Every week a new set of exercises is posted here on Monday. A pdf of the solution should be emailed to Silviu Radu at your earliest convenience, but no later than the coming Monday at 18:00. To get the best possible grade, one should solve half of the exercises. These solved exercises should be distributed on the whole period and not concentrated on a single period of time.

Issue DateDownloadMaterialDue Date
08.03.2021exercises-01.pdfvideos 1-315.03.2021
15.03.2021exercises-02.pdfvideos 4-722.03.2021
22.03.2021exercises-03.pdfvideos 8-912.04.2021
12.04.2021exercises-04.pdfvideos 10-1219.04.2021
19.04.2021exercises-05.pdfvideos 13-1526.04.2021
26.04.2021exercises-06.pdfvideos 16-1703.05.2021
03.05.2021exercises-07.pdfvideos 18-2010.05.2021
10.05.2021exercises-08.pdfvideos 22-2517.05.2021
17.05.2021exercises-09.pdfvideos 26-2931.05.2021
31.05.2021exercises-10.pdfvideos 30-3207.06.2021
07.06.2021exercises-11.pdfvideos 33-3714.06.2021
14.06.2021exercises-12.pdfvideos 38-4121.06.2021
21.06.2021exercises-13.pdfvideos 42-4528.06.2021