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

أي خوارزمية فرز تبدّل مرارًا مواضع العناصر المتجاورة الموجودة في ترتيب خاطئ؟

1. Aالفرز بالكومة (Heap sort)
2. Bالفرز السريع (Quicksort)
3. Cالفرز الفقاعي (Bubble sort)
4. Dالفرز بالدمج (Merge sort)

ما قيمة log₂ 1024؟

1. A12
2. B32
3. C10
4. D512

ماذا تعني f(n) = Θ(g(n))؟

1. Aأن f تنمو بمعدل g نفسه، محصورة من الأعلى والأسفل بمضاعفات ثابتة لـ g
2. Bأن f تنمو أسرع من g تمامًا
3. Cأن f تنمو أبطأ من g تمامًا
4. Dأن f أصغر دائمًا من g لكل n، فتحدّها g من الأعلى ولا تحدّها من الأسفل أبدًا

حل العلاقة التكرارية T(n) = 2T(n/2) + O(n) هو:

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

كم مستوى لعودية الفرز بالدمج لمصفوفة من n عنصر؟

1. Aنحو n / 2
2. Bنحو n
3. Cنحو √n
4. Dنحو log₂ n

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

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

أي عبارة عن ترميز o الصغير صحيحة؟

1. An² = o(n)
2. Bn = o(n²)، لكن n ليست o(n)
3. C2n = o(n)، لأن 2n تنمو ببطء
4. Dn = o(n)، لأن كل دالة هي o صغير لنفسها

تستغرق مسألة حقيبة الظهر 0/1 المحلولة بالبرمجة الديناميكية زمنًا O(nW). لماذا يُسمى هذا شبه كثير الحدود (pseudo-polynomial)؟

1. Aلأن W عدد، فيكون الزمن أسّيًا بالنسبة إلى عدد البتات المستخدمة لكتابة W
2. Bلأنها تعمل فقط عندما W = 0
3. Cلأن n صغيرة دائمًا
4. Dلأن الخوارزمية عشوائية ويتفاوت زمن تشغيلها مع كل مدخل