Monthly Subscription Starting at AED 99 + VAT

I/O-efficient algorithms
  • Level Expert
  • المدة 10 ساعات hours
  • الطبع بواسطة EIT Digital
  • Offered by

عن

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.

الوحدات

1.1 Introduction

    • 1 Videos
Show info about module content

1 Videos

  • Why I/O-efficient Algorithms

1.2 The basic I/O-model

    • 1 Videos
Show info about module content

1 Videos

  • The basic I/O-model

1.3 Analyzing algorithms in the I/O-model

    • 1 Videos
Show info about module content

1 Videos

  • Analyzing algorithms in the I/O-model

1.4 Analyzing algorithms in the I/O-model, II

    • 1 Videos
Show info about module content

1 Videos

  • Analyzing algorithms in the I/O-model, II

1.5 Cache-aware versus cache-oblivious algorithms

    • 1 Videos
Show info about module content

1 Videos

  • Cache-aware versus cache-oblivious algorithms

1.6 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Introduction

1 Readings

  • Course notes 1.1 and 1.2

2.1 The matrix-transposition problem

    • 1 Videos
Show info about module content

1 Videos

  • The matrix-transposition problem

2.2 A cache-aware algorithm for matrix transposition

    • 1 Videos
Show info about module content

1 Videos

  • A cache-aware algorithm for matrix transposition

2.3 A cache-oblivious algorithm for matrix transposition

    • 1 Videos
Show info about module content

1 Videos

  • A cache-oblivious algorithm for matrix transposition

2.4 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Designing cache-aware and cache-oblivious algorithms

1 Readings

  • Course notes 1.3

3.1 Replacement Policies

    • 1 Videos
Show info about module content

1 Videos

  • Replacement Policies

3.2 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Replacement policies

1 Readings

  • Course notes 1.4

4.1 I/O-Efficient sorting, I

    • 1 Videos
Show info about module content

1 Videos

  • I/O-Efficient sorting, I

4.2 I/O-Efficient sorting, II

    • 1 Videos
Show info about module content

1 Videos

  • I/O-Efficient sorting, II

4.3 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • I/O-efficient sorting

1 Readings

  • Course notes chapter 2

5.1 Efficient searching I: B-Trees

    • 1 Videos
Show info about module content

1 Videos

  • Efficient searching I: B-Trees

5.2 Efficient searching II: Buffer Trees

    • 1 Videos
Show info about module content

1 Videos

  • Efficient searching II: Buffer Trees

5.3 I/O-Efficient Priority queues

    • 1 Videos
Show info about module content

1 Videos

  • I/O-Efficient Priority queues

5.4 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • I/O-Efficient Data Structures

1 Readings

  • Course notes 3.1

6.1 Evaluating local functions on a dag

    • 1 Videos
Show info about module content

1 Videos

  • Evaluating local functions on a DAG

6.2 Evaluating local function on a dag: I/O-analysis

    • 1 Videos
Show info about module content

1 Videos

  • Evaluating local function on a DAG: I/O-analysis

6.3 Time-forward processing

    • 1 Videos
Show info about module content

1 Videos

  • Time-forward processing

6.4 Computing maximal independent sets

    • 1 Videos
Show info about module content

1 Videos

  • Computing maximal independent sets

6.5 Quiz

    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • I/O-EFFICIENT FUNCTION EVALUATION ON A DAG

1 Readings

  • Course notes 3.2

Auto Summary

Explore the fascinating realm of I/O-efficient algorithms in this expert-level course, perfect for data science and AI enthusiasts. Led by a proficient instructor, this course delves into algorithms designed to handle massive datasets that exceed main memory capacity, crucial for large-scale data processing and database management. With a solid foundation in algorithms, mathematics, and basic data structures, you'll learn to navigate memory hierarchies and optimize data fetches. The course spans 600 minutes, with both Starter and Professional subscription options available, providing comprehensive resources and in-depth knowledge to enhance your algorithmic skills.

Mark de Berg
Instructor

Mark de Berg