Equivalences between triangle and range query problems

https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.3

Combinatorial Algorithms and Data Structures

https://people.eecs.berkeley.edu/~satishr/cs270/sp17/

الگوریتم برای میانه + یک قضیه تحلیل زمان

http://www.cs.cmu.edu/afs/cs/academic/class/15451-s14/LectureNotes/median.pdf

جزوه الگوریتم پیشرفته (ETH)

http://people.csail.mit.edu/ghaffari/AA18/Notes/AAscript.pdf

Beyond Worst-Case Analysis

http://theory.stanford.edu/~tim/notes.html

Nested Satisfiability

مرجع: Selected Papers on Design of Algorithms

این مسئله در زمان چندجمله‌ای قابل حل است و حالتی از SAT است که در آن عبارت‌ها ساختار سلسله مراتبی دارند.

اگر m عبارت با این خاصیت و n متغیر داشته باشیم، حداکثر 2m+n جمله داریم.

این مرجع پیشنهاد یکی از دوستان بود که کامنت خصوصی گذاشته بود.

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

۱- از یک زمانبند حریصانه استفاده می‌کنیم. اگر زمان اجرای یک الگوریتم روی ۴ پردازنده ۲۶۰ ثانیه و روی ۳۲ پردازنده ۹۰ ثانیه باشد؛ آیا مقادیر T1=1024 و Tinfinity = 64 می‌توانند مقادیر معتبری باشند؟

۲-  الگوریتم push-relabel را روی گراف زیر اجرا کنید که همه‌ی یالهای آن وزن ۲ دارند به جز یال آخر که وزن ۱ دارد.

s->v1->....->vn->t

تعداد pushها و تعداد relabelها و زمان الگوریتم را حساب کنید.

۳- یک الگوریتم موازی برای محاسبه‌ی ترانهاده‌ی ماتریس X که n*n است بنویسید و کار و زمان و موازات آن را حساب کنید.

۴- یک شبکه شار داریم که یالهای آن آبی یا قرمز هستند. یالهای آبی ظرفیت ce دارند و یالهای قرمز کران پایین de دارند. شار بیشینه را می‌خواهیم به دست بیاوریم.

الف) برای آن یک LP بنویسید و ثابت کنید زمان آن خطی است.

ب) ثابت کنید اگر یالهای قرمز را بتوانیم خاموش و روشن کنیم؛ مسأله‌ی اینکه این گراف شار k دارد یا نه، np-complete است. (از subset-sum کمک بگیرید.)

۵- ثابت کنید دور فروشنده دوره‌گرد را نمی‌توان بهتر از یک تابع چندجمله‌ای بر حسب n تقریب زد.

۶- تابع پیشوندی در الگوریتم KMP را بنویسید و تحلیل کنید.

تمرین‌های الگوریتم پیشرفته

تمرین‌های کتاب که فقط شماره‌ی آنها داده شده بود. (این همه‌ی تمرین‌ها نیست)

ایده‌ی حل سوالهای میان ترم ۹۱ الگوریتم

۱- تکراری با سوال ۱ ما. (رجوع به پست قبلی)
۲-....
۳- به نظرم رسید با min cut حل کنیم که رأسهای یک طرف جزو مسیر هستند و یالهای طرف دیگر جزو مسیر نیستند. می‌دانیم که رأسها به ترتیب توپولوژیکی هستند (طبق شرط جهت که گذاشته)
برای اینکه رأس تکراری نباشد هم یک کپی از رأسها می‌گذاریم با یال بینهایت وصل می‌کنیم.
۴- به نظرم باید دایجسترا اجرا کنیم (کوتاهترین مسیر چون شار در طول مسیر ثابت است همینکه کوتاهترین مسیر باشد کافی است.)
۵- ب) مشابه مسأله‌ی پروژه‌ها: پروژه ها همان سرمایه گذارها هستند و پیشنیازها بازیگرهای مربوط به آن هستند.

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

۱- n عنصر و m مجموعه داریم که هر مجموعه k عضو دارد می‌خواهیم عناصر را با k رنگ، رنگ آمیزی کنیم که از هر رنگ یکی در هر مجموعه باشد.
الف) ثابت کنید که این مسأله NP است.
ب) ثابت کنید که برای k=3 ان پی کامل است. (با استفاده از ۳-رنگ پذیری گراف)
ج) ثابت کنید برای k=2 پی است.
جواب:
الف) یک مصداقش در زمان چندجمله‌ای قابل جواب دادن است.
ب) هر رأس و رأسهای مجاور را یک مجموعه بگیرید.
ج) رنگ آمیزی گراف با دو رنگ فقط برای گراف دوبخشی ممکن است (دور فرد نداشته باشد).
۲- مسأله‌ی هش کردن پویا را با فرض اینکه به جای دو برابر رادیکال n برابر کنیم که n تعداد عناصر موجود است حل کنید.
الف) زمان درج هش پویای معمولی چقدر است.
ب) حداکثر جای خالی جدول در این تعریف جدید چقدر است؟ (ثابت کنید از مرتبه رادیکال n است)
ج) زمان درج برای این حالت جدید چقدر است؟ (سرشکنی)
جواب: تابع پتانسیل را تعداد اعداد موجود منهای توان ۲ تعداد جاهای خالی +۱ گرفتم. (اون +۱ برای حالت پایه اش بود که منفی نشه)

۳- یک گراف نامشخص داریم فقط درجه ورودی و خروجی هر رأس را می‌دانیم. گراف را پیدا کنید.

جواب: شار بیشینه. n رأس سمت راست و n رأس سمت چپ می‌گذاریم و از s با درجه خروجی هر رأس و به t با درجه ورودی هر رأس وصل می‌کنیم. بین رأسهای سمت راست و چپ هم یالهای با ظرفیت ۱ می‌گذاریم. این گراف جهت دار بدون یال چندگانه و با طوقه می‌دهد. اگر بخواهیم طوقه نداشته باشد باید رأسها را به خودشان وصل نکنیم. برای یال چندگانه هم ظرفیت بینهایت بگذاریم به جای ۱.

۴- در مورد push relabel به سوالهای زیر جواب بدهید:

الف) ثابت کنید اگر رأس u پیش شار داشته باشد در Gf مسیر از u به s هست.

ب) تعداد عملیات مختلف را به دست بیاورید. non saturating push, saturating push, relabel

*اگر سوالی هست که یادم رفته بنویسم کامنت بگذارید.