All exams are now complete and 28 students succesfully completed the course. Congrats to all!

\Philip

Leave a reply

All exams are now complete and 28 students succesfully completed the course. Congrats to all!

\Philip

Here’s an extra hint for question 2) in the mandatory exercise: For a specific index position i, and a length k, we wish to find all the dual substrings of T of length 2k, where the first half intersects/spans position i in T. You can argue that these dual substrings will all start in a consecutive range [a,b] in T, and that this range can be found using two constant-time LCE queries (one in each direction). Consequently, by repeating for all k, we can output all the dual substrings where the first half intersects position i in O(n+occ) time.

If you have questions about the lecture or the mandatory exercise, you are welcome to come by my office in 322/008 tomorrow (Friday) between 12.00 and 12.30.

– Hjalte

Next monday we do a round up, answer questions about the oral exam, and talk about thesis and project in algorithms. **We start at 10.00 in the auditorium.**

Somebody asked what “finding all k-nearly dual substrings in T” means. Just to be completely clear: This means reporting the *positions** *of the substrings of T, which are k-nearly dual strings. That is, output all pairs (i,j), i<j such that T[i..j] is a k-nearly dual string.

– Hjalte

There is feedback for exercise 8 on campusnet.

Exercise 6 is also corrected and you can get it in my office today between 12.30 and 13 or on Monday at the lecture.

-Inge

As mentioned today, I’ve moved office hours this week to Friday 12:30-13:00.

\Philip

Due to illness both the class (both lectures and exercises) are canceled tomorrow.

-Inge