Distributed Graph Algorithms

 

First things first: there will be no lecture on June 20, and also no exercise class. In other words, you will have a full week for looking at some of the course content again or catching up with some of the material in case you missed a lecture or exercise class. Make use of it!

As we had some more interactive parts in the last lectures, the content covered in the lectures is currently not entirely synchronous with the lecture notes that are available for the respective lectures. In particular, in the last lecture (May 23) we covered Section 3.2 of Lecture Notes 4 and Section 1 of Lecture Notes 5. (When asked in the exercise class, I said something different, that's why I'm mentioning it explicitly.)

Lastly, for everyone who missed it: in order to give a bit of encouragement for really working on the exercises and to increase participation in presenting the solutions, we will only provide written solutions for those questions for which some of you present a solution (or at least the crucial ideas leading to the solution) during the exercise class. That already worked nicely in the last exercise class, keep it up!

 

 

Here are some updates on various topics.

The exam dates have been fixed. The exam will take place on Tuesday, August 30, 9:00-12:00. The re-exam is scheduled for Friday, October 7, 9:00-12:00.

As mentioned in the lecture, some resources (books, lecture notes from other courses) have been added to the webpage, available here.

For the time being, we will also provide at least some solutions for the exercises (again, here). They might not be fully-fledged solutions with all details, but they should suffice to remind you of what we discussed in the exercise class. They are intended precisely for this purpose, please don't consider them as a substitute for solving the exercises yourself. Being able to follow a solution presented to you and coming up with a solution yourself are two entirely different things, please don't make the mistake of assuming that the former suffices.

As you may have noticed, also the lecture notes and slides for Lecture 2 have been added in the meantime. We will usually make the slides available before the respective lecture, in case you want to add some notes to the slides during the lecture. As always, some of these resources might be slightly updated at some point, e.g., to eliminate mistakes or better reflect the actual content covered during the lecture.

The exercise sheet for Lecture 2 is also out now. Please note that an exercise question about lower bounds has been added on Monday evening, so please check whether you have the updated version.

That's all for now, see you next Monday!

Thanks everyone for attending the first lecture and tolerating the technical mishaps! The lecture notes, slides (slightly edited), and the exercise sheet for Lecture 1 are all available here. Please note that for some lectures the content of the respective lecture notes might not be exactly aligned with the content that we manage to cover in that lecture (for instance, the lecture notes for Lecture 1 cover some content that we will only get to in Lecture 2). Regarding the exercise sheet, the "algorithm by Cole and Vishkin" mentioned in Exercise 1 is simply the 3-coloring algorithm we saw in the lecture.

Apologies again for the technical issues we had today. As the source of the troubles were (merely) insufficiently charged transmitters and receivers, we can hope for a lecture without any technical problems next Monday.