• Design and Analysis of Algorithms Part 1 - Mathematical Tools and Network Problems, Fall 2021

    PhD course

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.
  • The examination will take place Monday, March 21, 2022, 13:30-(max)16: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

  • Distributed algorithms

Standard techniques

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

Homework


Lecture Slides


  • Slides are password protected!
  • The password will be announced in the first seminar.
  • November 3, 2021: [PDF]
  • November 24, 2021: [PDF]
  • December 1, 2021: [PDF]
  • December 17, 2021: [PDF]
  • January 14, 2022: [PDF]
  • January 31, 2022: [PDF]
  • February 21, 2022: [PDF]

Group Projects


(Note: This is a guideline, you can extend, and, if you can motivate it, delete parts.)

Literature

The course is self-contained, that is, the lecture notes and other course material will be enough to follow the course. For the group presentation material will be made available. Interested students may use the following books for additional self-study:
  • 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.