تمرین 1

این سوالهای اون دانشگاهیه که قبلش امتحانهاش رو حل کردم. این کتاب دومیه خیلی خوب بوده حیف شده زودتر ندیدم بخونمش! :|

1.3 Let E be an unsorted set of n segments that are the edges of a convex

polygon. Describe an O(nlogn) algorithm that computes from E a list

containing all vertices of the polygon, sorted in clockwise order.

یالهای نامرتب CH رو داده، راسها رو به ترتیب ساعتگرد میخواد. خب دو سر پاره خط رو به عنوان نقطه به هر الگوریتم CH ای که بدی برات پیدا می کنه دیگه.

1.8 The O(nlogn) algorithm to compute the convex hull of a set of n points

in the plane that was described in this chapter is based on the paradigm

of incremental construction: add the points one by one, and update the

convex hull after each addition. In this exercise we shall develop an

algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total.

Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.

مماس مشترک بالایی و پایینی رو پیدا می کنیم و بینش رو حذف می کنیم. زمان پیدا کردن مماس مشترک که خیلی کمتر از این حرفهاست، زمان حذف کردن هم که یکه. اصلا O(n) چرا با logn حل میشه.

b. Use the algorithm from part a to develop an O(nlogn) time divide-and-

conquer algorithm to compute the convex hull of a set of n points in

the plane.

الگوریتمش هست دیگه، نقطه ها رو نصف می کنی، CH راستی ها، CG چپی ها و ادغام هم O(n).

T(n) = 2T(n/2)+O(n) ==> T(n) = O(nlogn)

1.9 Suppose that we have a subroutine CONVEXHULL available for comput-

ing the convex hull of a set of points in the plane. Its output is a list of con-

vex hull vertices, sorted in clockwise order. Now let S = {x1,x2,...,xn}

be a set of n numbers. Show that S can be sorted in O(n) time plus the

time needed for one call to CONVEXHULL. Since the sorting problem

has an Ω(nlogn) lower bound, this implies that the convex hull problem

has an Ω(nlogn) lower bound as well. Hence, the algorithm presented in

this chapter is asymptotically optimal.

اعضای S رو به نقاط xi, xi^2 تبدیل می کنیم و CH اونها رو حساب می کنیم. بعد مرتب شده بر می گردونه. چون بر اساس زاویه مرتب می کنه که tan a = x^2/x = x

خب ببینیم چقدر از این جواب ها درست بوده!

باید سه تا راس رو در نظر می گرفتیم برای حالت بندی پیدا کردن مماس مشترک. خیلی خوبه که هیچ کس اینو نگفته! :| (سوال 1) کلا 4 تا حالت میشه.

یه سوالو جا انداخته بودم:

2.3 Change the code of Algorithm FINDINTERSECTIONS (and of the pro-

cedures that it calls) such that the working storage is O(n) instead of

O(n+k).

الگوریتمی که گفته یه sweep بوده که قرار بوده تقاطع خطوط رو پیدا کنه. خودش گفته که فقط تقاطع پاره خط های مجاور رو نگه دارید (که خط جارو رو قطع می کنن) گفته n تا پاره خط اند حداکثر که دارن خط جارو رو قطع می کنن پس این میشه O(n). بعد گفته تعداد event ها هم خطیه چون همین ها event هم هستند. (در هر مرحله ی الگوریتم: چون برای مرحله ی بعد حذف می کنیم از n بیشتر نمیشه).

تو سوال یک یادم رفت تکراری ها رو باید حذف کنم! :) خودش بر حسب زاویه مرتب کرده. و گفته از کم به زیاد مرتب کنیم CH میشه.