News · Summary · Content · Material · Schedule · Format · Grading · Tracking · Support · Feedback · Comments · More · FAQ · Glossary
The course on Deterministic Distributed Algorithms is offered in Spring 2012, during the 4th period. The course instructor is Jukka Suomela, and the exercise sessions are held by Juho Hirvonen.
The course provides an introduction to the theory of distributed algorithms. The topics include algorithmic techniques that can be used to solve graph problems efficiently in extremely large networks, as well as fundamental impossibility results that set limits to distributed computing. No prior knowledge of distributed systems is needed, but students are expected to have an interest in algorithmic problems and a basic knowledge of discrete mathematics.
The course is worth 4 credits, and the course code is 582661. This is an advanced (Master level) course, so it is expected that the participants have a BSc degree or equivalent.
The course is not based on any textbook; course material and presentation slides will be posted on this page. Lectures and course material will be in English.
The course is an extended version of the intensive course that was given in spring 2010.
The main themes and the learning objectives are as follows. In the course exam, if you can do everything listed in the column "Approaches learning objectives", you should be able to pass the course, and if you can do everything listed in the column "Reaches learning objectives", you should be able to get the highest grade 5/5.
|Principal theme||Prerequisite knowledge||Approaches learning objectives||Reaches learning objectives||Deepens learning objectives|
|basics of discrete mathematics||apply the definitions of graph-theoretic concepts||prove connections between graph problems||apply techniques beyond elementary graph theory|
(Chapters 2 & 4)
|basic knowledge of models of computation||design simple distributed algorithms||analyse distributed algorithms||apply linear programming to design combinatorial algorithms|
(Chapters 3 & 4)
|basics of discrete mathematics||identify covering relations between graphs||construct graphs that can be used to prove negative results||derive tight inapproximability results|
|basics of discrete mathematics||describe a fast graph colouring algorithm and prove its correctness||use graph colouring as an algorithm design technique||describe modern graph colouring algorithms|
|basics of discrete mathematics||apply Ramsey's theorem to prove negative results||prove Ramsey's theorem||apply bounds on Ramsey numbers to prove lower bounds|
The course material is a short online textbook that is freely available for download:
Course registration opened on 21 February 2012 in the Ilmo system.
Lectures are given on
The exercise sessions are held on
The first lecture is on Tuesday, 13 March 2012, and the first exercise session is on 16 March. There is an Easter holiday from 5 April to 11 April. The last lecture is on Thursday, 26 April, and the last exercise session is on 27 April.
There is a course exam on 4 May 2012, and a renewal exam on 15 June 2012 (check the exam web pages for the latest information).
The course schedule is available on Google Calendar: html, ical, xml.
The course is worth 4 credits, and there are 6 full weeks of lectures plus an exam. As one credit entails approx. 27 hours of work, you are expected to work 17–18 hours each week on this course.
The emphasis is on self-study; you will learn by doing. The lectures and exercise sessions are intended to support self-study, not replace it.
The course material consists of 6 short chapters of text, and with each chapter there is a selection of exercises. On week x you are expected to do the following:
Note that you are not expected to solve all exercises. Keep track of your working hours – do not overdo it. Usually, it makes sense to start with the first exercises. However, you are welcome to skip exercises that look utterly trivial to you, and focus on more interesting problems. If you get stuck, remember that help is available almost daily.
Below is the suggested weekly routine. You are free to adapt it to your needs, but keep in mind that the lectures and exercise sessions are planned so that they support this routine. In particular, make sure that you have read the relevant chapter of the course material before Tuesday's lecture.
|Mon||4 hours||self-study||Read Chapter x, have a look at the exercises.|
|Tue||2 hours||lectures||Review of Chapter x. Discussion. Examples.|
|Wed||3 hours||self-study||Exercises. Update course tracking.|
|Thu||2 hours||lectures||More in-depth material related to Chapter x. We will discuss possible solutions to selected exercises.|
|2 hours||self-study||Exercises. Update course tracking.|
|Model solutions to selected exercises, discussion. Update course tracking.|
The lectures and exercise sessions will be adapted based on the information in the course tracking system. Hence to make sure that the sessions are as useful to you as possible, remember to update the course tracking system regularly.
The beginning of the first week will be a bit more relaxed, as the material focuses on reviewing concepts from graph theory. Hence if you are only reading these instructions after the first lecture, you will still have time to catch up. However, do not expect that the exercises of the first week are trivial…
If you realise that you have taken too many courses during the 4th period, remember that you can abuse the Easter holiday for load balancing. There will be one full week without any lectures or exercise sessions in April.
The grading is based solely on the course exam, using the usual scale of 1–5. If you pass the exam, you pass the course – there are no other requirements.
In particular, you will not get any credits or points from the exercises. However, most probably
For an average student, 4 × 27 hours of studying during the course will be sufficient in order get an average grade in the exam.
There is an online course tracking system. In the system, you are expected to report your progress. All reports are anonymous.
The course tracking system serves the following purposes:
In the course tracking system, you will report your progress with each exercise using the following codes:
|A||The problem looks straightforward. I did not solve it but I am confident that I would be able to solve it in the exam.|
|B||I solved the problem by myself and I believe the solution is correct. I am confident that I would be able to solve it in the exam.|
|C||I needed some help from other students or course instructors, but I believe I have a correct solution now and I understand all parts of it. I am confident that I would be able to solve this problem in the exam.|
|D||I have tried hard, but I do not have a correct solution yet. I need some help.|
|E||I am still working on it…|
|X||I will not have time to solve this problem, as I have already spent approx. 18 hours/week on this course.|
|(empty)||I have not yet had a look at it.|
If you have registered for the course, you should have received detailed information by email; if this is not the case, please contact the course instructor.
The following online forums are available:
You do not need to follow these forums; all essential information will be provided on this web page. Nevertheless, it might be a good idea to join the Google Groups forum or try out IRC well in advance before the course begins, just in case you should need quick help with the exercises.
You can also email Jukka Suomela or Juho Hirvonen if you have any questions!
If you have any comments or suggestions before or during the course, feel free to email the course instructor or drop a note on the online forums.
After the course, everyone is expected to submit course feedback using the course feedback system. Course feedback is anonymous.
I will publish a summary of the course feedback on this web page, and I will also comment on it here.
The key statistics of the course are as follows:
The following table summarises the numerical course feedback (scale from 1 = disagree to 5 = agree).
|Course objectives were clear||·||2||·||444||555555|
|Course material supported learning||·||·||3||444||555555|
|Course activities supported learning||·||·||33||4444||5555|
|Exams and grading measured learning||·||·||3||4444||555|
|Lots of work||·||2||33||4||555555|
Here are selected (adapted, abbreviated, translated, and anonymised) fragments of the free-form course feedback, both from the feedback form and from the emails that I received.
First of all, many thanks to all of you who provided feedback, and in particular, thanks for your kind, supportive, and helpful comments! I really appreciate all kinds of feedback.
Here are my own interpretations of the main points of the feedback, with some comments:
I would like to comment the last point – workload – in more detail. Let us first have a look at the background. The Finnish legislation (Valtioneuvoston asetus yliopistojen tutkinnoista 794/2004, 5 §) explicitly states that one full year of studies equals 1600 working hours, which equals 60 credits; many other European countries have a very similar system.
Please note that I as a course instructor cannot really change any of this. In any case, 1600 hours per year sounds like a very reasonable number to me. For example, if you do 40 hours of studies each week, you can enjoy 12 full weeks of holidays each year.
Now if we do the math, we conclude that a 4-credit course entails approximately 107 hours of studies. Even if we allocate some working hours for the exam, we will have approximately 100/6 ≈ 17 hours of studies each week during a 6-week lecture course. This number seemed to come as a surprise to most of the students.
Unfortunately, this just happens to be the way our system works; I did not make up the numbers. Of course I could organise a course that is worth only 2 credits, and then I would expect only approximately 8 hours of studies each week, but I am not sure if the students would be happy with this approach, either.
I will try to provide some words of general advice, though. Please note that the total length of the four teaching periods is only 28 weeks, including the exam weeks. The idea is not that you compress a full working year in just 28 weeks! If you tried to do that, you would certainly be in trouble, struggling with 60-hour weeks. A simple solution is to study on your own outside the usual teaching periods – this way you can enjoy relaxed 40-hour working weeks, yet you will still have a long summer holiday.
I hope this at least clarifies the situation, even if it does not actually help that much with the workload… Once again, many thanks to all of you for taking part in the course! Have a nice summer!
There will be a seminar course on distributed algorithms in autumn 2012.
Master's thesis topics are available from the course instructor.
|regular graph||säännöllinen verkko|
|spanning subgraph||virittävä aliverkko|
|induced subgraph||indusoitu aliverkko|
|connected component||yhtenäinen komponentti|
|radius-r neighbourhood||r-säteinen ympäristö|
|connected graph||yhtenäinen verkko|
|independent set||riippumaton joukko|
|dominating set||dominoiva joukko|
|edge dominating set||dominoiva kaarijoukko|
|maximal independent set||maksimaalinen riippumaton joukko|
|maximum independent set||maksimikokoinen riippumaton joukko,|
suurin riippumaton joukko
|minimal vertex cover||minimaalinen solmupeite|
|minimum vertex cover||minimikokoinen solmupeite,|
|domatic partition||domaattinen ositus|
|edge domatic partition||domaattinen kaariositus|
|bipartite graph||kaksijakoinen verkko|
|perfect matching||täydellinen pariutus|
|directed graph||suunnattu verkko|
|undirected graph||suuntaamaton verkko|
|distributed algorithm||hajautettu algoritmi|
|distributed computing||hajautettu laskenta|
|distributed system||hajautettu järjestelmä|
|deterministic algorithm||deterministinen algoritmi|
|local neighbourhood||paikallinen ympäristö|