Complete version of lecture notes

I have added a section covering the material for the next lecture to the notes, which means that we now have a first complete version. Based on your input, I have also corrected and extended sections 6.1-6.3 on makespan scheduling. Further suggestions are welcome.

Best regards,

Carsten

Lecture notes updated and next mandatory exercise

Regarding the next mandatory exercise, I was asked what n/i-approximation means. Please see page 20 in the updated lecture notes and put r=n/i there.

Best regards,

Carsten

Master Thesis Defense in Algorithms

Morten Støckel, who took Algorithms for Massive Data Sets, defends his thesis on thursday March 31. See the full announcement here . This a good chance to see what a master thesis in algorithms could consist of.

\Philip

Remarks on Mandatory Exercise (update)

For your solution of the mandatory exercise it might be convenient to assume that the weights are sorted as w_1 >= w_2 >= … >= w_n. This does not lose generality since the (1+1) EA does not care (more precisely, it has the same stochastic behavior) when you rename the bits.

Note that the exercise considers a class of functions, which includes, amongst others, OneMax and BinVal. So you cannot assume that all weights are different. As a matter of fact, you are not allowed to change the algorithm depending on the function.

Finally, make sure to prove that your partition is fitness-based (in particular verify condition 4 from the definition) and prove that for every search point from a level there is a way to improve to a higher level. Most likely you need an argument like: If the search point is in level L_i (which might be defined according to the fitness only), then I still know that the search point has this-and-that kind of structure, and therefore there is a mutation that results in a search point from a higher level.

Best regards,

Carsten

Fitness-based partition for BinVal

In today’s lecture, it was asked whether the fitness-based partition for BinVal presented on page 19 of the slides

(L_i:=\{x\mid 2^{n-1} + 2^{n-2} + \dots + 2^{n-i} \le \textsc{BinVal}(x)
< 2^{n-1} + 2^{n-2} + \dots +  2^{n-i}+ 2^{n-i-1}\})

is correct or whether the last -1 should be a +1. I think the definition is correct since the powers of 2 are listed in decreasing order.

Best regards,

Carsten

Office hours Carsten

My office hours (until further notice) take place on Thursdays from 12-13 in my office (322/124).

Best regards,

Carsten