طراحی الگوریتم‌هاAlgorithm Design

فرض کنید T(x) = ۲T(x/۲) + ۸/۹T(۳x/۴) + θ((x^۲)/(log x)) . دراین‌صورت کدام مورد درست است؟

دنباله A[1..n] یک دنباله دوآهنگی (Bitonic) است، بدین معنی که هرگاه عناصر دنباله را به‌ترتیب دور یک دایره بنشانیم، یک عنصر یافت می‌شود که دنباله عناصر بعدی ابتدا صعودی و سپس نزولی هستند. بهترین زمان…

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

فرض کنید مسئله‌ای با نام انتخاب پروژه‌های با بیشترین سود (Maximum Profit Project Selection) داریم. در این مسئله، تعدادی پروژه وجود دارد که هر پروژه دارای سود مشخص است و m ماشین و یک محدودیت زمانی T…

در الگوریتم مرتب‌سازی Insertion Sort، اگر برای جستجوی مکان مناسب عنصر جاری به جای جستجوی خطی از جستجوی دودویی استفاده کنیم، کدام مورد زیر درخصوص پیچیدگی زمانی آن در بدترین حالت درست است؟

فرض کنید در مسئله‌ای اعداد مشخصی محاسبه می‌شوند و هرچه ورودی‌ها بیشتر شوند، تعداد محاسبه‌های (زیرمسئله‌های) تکراری بیشتر می‌شود. می‌خواهیم هنگام محاسبهٔ پاسخ، با ساختن از روی زیرمسئله‌های کوچک‌تر از…

فرض کنید برای حل مسئله پوشش حداکثر (maximum Coverage)، از الگوریتم حریصانه استفاده می‌کنید که مجموعه‌ای از عناصر را با کمترین هزینه ممکن پوشش دهد. چرا این الگوریتم نمی‌تواند جواب بهینه را تضمین کند؟

چند گزاره از گزاره‌های زیر درست است؟ ـ هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلیدها مرتب‌سازی می‌کند، باید در بدترین حالت حداقل ⌈ log(n!) ⌉ مقایسه کلیدها را انجام دهد. ـ اگر m تعداد…

هر الگوریتم قطعی که بتواند بزرگ‌ترین کلید دوم (دومین بزرگ‌ترین کلید) را در هر ورودی ممکن، تنها با مقایسه کلیدها بیابد، باید در بدترین حالت، حداقل چند مقایسه انجام دهد؟ (تعداد عناصر برابر n است.)

در دو الگوریتم مرتب‌سازی سریع (Quick Sort) و مرتب‌سازی ادغامی (Merge Sort)، تعداد مقایسه‌ها و جابه‌جایی‌ها متفاوت است. کدام گزاره زیر، درباره این تفاوت‌ها درست است؟

آرایه A به طول n را K- مرتب می‌کنیم. هرگاه برای هر i که k ≤ i ≤ n-k داشته باشیم A[i-k] ≤ A[i] ≤ A[i+k] ، یعنی آرایه A به k لیست مرتب که هر کدام تقریباً n/k عنصر دارند افراز می‌شود. فرض کنید A یک…

فرض کنید G = (V , E) ، یک گراف هم‌بند وزن‌دار باشد. چند مورد از گزاره‌های زیر درست است؟ اگر وزن تمام یال‌های گراف با هم برابر باشد، می‌توان درخت فراگیر کمینه آن را با الگوریتمی از مرتبه O( E ) بدست…

رشته‌هایی که از دو طرف یکسان خوانده می‌شوند پالیندروم (Palindrome) نامیده می‌شوند (مانند abcba). برای محاسبهٔ بزرگ‌ترین زیررشتهٔ پالیندروم یک رشته به طول n، یک الگوریتم پویا با ترتیب از راست به چپ…

آن را با LDS (S) (Longest Double String) نشان می‌دهیم. دراین‌صورت رابطه بازگشتی طول بزرگ‌ترین زیررشته (LDS) چیست؟ (توجه کنید LCS تابعی است که طول بزرگ‌ترین زیررشته مشترک دو رشته ورودی را برمی‌گرداند.)

تابع بازگشتی زیر را در نظر بگیرید: int f(int n) if(n == ۰ n == ۱) return (n + ۱); else if (n == ۲) return ۴; return (f(n-۱) + ۲ f(n-۲) + f(n-۳)); برای n ≥ 3 ، کدام گزینه بهترین کاندید برای f(n) است؟

فرض کنید آرایه‌ای به طول n داریم که به شکل حلقوی مرتب صعودی است. برای مثال آرایه زیر: ۴۰ ۵۰ ۶۰ ۷۰ ۸۰ ۹۰ ۱۰ ۲۰ ۳۰ ---- ---- ---- ---- ---- ---- ---- ---- ---- می‌خواهیم الگوریتمی بنویسیم که ⌊ √n ⌋…

بهترین پیچیدگی زمانی مورد نیاز برای محاسبه مجموع دو جمله i ام و j ام از دنباله فیبوناچی چیست؟

هریک از کارهای زیر در یک واحد زمان قابل اجرا است. هر یک از این کارها دارای یک زمان خاتمه است و درصورتی‌که بعد از زمان خاتمه انجام شود مشمول یک جریمه خواهد شد. اگر این کارها را برای اجرا به کم‌ترین…

فرض کنید که در الگوریتم مرتب‌سازی سریع برای انتخاب محور از میان n عنصر آرایه 2⌊ log n⌋ + 1 عنصر اولیه را انتخاب کنیم و با الگوریتم مرتب‌سازی درجی آنها را مرتب کنیم. عنصر میانه این تعداد عنصر مرتب را…

فرض کنید f(n) = n و g(n) = n^((۱+sin n)) ، که n یک عدد صحیح مثبت است. کدام‌یک از گزاره‌های زیر درست است؟ I. f(n) = O(g(n)) II. f(n) = Ω(g(n))

چند مورد از گزاره‌های زیر درست است؟ I. هر الگوریتم که ضرب دو ماتریس را محاسبه کند، می‌تواند در همان مرتبه وارون یک ماتریس را محاسبه کند و بالعکس. II. برای محاسبه ضرب دو چندجمله‌ای از درجه ۱۶ تعداد…

در مسئلهٔ یافتن پوسته محدب، تعدادی نقطه در صفحه داده شده است. هدف پیداکردن کوچکترین (کمترین محیط) چندضلعی محدب است که شامل همه نقاط باشد. بهترین الگوریتم ممکن برای یافتن این چندضلعی، چه مرتبه زمانی…

مرتبه زمانی الگوریتم زیر کدام است؟ for(i = ۱ ; i <= n ; i++) for(j = ۱ ; j <= ⌊n/i⌋ ; j++) S.O. ...

کدام‌یک از عبارات زیر درست است؟ الف- هر مسئله‌ای NP- کامل یک مسئله‌ای NP- سخت است. ب- هر مسئله‌ای NP- سخت یک مسئله‌ای NP- کامل است. ج- هر مسئله‌ای P (چندجمله‌ای) یک مسئله‌ای NP هم هست.

فرض کنید که یک مسئله را بتوان به‌صورت بهینه هم با روش تقسیم و حل، هم با روش برنامه‌ریزی پویا و هم با روش حریصانه حل کرد. در این‌صورت از لحاظ پیچیدگی زمانی کدام‌یک ارجحیت دارد؟

کدام‌یک از مسائل زیر در زمان خطی برحسب تعداد رئوس و یال‌های گراف ورودی قابل‌حل نیست؟

برای پیاده‌سازی مؤثر کدام‌یک از الگوریتم‌های زیر، ساختمان داده heap لازم نیست؟

یک آرایه دوبعدی n × n از اعداد داده شده‌است که هر سطر به‌صورت صعودی از چپ به راست و هر ستون به‌صورت صعودی از بالا به پایین مرتب شده‌است. کمترین پیچیدگی زمانی برای پیداکردن یک عدد داده‌شده در این…

یک الگوریتم یک آرایه دوبعدی n × n را به‌عنوان ورودی دریافت می‌کند و زمان اجرای آن برحسب n عبارت است از T(n) = O(n log n) ، زمان الگوریتم برحسب اندازه ورودی m = n^۲ کدام است؟

فرض کنید برای حل یک مسئله باید از بین چهار الگوریتم انتخاب کنید. کدام یک ارجحیت دارد؟