Operations on data become more expensive when the data item is located higher in the memory hierarchy. An operation on data in CPU registers is roughly a million times faster than an operation on a data item that is located in external memory that needs to be fetched first. These data fetches are also called I/O operations and need to be taken into account during the design of an algorithm. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. We will work with a simplified memory hierarchy, but the notions extend naturally to more realistic models.
提供:


I/O-efficient algorithms
EIT Digitalこのコースについて
提供:

EIT Digital
EIT Digital is a European education and innovation organisation with a mission to foster digital technology innovation and entrepreneurial talent for economic growth and quality of life. By linking education, research, and business, EIT Digital empowers digital top talent for the future.
シラバス - 本コースの学習内容
Introduction
In this module we give an introduction to the course I/O-efficient algorithms. We discuss the so-called I/O-model, which consists of an internal memory of limited size, an external memory of unlimited size and where data transfer between these two happens in blocks of a given size. We give a simple example showing that the actual running time of an algorithm working on data in external memory is greatly influenced by its I/O-behavior. Finally, we discuss the basics of analyzing algorithms in the I/O-model.
Designing cache-aware and cache-oblivious algorithms
In this module we discuss two techniques to design I/O-efficient algorithms, using the matrix-transposition problem as a running example. The first technique is a "tile-based" approach and leads to a cache-aware algorithm. The second technique uses a recursive approach and leads to a cache-oblivious algorithm.
Replacement Policies
When we want to read something from external memory while the internal memory is full we need to make room by evicting a block from internal memory. The block which should be evicted is decided by the replacement policy. In this module we introduce LRU and some other some well-known replacement policies, and investigate the I/O-efficiency of LRU compared to an optimal replacement policy.
I/O-efficient sorting
In this module we analyze the I/O-efficiency of MergeSort and discuss how to adapt it to make it more I/O-efficient.
レビュー
- 5 stars66.03%
- 4 stars26.41%
- 3 stars5.66%
- 2 stars1.88%
I/O-EFFICIENT ALGORITHMS からの人気レビュー
Really like the course. Though it's difficult and challenging, I managed to understand the concept. I will keep practicing.
Everything was clearly explained and the questions were quite intuitive and checking my knowledge. More examples for different scenarios too would help us a lot to learn more.
The course is really good and the course material is also amazing. I highly reccomend it provided you have an interest in this specialization.
The excercises and assignments helped in undertanding the concepts much better. Also as this course content can't be found easily at one place this really helped. Thank you
よくある質問
いつ講座や課題にアクセスできるようになりますか?
修了証を購入すると何を行えるようになりますか?
学資援助はありますか?
さらに質問がある場合は、受講者ヘルプセンターにアクセスしてください。