IIT Guwahati · Computer Science

Parallel Algorithms

Prof. Sajith Gopalan · 37 free video lectures

37 video lectures. Topics: Shared Memory Models - 1; Shared Memory Models - 2; Interconnection Networks; Cost and Optimality; Basic Techniques 1; Basic Techniques 2; Basic Techniques 3; Basic Techniques 4; Basic Techniques 5; Odd Even Merge Sort (OEMS); OEMS, Bitonic-Sort-Merge Sort (BSMS); BSMS…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Shared Memory Models - 1
  2. Shared Memory Models - 2
  3. Interconnection Networks
  4. Cost and Optimality
  5. Basic Techniques 1
  6. Basic Techniques 2
  7. Basic Techniques 3
  8. Basic Techniques 4
  9. Basic Techniques 5
  10. Odd Even Merge Sort (OEMS)
  11. OEMS, Bitonic-Sort-Merge Sort (BSMS)
  12. BSMS, Optimal List Colouring
  13. Description
  14. Analysis
  15. Applications
  16. Applications
  17. Fast optimal merge algorithm
  18. High level Description
  19. Cole's Merge Sort: Details
  20. Analysis of Cole's Merge Sort; Lower bound for sorting
  21. Sorting Lower bound; Connected Components
  22. Connected Components (CREW)
  23. Connected Components, Vertex Colouring
  24. Sorting on a 2D mesh
  25. Sorting on a 2D mesh
  26. Sorting, Offline routing on a 2D mesh
  27. Sorting on a 3D mesh
  28. Mesh of Trees, Hypercube
  29. Hypercube cont'd
  30. Hypercube cont'd, butterfly network
  31. Butterfly, CCC and Benes Networks
  32. Butterfly, CCC and Benes Networks
  33. Shuffle Exchange Graphs, de Bruijn Graphs
  34. Interconnection Networks Algorithms
  35. Circuit Value Problem is P-complete for NC-reductions
  36. Ordered DFS is P-complete for NC-reductions
  37. Max Flow is P-complete for NC-reductions

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Guwahati.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights