NOC:Parallel Algorithms


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