English

Introduction to Algorithms - A Minicourse on Dynamic Multithreaded Algorithms

Abstract: This tutorial teaches dynamic multithreaded algorithms using a Cilk-like [11, 8, 10] model. The material was taught in the MIT undergraduate class 6.046 Introduction to Algorithms as two 80-minute lectures. The style of the lecture notes follows that of the textbook by Cormen, Leiserson, Rivest, and Stein [7], but the pseudocode from that textbook has been �Cilki�ed� to allow it to describe multithreaded algorithms. The �rst lecture teaches the basics behind multithreading, including de�ning the measures of work and critical-path length. It culminates in the greedy scheduling theorem due to Graham and Brent [9, 6]. The second lecture shows how parallel applications, including matrix multiplication and sorting, can be analyzed using divide-and-conquer recurrences.

Sign in with your free account to read, download EPUBs or listen.