سوالات

فرض کنید 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^۲ کدام است؟

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

فرض کنید A = [a_1, a_2, …, a_n] آرایه‌ای از اعداد صحیح متمایز باشد و k یک عدد صحیح داده شده باشد. هدف این است که دو عدد متمایز از A را پیدا کنید که مجموع آنها دقیقاً k باشد، یا گزارش دهید که چنین…

الگوریتم مرتب‌سازی ادغام (Megesort) را درنظر بگیرید. به‌جای اینکه آرایه ورودی را به دو قسمت تقریباً مساوی تقسیم کنیم، آن را به m بخش تقسیم می‌کنیم که لزوماً مساوی نیستند (m یک ثابت است.) سپس به‌صورت…

کدام‌یک از روابط بازگشتی زیر را نمی‌توان مستقیماً با قضیه اصلی حل کرد؟

گراف جهت‌دار و وزن‌دار G = (E, V) با n رأس و O(n) یال و زیرمجموعه S ⊆ V از رأس‌های گراف با اندازه حداقل n/2 داده شده است. فرض کنید وزن تمام یال‌های گراف مثبت است. به‌ازای هر رأس u از گراف، فاصله رأس…

فرض کنید گراف G یک گراف وزن‌دار و مسطح با n رأس است. درخت پوشای کمینه G را در چه زمانی می‌توان محاسبه کرد؟ توجه کنید لزومی ندارد از الگوریتم‌های معروف برای محاسبه درخت پوشای کمینه استفاده شود.…

آرایه A شامل n عدد داده شده است. هدف پیدا کردن تعداد جفت اندیس‌های i و j است، به‌گونه‌ای که A[i]× A[j] > i× j . این کار در چه زمانی قابل انجام است؟ (بهترین گزینه را انتخاب کنید.)

در کدام مورد، توابع به‌ترتیب صعودی (و نه اکیداً صعودی) بر مبنای رشد تابع از سمت چپ به راست، مرتب شده‌اند؟

مسئله k-مجموعه بدین شکل تعریف می‌شود: مجموعه A از n عدد حقیقی و عدد k داده شده است. آیا k عضو از مجموعه A وجود دارند که جمع آنها صفر شود؟ چه تعداد از گزاره‌های زیر درست است؟ مسئله ۱-مجموعه در زمان…

مسئله جستجوی عنصر x در آرایه A شامل n عنصر را در نظر بگیرید. فرض کنید اطلاع داریم که توزیع ورودی به اینصورت است که احتمال حضور عنصر x در نیمه دوم آرایه سه برابر احتمال حضور آن در نیمه اول است. همچنین…

آرایه A شامل n عنصر داده شده است. عنصری از آرایه که حافظ بیش از n/2 بار تکرار شده باشد را یک عضو پرتکرار می‌نامیم. می‌خواهیم در آرایه A یک عضو پرتکرار را در صورت وجود پیدا کنیم. در این کار از یک روش…