PhD course: Design and Analysis of Algorithms Part 1 - Mathematical tools and Network problems, spring 2017.

This course is the first in a series of three, where each course can be taken independently:
Part 1: Mathematical Tools and Network Problems
Part 2: Approximation and Online Algorithms (homepage for part 2)
Part 3: Computational Geometry
Parts 2 and 3 will be offered in the following terms.

Organisation

  • Lecturer: Christiane Schmidt , Valentin Polishchuk
  • The first seminar is on March 9, 2017, 09:00-13:00. Seminar 2 on March 30, 13:00-17:30, seminar 3 on April 10 09:00-13:00, seminar 4 on June 7 13:00-18:00. The first student presentation seminar will be on distributed algorithms on May 11 13:00-17:00, and the student presentation seminar on matroids on May 24 9:00-13:00.
  • The course will consist of 7 seminars, the first in the week of February 20. The course will run until the end of May/beginning of June. Most of the seminars will be lectures/problem solving sessions led by me. 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.

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

Current stuff.

  • There is a nice overview on proof techniques, all with a common example, from Estie Arkin available [here].
  • Homework set #1 is online.
  • Welcome to the class!

Group Projects

(Note: This is a guideline, you can extend, and, if you can motivate it, delete parts.)
  • 1.Greedy and Matroid Duality (Proof of the Greedy algorithm (with necessary definitions); Some applications of the Greedy algorithm; Matroid duality; Greedy and matroid duality)
  • 2. Matroid Union, Matroid Intersection and Applications (What is a matroid union? (2 matroids on a common ground set, n matroids); Show that the resulting construction in a matroid; Given an example/apply this; What is a matroid intersection?; Give an example)
  • 3. Distributed Vertex Coloring and Leader Election (Colouring trees (up to 3 colors); What is leader election?; Leader election in an asynchronous ring; Leader election in a synchronous ring)
  • 4. Distributed Tree Algorithms (Broadcast; Converge cast; Distributed Dijkstra and MBF; Distributed MST construction)

Mailing list.

Information will be made available via the mailinglist, contact christiane.schmidt(at)liu.se to be added to the list.

Homework and Lectures.

  • The current homework sets can be found here.
  • Slides/notes can be downloaded from this site - Slides are password protected!
  • The password will be announced in the first seminar.

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.