ورقة عمل الخوارزميات والتعقيد مع الإجابات

ما زمن تنفيذ الفرز بالعدّ لـ n عددًا صحيحًا في المدى من 0 إلى k؟

1. AO(n²)
2. BO(n + k)
3. CO(k log n)
4. DO(n log n)

ماذا يصف زمن التنفيذ في أسوأ الحالات لخوارزمية؟

1. Aالزمن المتوقع الذي تستغرقه على مدخل عشوائي بحجم n
2. Bأقصى زمن تستغرقه على كل المدخلات ذات الحجم n
3. Cالزمن الذي تستغرقه على أصغر مدخل
4. Dالزمن الذي تستغرقه على حاسوب بطيء

أي مما يلي ينمو بأبطأ ما يمكن عندما تصبح n كبيرة؟

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(n log n)

بقطع نقدية من فئات 1 و3 و4 ومبلغ 6، كم قطعة تستخدم الطريقة الجشعة "أكبر قطعة أولًا" مقارنةً بالحل الأمثل؟

1. Aتستخدم الجشعة 3 قطع، والأمثل 2
2. Bتستخدم الجشعة 3 قطع، والأمثل 3
3. Cتستخدم الجشعة 4 قطع، والأمثل 3
4. Dتستخدم الجشعة قطعتين، والأمثل 2

ماذا تحسب خوارزمية Floyd–Warshall، وبأي سرعة؟

1. Aترتيبًا طوبولوجيًا في O(V²)
2. Bشجرة امتداد صغرى في O(E log V)
3. Cأقصر المسارات من رأس مصدر واحد إلى سائر الرؤوس في O(V + E)
4. Dأقصر المسارات بين كل أزواج الرؤوس في O(V³)

ما حل علاقة التكرار T(n) = 2T(n − 1) + O(1)؟

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(2ⁿ)

أي أمرين يجب إثباتهما لإثبات أن مسألة القرار X هي NP-تامة؟

1. Aأن X تنتمي إلى P، وأن X تُختزل إلى SAT
2. Bأن X ليس لها خوارزمية كثيرة حدود، وأن X قابلة للحسم
3. Cأن X تنتمي إلى NP، وأن مسألة NP-تامة معروفة تُختزل إلى X في زمن كثير حدود
4. Dأن X تُختزل إلى مسألة في P، وأن X تنتمي إلى NP

أخذ طرفي كل حافة في تطابق أعظمي (maximal matching) يعطي غطاءً رأسيًا. ما جودة هذا الغطاء؟

1. Aجودته مجهولة مقارنةً بالأمثل
2. Bضعف حجم الغطاء الرأسي الأصغر على الأكثر
3. Cغطاء رأسي أصغر دائمًا
4. Dlog n ضعف الأصغر على الأكثر