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

سوال آخر تمرین ۳ که خواسته است رابطه بازگشتی تو در تو حل کنیم با parallel prefix با فرض بینهایت پردازنده در زمان O(log n) حل می‌شود که زمان parallel prefix و semigroup است چون زمان مراحل موازی با هم ماکسیمم گرفته می‌شوند یک مرحله محاسبه‌ی پیشوند داریم و دو مرحله جمع جملات (semigroup) داریم.

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

online auctions

http://www.cs.umd.edu/~hajiagha/AGT10/13-10-10-OnlineAuctions.pdf

مشخصات توپولوژی‌های مختلف (موازی)

جواب سوال آخر تمرین ۳ پردازش موازی

اصلا سعی نکنید این سوال را حل کنید الکی وقتتون تلف میشه!

http://en.wikipedia.org/wiki/Newton_polynomial

http://en.wikipedia.org/wiki/Divided_differences

Mind maths: Small world with big connections

دریافت

مرجع

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 یعنی با اضافه شدن نقطه و حذف شدن نقطه است. در آن از ورونوی دیاگرام گسسته هم استفاده شده است و مبنای الگوریتم عرض جهتی است.

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

Combinatorial Optimization 2012

http://dcg.epfl.ch/page-84766-en.html