الگوریتم‌های پردازش داده‌های حجیم

Massive Data Algorithmics

جدول ارائه درس:

اسلاید
سخنران
مرجع
مبحث
زمان

  [AV,AL]

مقدمه‌ای بر مدل‌های I/O و برخی الگوریتم‌ها

الگوریتم مرتب سازی

جلسه اول

جلسه دوم

جلسه سوم

[Alower]

 
کران پایین مرتب سازی و جایگشت در مدل I/O

جلسه چهارم

 

جلسه پنجم

   

[Anote]

Sec. 1-3

الگوریتم‌های جستجو
جلسه ششم

جلسه هفتم

   

[Anote]

Sec. 4-5

الگوریتم‌های جستجو
جلسه هشتم

جلسه نهم

 

[Anote]

Sec. 6-7

ساختمان داده‌های هندسی
جلسه دهم

جلسه یازدهم

   

[Anote]

Sec. 8-9

ساختمان داده‌های هندسی
جلسه دوازدهم

جلسه سیزدهم

    [Z] sec 2-4, [CGGTVV] sec 3-6, [ABDHM] sec 3.1-3.2
List Ranking - Algorithms on trees

جلسه چهاردهم

جلسه پانزدهم

 
  [Z] sec 6.1-6.2, [ABDHM] sec 3.3, [CGGTVV], sec 7, [BGVW], [MR] sec 5.1 Graph algorithms: Directed DFS and BFS, undirected BFS

جلسه شانزدهم

جلسه هفدهم

    [Z] sec 5+7, [ABT] sec 2, [ABDHM] sec 3.4, [KS] sec 2.2+3.3
Graph algorithms: Undirected Minimal Spanning Tree and Shortest Paths

جلسه هجدم

   

جلسه نوزدهم

  [B]
Cache-Oblivious Model: Model, matrix multiplication, sorting
جلسه بیستم
جلسه بیست و یکم
    [Stream]
Data Streams: Models and Algorithms

جلسه بیست و دوم

جلسه بیست و سوم

     
     
 

منابع درس:

[AV] The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. Vitter. CACM 31 (9), 1988.

[Alower] Lower bound on External Permuting/Sorting, Lecture notes by L. Arge.

[FJKT] Heaps and Heapsort on Secondary Storage. R.Fadel, K.V. Jakobsen, J. Katajainen, J. Teuhola. TCS 220 (2), 1999.

[AL] External partition element finding, Lecture notes by L. Arge and M. G. Lagoudakis.
[Anote] External Memory Geometric Data Structures. L. Arge. Lecture notes.

[Z] I/O-Efficient Graph Algorithms. N. Zeh. Lecture notes.

[CGGTVV] External-Memory Graph Algorithms. Y-J. Chiang, M. T. Goodrich, E.F. Grove, R. Tamassia. D. E. Vengroff, and J. S. Vitter. Proc. SODA'95

[BGVW] On External Memory Graph Traversal. A.L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, J.R. Westbrook, Proc. SODA'00.

[MR] I/O-Complexity of Graph Algorithms. K. Munagala and A. Ranade. Proc. SODA'99.

[ABT] On External-Memory MST, SSSP and Multi-Way Planar Graph Separation. L. Arge, G. S. Brodal, and Laura Toma. Journal of Algorithms 53:186-206, 2004.

[KS] Improved Algorithms and Data Structures for Solving Graph Problems in External Memory. V. Kumar and E.J. Schwabe. Tech. report version of paper in SPDP'96.

[FLPR99] Cache-Oblivious Algorithms. M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran. Proc. FOCS '99.

[ABDHM] Cache-Oblivious Priority Queue and Graph Algorithm Applications. L. Arge, M. Bender, E. Demaine, B. Holland-Minkley and I. Munro. SICOMP, 36(6), 2007.

[BF02] Cache Oblivious Distribution Sweeping. G. S Brodal and R. Fagerberg. Proc. ICALP’02.

[B] Cache-oblivious Algorithms and data structures. SWAT’04.

[Stream] Data Streams: Models and Algorithms

Ulrich Meyer, Peter Sanders, Jop Sibeyn (Eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science Vol 2625, Springer-Verlag Berlin Heidelberg, 2003.

 

درس در سایر دانشگاههای جهان

Lars Arge (MADALGO-Denmark)

Herman Haverkort (TU/e-The Netherlands)

Rolf Fagerberg (Denmark)

Norbert Zeh (Dalhousie University-Canada)

MohammadAli Abam (Sharif U. Tech.)