Selected Topics in Algorithms, Summer Term 2009

Organization

The lecture on Monday is in Room 024, MPI Building, the lecture on Friday is in Lecture Hall 3, Informatik Building.

The first lecture will take place on Friday, April 24th. There will be no lectures on May 1st (holiday) and May 4th,

The discussion sessions will be integrated into the lectures.

Guest Speakers

I will organize guest speakers for these days.

Pascal Schweitzer will teach on June 8th and June 15th about Graph Isomorphism. He wrote his PhD-thesis on the subject. He will defend his thesis in July.

Exam

Wiki of the Course

Future Courses

Thesis Topics

• Integral Cycle Bases

Contents, Forthcoming

• Certifying Algorithms

I will start teaching on this subject on June 22nd. There will be a handout. The handout is a ``paper under construction'' and therefore will not be put on the web-page of the course.

• Root Isolation of Polynomials

  I will base my lectures on the papers
  • New Bounds for the Descartes Method,
  • A Deterministic Descartes Algorithm for Real Polynomials
  • Complexity of Real Root Isolation using Continued Fractions

• Literate Programming

Contents, Covered

• Cycle Bases in Graphs

  I will base my lectures on
  • the survey Cycle Bases in Graphs: Characterization, Algorithms, Complexity, and Applications and
  • the paper Breaking through the $O(m^2 n)$ Barrier for Minimum Cycle Bases
  • additional course notes
    • Notes for May 8th and May 11th
    • Unique Shortest Paths
    • NP-Completeness of Fundamental Cycle Basis Problem
    • An ILP for Minimum Integral Bases
  • NP-completeness of mininim weight fundamental cycle basis problem.
    • Johnson et al., Networks 1978
    • Deo et al., ACM Transactions on Mathematical Software, 1982

Exercise Sheets

• Exercise Sheet 1
• Exercise Sheet 2
• Exercise Sheet 3
• Exercise Sheet 4
• Exercise Sheet 5
• Exercise Sheet 6
• Exercise Sheet 7
• Exercise Sheet 8