NPTEL : NOC:Parallel Algorithms (Computer Science and Engineering)

Co-ordinators : Prof. Sajith Gopalan


Lecture 1 - Shared Memory Models - 1

Lecture 2 - Shared Memory Models - 2

Lecture 3 - Interconnection Networks

Lecture 4 - Cost and Optimality

Lecture 5 - Basic Techniques - 1

Lecture 6 - Basic Techniques - 2

Lecture 7 - Basic Techniques - 3

Lecture 8 - Basic Techniques - 4

Lecture 9 - Basic Techniques - 5

Lecture 10 - Odd Even Merge Sort (OEMS)

Lecture 11 - OEMS, Bitonic-Sort-Merge Sort (BSMS)

Lecture 12 - BSMS, Optimal List Colouring

Lecture 13 - Description

Lecture 14 - Analysis

Lecture 15 - Applications

Lecture 16 - Applications

Lecture 17 - Fast optimal merge algorithm

Lecture 18 - High level Description

Lecture 19 - Cole's Merge Sort: Details

Lecture 20 - Analysis of Cole's Merge Sort; Lower bound for sorting

Lecture 21 - Sorting Lower bound; Connected Components

Lecture 22 - Connected Components (CREW)

Lecture 23 - Connected Components, Vertex Colouring

Lecture 24 - Sorting on a 2D mesh

Lecture 25 - Sorting on a 2D mesh

Lecture 26 - Sorting, Offline routing on a 2D mesh

Lecture 27 - Sorting on a 3D mesh

Lecture 28 - Mesh of Trees, Hypercube

Lecture 29 - Hypercube (Continued...)

Lecture 30 - Hypercube (Continued...), butterfly network

Lecture 31 - Butterfly, CCC and Benes Networks

Lecture 32 - Butterfly, CCC and Benes Networks

Lecture 33 - Shuffle Exchange Graphs, de Bruijn Graphs

Lecture 34 - Shuffle Exchange Graphs, de Bruijn Graphs (Continued...)

Lecture 35 - Circuit Value Problem is P-complete for NC-reductions

Lecture 36 - Ordered DFS is P-complete for NC-reductions

Lecture 37 - Max Flow is P-complete for NC-reductions