Parallel LSH

مرجع: http://padas.ices.utexas.edu/static/papers/sc11-knn.pdf

این پوستر(!) مربوط به LSH موازی است. با دیدن اینکه فقط به عنوان پوستر پذیرفته شده حس می‌کنم هدف الگوریتم‌های sublinear موازی حل کردن مسأله است و تازه می‌فهمم ایده‌ی Hashing چرا برای حل این مسأله استفاده شده است.

نزدیک‌ترین همسایه تقریبی موازی

مرجع: کتاب هندسه محاسباتی موازی Akl S.G., Lyons K.

البته کتاب قدیمی است و نتایج هم احتمالاً قدیمی اند!

کوئری نزدیک‌ترین همسایه و جستجوی بازه‌ای

مرجع: http://cs-wwwarchiv.cs.unibas.ch/lehre/ws06/cs342/slides/6_en_SimilaritySearch_2.pdf

یعنی باید دایره حول نقطه کوئری را بزرگتر می‌گرفتیم (همان طور که در قسمت‌های بعدی سوال گفته شده است)‌ و بعد با شماره‌گذاری خانه‌های نزدیک‌تر با اعداد کمتر به جواب می‌رسیدیم.

(سوال اول تمرین این سری هندسه را هم غلط حل کردم. البته قسمت اولش رو چون بعدی ها رو مستقل ثابت کردم ولی احتمالاً نمره‌ی هیچ کدوم رو نمی‌گیرم.)

نزدیک‌ترین همسایه با درخت چهارتایی

منبع: http://sarielhp.org/teach/1999/course.html

مرجع جدید موازی

http://laurel.datsi.fi.upm.es/_media/proyectos/gopac/programming_massively_parallel_processors.pdf

David B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Processors, A Hands-on Approach, Morgan Kaufmann, 2010 (supplementary for multicore programming in CUDA)

حل سوالهای الگوریتم پیشرفته یک دانشگاه دیگر

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/sol/

دریافت

دریافت

دریافت

دریافت

اصلاحیه تمرین موازی ۱

حل سوال ۱.۱۶۱ قسمت دوم: مربع‌های کوچک رادیکال n بر لگاریتم n هستند.

1.152. بدترین حالت این است که کل آن به صورت یک آرایه خطی مرتب شود که در حالت یکی در میان ۰ و ۱ بودن بیت‌ها رخ می‌دهد.

۱.۱۵۴. n گام برای حالت زیر:

000001

000001

000001

000001

اصلاحیه 5

روی جواب تمرین هندسه اصلاحیه داده شد.

سوال ۸ تمرین الگوریتم تقریبی

سوال ۳.۵ وزیرانی

حل: (سوال آخر)

http://dcg.epfl.ch/files/content/sites/dcg/files/Courses/Combinatorial%20Optimization%202012/ProblemSet11Solutions.pdf

سوال ۷ تمرین الگوریتم تقریبی

این سوال ۳.۶ WS هم هست. جواب:

http://www.diku.dk/OLD/undervisning/2005v/404/approx_path.pdf