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 数字課程信息
提供方

EIT 数字
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 stars67.27%
- 4 stars25.45%
- 3 stars5.45%
- 2 stars1.81%
來自I/O-EFFICIENT ALGORITHMS的熱門評論
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 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
Really like the course. Though it's difficult and challenging, I managed to understand the concept. I will keep practicing.
The course is really good and the course material is also amazing. I highly reccomend it provided you have an interest in this specialization.
常見問題
我什么时候能够访问课程视频和作业?
我购买证书后会得到什么?
有助学金吗?
還有其他問題嗎?請訪問 學生幫助中心。