Learn · NPTEL

Course10610318837 lectures

Parallel Algorithms

Prof. Sajith Gopalan · IIT Guwahati

Start with lecture 1 At NPTEL

Lectures

Models of Computation

  1. Shared Memory Models - 1 Video
  2. Shared Memory Models - 2 Video
  3. Interconnection Networks Video

Performance of Parallel Algorithms and Basic Techniques

  1. Cost and Optimality Video
  2. Basic Techniques 1 Video
  3. Basic Techniques 2 Video

BasicTechniques

  1. Basic Techniques 3 Video
  2. Basic Techniques 4 Video
  3. Basic Techniques 5 Video

Comparator Networks

  1. Odd Even Merge Sort (OEMS) Video
  2. OEMS, Bitonic-Sort-Merge Sort (BSMS) Video
  3. BSMS, Optimal List Colouring Video

An Optimal List Ranking algorithm

  1. Description Video
  2. Analysis Video
  3. Applications Video

An Optimal List Ranking algorithm, Expression Tree Evaluation, Merging,Cole's Merge Sort

  1. Applications Video
  2. Fast optimal merge algorithm Video
  3. High level Description Video

Cole's Merge Sort; Sorting Lower Bound, Sorting Lower bound; Connected Components

  1. Cole's Merge Sort: Details Video
  2. Analysis of Cole's Merge Sort; Lower bound for sorting Video
  3. Sorting Lower bound; Connected Components Video

Connected Components

  1. Connected Components (CREW) Video
  2. Connected Components, Vertex Colouring Video
  3. Sorting on a 2D mesh Video

Interconnection Networks Algorithms

  1. Sorting on a 2D mesh Video
  2. Sorting, Offline routing on a 2D mesh Video
  3. Sorting on a 3D mesh Video
  4. Mesh of Trees, Hypercube Video
  5. Hypercube cont'd Video
  6. Hypercube cont'd, butterfly network Video
  7. Butterfly, CCC and Benes Networks Video
  8. Butterfly, CCC and Benes Networks Video
  9. Shuffle Exchange Graphs, de Bruijn Graphs Video
  10. Interconnection Networks Algorithms Video

Parallel Complexity Theory

  1. Circuit Value Problem is P-complete for NC-reductions Video
  2. Ordered DFS is P-complete for NC-reductions Video
  3. Max Flow is P-complete for NC-reductions Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Guwahati
Department
Computer Science and Engineering
Teacher
Prof. Sajith Gopalan
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed