DM803 - Advanced Data Structures
 
Spring 2022
Kim Skak Larsen
Home
Official Course Description Pizza Meeting Presentation Midterm Evaluation Course Evaluation Attendance vs. Exam Grades Distribution Language Policy
Lectures and Exercises Literature
Exam
Schedule Contact Information
☰
Exercises
  1. Some of you have likely heard of the array doubling technique. Here we will prove that it works. We work with arrays of sizes that are powers of two. We want arrays because we want to be able to perform look-ups and updates in constant time. Now, we also want to append, i.e., extend our array by one extra entry. If the number of elements, n, is not a power of two, there are unused entries in the array and we just increment n and use the next entry. Otherwise, the array is filled up, and we allocate a new array of double the size, move all elements to the new array, and deallocate the old array (this just means that we inform the operating system that we will not use it again and so it does not count as space we are using). Define a potential function and show that we can implement append in amortized constant time. What is the space overhead?

    Now we also want to be able to shrink the array by one from the end, i.e., a reverse operation to append. It could make sense to refer to the operations as push and pop instead. Decide on a strategy for when to reallocate to a smaller array so that the space overhead is O(n) and such that you can define a potential function and show that push and pop (any mix of these) are both amortized constant.

  2. Now, we want to do the same as above, supporting push and pop, but we want all times to be worst-case instead of amortized. To that end, we must anticipate reallocation to smaller and larger arrays and get it done gradually. This will increase our space overhead, but it should still be O(n). Devise an algorithm and argue that it works. (Doing something like this is referred to as global rebuilding.) What is your space overhead?

  3. In the above, we have taken advantage of ``knowing what we are working with''. Because we know it is arrays, we could pre-allocate some extra space. Assume now that we are working on some data structure where this cannot be done (or you do not know how). All you have is a built operation. You can give it n elements, and it will return a structure to you in time O(f(n)), for some function, f (think of a construction time of O(n) or O(n log n)). We now assume that the data structure is decomposable; this means that if the elements are spread out over a number of smaller data structure of this type, then the answers we obtain from searching in each of them separately can be combined (fast) to the answer we would get, if all elements where together in one copy. Under this assumption, try to come up with some storage/rebuilding scheme such that search times increase by at most a factor log n and such that the data structure can provide insertions in time amortized O(log n) or O(log2 n), depending on whether f(n)=n or f(n)=n log n (which are the most common construction times).

 

   Data protection at SDU ▪ Databeskyttelse på SDU