Computer Science Seminars
Distinguished Lecture Series

Université Libre de Bruxelles
Computer Science Department


Practical information

The seminars are usually held on Thursdays or Fridays between 12:15 and 1:15PM, Campus de la Plaine.

You can receive seminar announcements by subscribing to the 'computerscience' mailing list. Help on ULB/VUB mailing lists can be found here. For more information, please contact Stefan Langerman (slanger at ulb dot ac dot be).



Thursday October 12, 2017, 12:15 PM, room: Forum G
The Cache Oblivious Model of Computation
John Iacono (New York University / ULB)

Abstract: In the standard model of computation often taught in computer science courses one identifies elementary operations and counts them in order to obtain the runtime. However, given the complexity of computing hardware, this measure often does not correlate well with actual observed runtime on a computer; accessing n items sequentially or randomly typically have runtimes that differ by several orders of magnitude. In this talk I will present the cache-oblivious model of computation, a model that was introduced by Prokop in 1999 and is relatively easy to reason with, by modeling the multilevel caches that are a defining feature of the cost of modern computation. After presenting the model, several data structure and algorithms that illustrate design techniques to develop cache-obliviously optimal structures will be presented.

The speaker is hosted by the Algorithms Group.