This course is the first in a series of three, where each course can be taken independently:

Part 1: Mathematical Tools and Network Problems (

[DAA1, 2019],

[DAA1, 2017])

Part 2: Approximation and Online Algorithms (

[DAA2, 2018])

Part 3: Computational Geometry (

[information page])

Parts 2 and 3 will be offered in the other terms.

#
Organisation

- Lecturer: Christiane Schmidt
- The course will be taught online via zoom.
- The course will start in the end of October/beginning of November, 2021.
- The course will consist of 7 seminars.
Most of the seminars will be lectures/problem solving sessions led by me, Christiane.
Moreover, all students have to prepare a group presentation (on topics from Distributed Algorithms, possibly, depending on the number of participants, on Matroids).
In addition, homework assignments will be given.
These will not be marked, but for each student 2 assignments are picked
for presentation, and the requisite of 50% of homework translates to a
sufficiently correct and complete presentation of at least one solution.
The grade will be based on the exercises assigned during the course and one exam per part.
- Information will be made available via the mailinglist, contact christiane.schmidt(at)liu.se to be added to the list.
- The first seminar is on Wednesday, November 3, 2021, 14:45-18:45 on zoom.
- The second seminar will take place Wednesday, November 24, 2021, 14:30-18:30 on zoom.
- The third seminar will take place Wednesday, December 1, 2021, 14:45-18:45 on zoom.
- The fourth seminar will take place Friday, December 17, 2021, 12:00-16:00 on zoom.
- The fifth seminar will take place Friday, January 14, 2022, 13:00-17:00 on zoom.
- The sixth seminar will take place Monday, January 31, 2022, 13:00-17:00 on zoom.
- The seventh seminar will take place Monday, February 21, 2022, 13:00-17:00 on zoom.

# Current Stuff

- Welcome to the class!
- There is a nice overview on proof techniques, all with a common example, from Estie Arkin available [here].

# Course Content

#
Topics

- Basic notions of graph theory
- Asymptotic growth of functions and big-O notation
- Sorting
- Tree algorithms
- Paths in graphs
- Discrete network flows
- Covering and packing (IS, coloring, in particular, distributed)

#
Algorithmic approaches

#
Standard techniques

- Divide-and-Conquer
- Dynamic Programming
- Greedy Algorithms