EIT Digital

I/O-efficient algorithms

Taught in English

Some content may not be translated

7,760 already enrolled


Gain insight into a topic and learn the fundamentals

Mark de Berg

Instructor: Mark de Berg


(59 reviews)

Advanced level
Designed for those already in the industry
9 hours to complete
3 weeks at 3 hours a week
Flexible schedule
Learn at your own pace

Details to know

Shareable certificate

Add to your LinkedIn profile


6 quizzes

See how employees at top companies are mastering in-demand skills


Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV

Share it on social media and in your performance review


There are 6 modules in this course

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.

What's included

5 videos1 reading1 quiz

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.

What's included

3 videos1 reading1 quiz

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.

What's included

1 video1 reading1 quiz

In this module we analyze the I/O-efficiency of MergeSort and discuss how to adapt it to make it more I/O-efficient.

What's included

2 videos1 reading1 quiz

In this module we introduce some I/O-efficient data structures: B-trees and buffer trees, and an I/O-efficient priority queue based on buffer trees.

What's included

3 videos1 reading1 quiz

In this module we discuss time-forward processing, a technique that can be used to evaluate so-called local functions on a directed acyclic graph.

What's included

4 videos1 reading1 quiz


Instructor ratings
4.7 (26 ratings)
Mark de Berg
EIT Digital
2 Courses12,454 learners

Offered by

EIT Digital

Recommended if you're interested in Algorithms

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 59


59 reviews

  • 5 stars


  • 4 stars


  • 3 stars


  • 2 stars


  • 1 star



Reviewed on Nov 5, 2019


Reviewed on May 8, 2022


Reviewed on Feb 28, 2022

New to Algorithms? Start here.


Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions