First lecture:

Thuesday

5.3.2024   12:00 - 13:30, room: P215

In this lecture basic skills and techniques will be elaborated which are relevant to simplify formulas related to enumeration, in particular, to carry out the average and worst case complexity analysis of algorithms. The content of the lecture can be summarized by the following key words:

• algorithmic treatment of formal power series
• c-finite and holonomic functions/sequences
• recurrence solving
• basic aspects of asymptotics
• symbolic summation

A major emphasis of the lecture is to present the basic notions, to develop the basic ideas of the underlying algorithms and to put computer algebra into action for concrete examples.

Many of the topics discussed in the lecture can be found in the books

• "Concrete Mathematics - A Foundation for Computer Science" by R.L.Graham, D.E.Knuth und O.Patashnik (Addison-Wesley, 1994)
• "The Concrete Tetrahedron" by Manuel Kauers and Peter Paule (Springer Wien, 2011).

Requirements: Basic knowledge from analysis and linear algebra.

Grading: The grades are given by oral exams (30 minutes) that are schelduled in July on an indiviual basis. I will also offer the possibilty of oral exams in September or later depending on the needs of the students.

The lecture notes will be enhanced step wise and will be found here: LectureNotes.pdf; a supplementing Mathematica notebook can be found here.

In case that some content is unclear, feel free to contact me. I will try to answer all your questions, and will incorporate the answers also into the lecture notes.

Exercises

The exercises will be stated in the lectures in form of "homeworks" and will be discussed one (or more) weeks later in the exercise class. Further details will be discussed in the lecture and exercise class. The first exercise class will take place in P215 on March 12.
Exercise instructor: Koustav Banerjee (KoustavDOTBanerjeeATriscDOTjkuDOTat)


The posed exercises are collected in Exercises.pdf.