Explore

I/O-efficient algorithms

Approx. 10 hours to complete

Save Course

Go to Course

Course Summary

Learn about I/O-efficient algorithms in this advanced course that covers topics such as external memory models, sorting, searching, graph algorithms, and more.

Key Learning Points

Gain an understanding of I/O-efficient algorithms and their applications
Learn about external memory models and how to design algorithms for them
Explore different sorting and searching techniques for large datasets
Study graph algorithms and other advanced topics

Learning Outcomes

Design and implement I/O-efficient algorithms
Analyze and optimize algorithms for external memory models
Apply advanced sorting, searching, and graph algorithms to large datasets

Prerequisites or good to have knowledge before taking this course

Basic knowledge of algorithms and data structures
Familiarity with programming in a high-level language such as Python, Java, or C++

Course Difficulty Level

Advanced

Course Format

Online
Self-paced

Similar Courses

Advanced Data Structures
Algorithms on Strings
Graph Algorithms

Related Education Paths

Notable People in This Field

Jeff Erickson
Erik Demaine

Related Books

Description

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.

Prerequisites: In order to successfully take this course, you should already have a basic knowledge of algorithms and mathematics. Here's a short list of what you are supposed to know: - O-notation, Ω-notation, Θ-notation; how to analyze algorithms - Basic calculus: manipulating summations, solving recurrences, working with logarithms, etc. - Basic probability theory: events, probability distributions, random variables, expected values etc. - Basic data structures: linked lists, stacks, queues, heaps - (Balanced) binary search trees - Basic sorting algorithms, for example MergeSort, InsertionSort, QuickSort - Graph terminology, representations of graphs (adjacency lists and adjacency matrix), basic graph algorithms (BFS, DFS, topological sort, shortest paths) The material for this course is based on the course notes that can be found under the resources tab. We will not cover everything from the course notes. The course notes are there both for students who did not fully understand the lectures as well as for students who would like to dive deeper into the topics. The video lectures contain a few very minor mistakes. A list of these mistakes can be found under resources. If you think you found an error, report a problem by clicking the square flag at the bottom of the lecture or quiz where you found the error.

Outline

Introduction
Why I/O-efficient Algorithms
The basic I/O-model
Analyzing algorithms in the I/O-model
Analyzing algorithms in the I/O-model, II
Cache-aware versus cache-oblivious algorithms
Course notes 1.1 and 1.2
Introduction

Designing cache-aware and cache-oblivious algorithms
The matrix-transposition problem
A cache-aware algorithm for matrix transposition
A cache-oblivious algorithm for matrix transposition
Course notes 1.3
Designing cache-aware and cache-oblivious algorithms

Replacement Policies
Replacement Policies
Course notes 1.4
Replacement policies

I/O-efficient sorting
I/O-Efficient sorting, I
I/O-Efficient sorting, II
Course notes chapter 2
I/O-efficient sorting

I/O-efficient data structures
Efficient searching I: B-Trees
Efficient searching II: Buffer Trees
I/O-Efficient Priority queues
Course notes 3.1
I/O-Efficient Data Structures

Time-Forward Processing
Evaluating local functions on a DAG
Evaluating local function on a DAG: I/O-analysis
Time-forward processing
Computing maximal independent sets
Course notes 3.2
I/O-EFFICIENT FUNCTION EVALUATION ON A DAG

Summary of User Reviews

This course on I/O Efficient Algorithms has received great reviews from learners, with many praising its practical approach and clear explanations. Learners have also found the course to be a valuable resource for understanding fundamental concepts and improving their coding skills.

Key Aspect Users Liked About This Course

The course is highly practical and provides clear explanations of complex concepts.

Pros from User Reviews

Great practical approach to learning I/O efficient algorithms
Clear and concise explanations of complex concepts
Valuable resource for improving coding skills

Cons from User Reviews

Some learners may find the pace of the course to be too slow
Not suitable for beginners with no prior knowledge of algorithms
Could benefit from more interactive activities or exercises

Recommended for you

JavaScript Algorithms and Data Structures Masterclass

The Missing Computer Science and Coding Interview Bootcamp Updated in November 2018 with brand new section on Dynamic Programming!     We cover the ins and outs of Recursion....

Save Course

Introduction to Machine Learning for Data Science

A primer on Machine Learning for Data Science. Revealed for everyday people, by the Backyard Data Scientist. Course Most Recently Updated Nov/2018! ...

Save Course

Introduction to Programming with MATLAB

This course teaches computer programming to those with little to no previous experience. The design of the language makes it possible to write a powerful program in a few lines....

Save Course