- Lecturer: Christiane Schmidt
- Course start on October 14, 2019.
- 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.
- The first seminar is on Monday, October 14, 2019, 13:00-17:00 in room SP6225.
- The second seminar will take place Thursday, November 14, 2019, 13:00-17:30 in room SP6225.
- The third seminar will take place Monday, November 18, 2019, 13:00-17:00 in room SP6225.
- The fourth seminar will take place Thursday, December 12, 2019, 13:00-17:30 in room SP6225.
- The fifth seminar will take place Thursday, January 23, 2020, 13:00-17:30 in room SP6225.
- The sixth seminar will take place Monday, February 10, 2020, 13:00-17:00 in room SP7226.
- The seventh seminar will take place Friday, February 14, 2020, 13:00-16:00 in room SP6225. In this seminar the group projects will be presented: Nisha, Kristofer: Greedy and Matroid Duality; 2. Anastasia, Manos: Distributed Vertex Coloring and Leader Election.
- The examination will take place Monday, March 23, 2020, 15:15-(max)17:30 in room SP6225.
- Basic notions of graph theory
- Asymptotic growth of functions and big-O notation
- Tree algorithms
- Paths in graphs
- Discrete network flows
- Covering and packing (IS, coloring, in particular, distributed)
- Distributed algorithms
- Dynamic Programming
- Greedy Algorithms
- Welcome to the class!
Information will be made available via the mailinglist, contact christiane.schmidt(at)liu.se to be added to the list.
- •Bernhard Korte, Jens Vygen: Combinatorial Optimization, Theory and Algorithms. Fourth Edition, 2008, 660 pages, Springer Verlag.
- • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, Third Edition, 2009, 1312 pages, MIT Press.
- •Ravindra K. Ahuja, Thomas L. Magnanti , James B. Orlin: Network Flows: Theory, Algorithms and Applications. 1993, 846 pages, Cisco Press.