I/O-efficient algorithms
- Offered byCoursera
I/O-efficient algorithms at Coursera Overview
Duration | 10 hours |
Start from | Start Now |
Total fee | Free |
Mode of learning | Online |
Difficulty level | Advanced |
Official Website | Explore Free Course |
Credential | Certificate |
I/O-efficient algorithms at Coursera Highlights
- Earn a shareable certificate upon completion.
- Flexible deadlines according to your schedule.
I/O-efficient algorithms at Coursera Course details
- 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.
I/O-efficient algorithms at Coursera Curriculum
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