چندریسه‌ای+مرتب سازی روی پروانه

من یک جمله توی دفترم دارم که هر ریسه‌ای می‌تواند ۲ تا ریسه‌ی دیگر بسازد که به نظرم غلطه. الآن که با کتاب چک کردم درسته که هر دو مثالی که زده برای حالت‌های با ۲ تا نخ بوده ولی هیچ محدودیتی روی تعدادش نگذاشته. در نتیجه من بیخودی این حالت را حساب کردم. :|

مثال فیبوناچی هم طبیعتاً ربطی به این قضایا نداره چون اون خودش رابطه بازگشتی‌اش حل کردنش به صورت موازی O(n) زمان می‌خواهد. (طول مسیر بحرانی)

-------

برای مرتب سازی روی مدل پروانه‌ای هم bitonic sort را نوشتم در حالی که به خاطر اینکه روی پروانه داریم اجرا می‌کنیم ترتیبش یک جور دیگه باید باشه که من سر جلسه هر کاری کردم بهتر از اون نشد. توی کتاب هم گفته به صورت بازگشتی این کار را انجام می‌دهیم و اصلاً معلوم نیست چطوری این کار را کرده. :|

--------

فکر کنم هدف سوال ۲ هم این بود که حلقه موازی بنویسیم نه اینکه مثل من کل مسأله را در زمان log n حل کنیم! :) :|

پروپوزال

از یک طرف ایمیل خودم را می‌خونم می‌خندم که عین جمله‌های ایمیل قبلی استادم رو نوشتم، از یک طرف دیگر به اینکه پس پروپوزال را برای چی نوشتم می‌خندم.

A Polynomial Time Algorithm for Graph Isomorphism

http://www.dharwadker.org/tevet/isomorphism/main.html#8

چرا توی این سالها کسی به من نگفت که یکریختی گراف P است؟ :)

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

Spectral Sparsification in Dynamic Graph Streams

http://www.cis.upenn.edu/~sudipto/mypapers/resistance.pdf

Geometric Optimization (Fall 2013)

مرجع: http://www.cs.tau.ac.il/~michas/optcourse.html

استاد: Sharir

The syllabus of the course 

===== 

The syllabus may not exactly coincide with the material that will be taught. It will be (slightly) updated during the semester 

===== 

(1) Parametric Searching:

The basic technique

Illustration: Slope selection

Issues in parallel computation

Cole's improvement

Alternatives: Probabilistic approach, Expanders, Monotone Matrix Searching, Chan's technique

===== 

(2) Linear Programming: Geometric Approach:

Review of Megiddo's algorithm and Seidel's randomized algorithm. Algorithms by Clarkson and by Matousek et al.

Abstract linear programming: Framework, geometric applications, variants

===== 

(3) Search in Monotone Matrices: 

===== 

(4) Facility Location:

The p-center probolem

Efficient algorithm for the 2-center problem

Exact and approximate algorithms for the general case

Clustering

The p-median problem and other variants

===== 

(5) Diameter in Three Dimensions:

A randomized algorithm

A deterministic algorithm

===== 

(6) Geometric Optimization and Arrangements:

Hausdorff distances

Width in three dimensions

Polygon placements; biggest stick in a polygon.

===== 

(7) Shortest Paths:

Shortest paths in the plane

Shortest paths on a convex polytope and in polyhedral 3-D regions

Approximate shortest paths

===== 

(8) Approximation Algorithms for Geometric Optimization:

Euclidean travelling salesperson

Approximating diameter, width, minimum-width annuli and cylinders

===== 

(9) Approximate Nearest Neighbor Search in Higher Dimensions:

Review of recent techniques

Robust Shape Fitting via Peeling and Grating Coresets

http://www.cs.duke.edu/~pankaj/publications/papers/core-outlier.pdf

Let P be a set of n points in R^d. A subset S of P is called a (k,epsilon)-kernel if for every direction, the

direction width of S epsilon-approximates that of P, when k outliers can be ignored in that direction.

Width of Points in the Streaming Model

http://www.mit.edu/~andoni/papers/width.pdf

موضوع آن محاسبه‌ی عرض نقاط به صورت dynamic یعنی با اضافه شدن نقطه و حذف شدن نقطه است. در آن از ورونوی دیاگرام گسسته هم استفاده شده است و مبنای الگوریتم عرض جهتی است.

Parallel LSH

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

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

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

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

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

تعدادی از درس‌های الگوریتمی

الگوریتم تقریبی پیشرفته

http://www.cs.cmu.edu/~anupamg/adv-approx/

الگوریتم‌های دنیای واقعی (شامل LSH و چند تا از مدل‌های جویبار داده و الگوریتم موازی و ...)

http://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesS14.html

کاربرد متریک در مسائل الگوریتمی

http://www.cs.cmu.edu/~anupamg/metrics/index.html

همه‌ی این درس‌ها را یک نفر ارائه می‌دهد:

http://www.cs.cmu.edu/~anupamg/