Office hours
Inge and I will both have office hours Friday at 12.00-13.00.
\Philip
Week 13
For the last session in the course (week 13), we start at 10.15 in the exercise room.
Office hours
This week I will not be here for office hours. I’ll be there next week on Thursday at 12-13 as usual. Inge will have office hours this week on friday at 12-13 as usual.
\Philip
Yet another bug in mandatory exercise 5
The query time should be O(occ log log n + log n), i.e., with an additional + log n needed for the special case when occ log log n is much smaller than log n. The exercises are updated accordingly. Thanks to Jesper for finding this error!
\Philip
Week 5 mandatory exercise update.
I noticed that the fixed typo mentioned in an earlier post actually makes mandatory exercise 5 unintentionally hard. I have updated the exercise to avoid this problem and the exercises now explicitly calls for a solution using O(occ log log n) time and O(n log n). This is a major hint, that I’m sure you can use to creatively come up with some ideas if you are stuck in the exercise.
Technically, the comparison-based model requirement is not needed with this new formulation and is therefore also removed. However, using word RAM techniques will likely not help you to achieve the desired bounds. Comparison based techniques are quite sufficient.
\Philip
Office hours.
For clarification, my office hours are thursday 12-13. Last week was an exception due to travelling.
\Philip
Updated exercises for week 5
As discussed the exercises (and in particular the mandatory exercise) for week 5 have been updated. Please lose the old version.
\Philip
Guest Lecture, Exercises, and Slides.
As mentioned last week Stephen Alstrup will give a guest lecture on monday on labeling schemes and the nearest common ancestor problem. As a supplement I have uploaded my slides on this topic. The exercises are also available.
\Philip
cawidtu
ingeli
philipbille
leave a comment