Midterm Master Review مراجعة منتصف الفصل الشاملة
Comprehensive summary of Modules 1 through 6. Everything you need to know about Analysis, Sorting, Brute Force, Divide & Conquer, and Transform strategies. ملخص شامل للوحدات من 1 إلى 6. كل ما تحتاج معرفته عن التحليل (Analysis)، الفرز (Sorting)، القوة الغاشمة (Brute Force)، فرق تسد (Divide & Conquer)، واستراتيجيات التحويل (Transform).
1. Fundamentals & Analysis (Mod 1-2) 1. الأساسيات والتحليل (Mod 1-2)
Asymptotic Notations Asymptotic Notations (الترميز التقاربي)
How to Analyze كيفية التحليل
- Identify parameter $n$. حدد المعامل $n$.
- Find the Basic Operation (innermost loop). ابحث عن Basic Operation (الحلقة الداخلية).
- Set up a sum $\sum$. قم بإعداد المجموع $\sum$.
- Solve: $\sum_{i=1}^n 1 = n$, $\sum_{i=1}^n i \approx n^2/2$. حل: $\sum_{i=1}^n 1 = n$, $\sum_{i=1}^n i \approx n^2/2$.
- Identify parameter $n$. حدد المعامل $n$.
- Set up recurrence relation (e.g., $M(n) = M(n-1) + 1$). أنشئ علاقة تكرارية (مثلاً $M(n) = M(n-1) + 1$).
- Identify base case (e.g., $M(0) = 0$). حدد الحالة الأساسية (Base case).
- Solve using Backward Substitution. حل باستخدام Backward Substitution.
2. The Sorting Landscape (Mod 3, 4, 5) 2. مشهد الفرز (Mod 3, 4, 5)
| Algorithm الخوارزمية | Strategy الاستراتيجية | Best Case Best Case | Average Average | Worst Case Worst Case | Stable? مستقر؟ | In-Place? في المكان؟ |
|---|---|---|---|---|---|---|
| Selection Sort Selection Sort | Brute Force Brute Force | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | No لا | Yes نعم |
| Bubble Sort Bubble Sort | Brute Force Brute Force | $O(n)$ | $O(n^2)$ | $O(n^2)$ | Yes نعم | Yes نعم |
| Insertion Sort Insertion Sort | Decrease (by 1) Decrease (by 1) | $O(n)$ | $O(n^2)$ | $O(n^2)$ | Yes نعم | Yes نعم |
| Merge Sort Merge Sort | Divide & Conquer Divide & Conquer | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | Yes نعم | No لا |
| Quick Sort Quick Sort | Divide & Conquer Divide & Conquer | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | No لا | Yes نعم |
* Bubble/Insertion Best Case: Already Sorted Array. QuickSort Worst Case: Sorted Array with bad pivot. * Bubble/Insertion Best Case: مصفوفة مرتبة بالفعل || QuickSort Worst Case: مصفوفة مرتبة مع محور (pivot) سيء.
3. Advanced Techniques (Mod 4-6) 3. تقنيات متقدمة (Mod 4-6)
Decrease & Conquer Decrease & Conquer
-
Decrease by Constant:
Decrease by Constant:
DFS, BFS, Topological Sort (Source Removal). DFS, BFS, Topological Sort (إزالة المصدر). -
Decrease by Factor:
Decrease by Factor:
Binary Search ($O(\log n)$). Recurrence: $T(n) = T(n/2) + 1$. Binary Search ($O(\log n)$). Recurrence: $T(n) = T(n/2) + 1$. -
Variable Size:
Variable Size:
Euclid's GCD, QuickSelect ($O(n)$ avg). Euclid's GCD, QuickSelect ($O(n)$ avg).
Divide & Conquer Divide & Conquer
$T(n) = aT(n/b) + f(n)$
- If $a > b^d \to O(n^{\log_b a})$ If $a > b^d \to O(n^{\log_b a})$
- If $a = b^d \to O(n^d \log n)$ If $a = b^d \to O(n^d \log n)$
- If $a < b^d \to O(n^d)$ If $a < b^d \to O(n^d)$
Ex: Strassen's ($O(n^{2.8})$), Tree Traversals ($O(n)$). أمثلة: Strassen's ($O(n^{2.8})$), Tree Traversals ($O(n)$).
Transform & Conquer Transform & Conquer
-
Presorting:
Presorting:
Sort first ($n \log n$) to make searching ($O(\log n)$) or uniqueness check ($O(n)$) faster. الفرز أولاً ($n \log n$) لجعل البحث ($O(\log n)$) أو التحقق من التفرد ($O(n)$) أسرع. -
Representation Change:
Representation Change:
AVL Trees (Balanced BST). Height diff $\le 1$. AVL Trees (Balanced BST). فرق الارتفاع $\le 1$. -
Problem Reduction:
Problem Reduction:
LCM via GCD ($LCM = u \cdot v / GCD$). LCM عبر GCD ($LCM = u \cdot v / GCD$).
The Mega Exam Vault خزنة الاختبار الكبرى
Top Tricks from Modules 1-6 أهم الحيل من الوحدات 1-6
TRAP: Input Size فخ: حجم المدخلات (Input Size)
For number problems (like Primality Test or factoring), the input size $n$ is the number of bits ($\log_2 \text{value}$), NOT the magnitude of the number itself. في المشاكل الرقمية (مثل اختبار الأولية أو التحليل)، حجم المدخلات $n$ هو عدد البتات ($\log_2 \text{value}$)، وليس مقدار الرقم نفسه.
TRAP: DFS vs BFS Complexity فخ: تعقيد DFS vs BFS
The complexity depends on the Data Structure.
Adjacency Matrix: $O(|V|^2)$.
Adjacency List: $O(|V| + |E|)$.
Never just say "$O(N)$".
التعقيد يعتمد على هيكل البيانات (Data Structure).
Adjacency Matrix: $O(|V|^2)$.
Adjacency List: $O(|V| + |E|)$.
لا تقل أبداً "$O(N)$" فقط.
TRAP: QuickSort Worst Case فخ: QuickSort Worst Case
"Is QuickSort always $O(n \log n)$?"
NO. If the array is already sorted and you pick the first element as pivot, it becomes $O(n^2)$. Randomizing the pivot fixes this probabilistically.
"هل QuickSort دائماً $O(n \log n)$؟"
لا. إذا كانت المصفوفة مرتبة بالفعل واخترت العنصر الأول كمحور (pivot)، يصبح $O(n^2)$. اختيار المحور عشوائياً يحل هذه المشكلة احتمالياً.
TRAP: Topo Sort Cycles فخ: دورات Topo Sort
Topological Sort is IMPOSSIBLE if the graph has a Cycle. It only works on DAGs. If an exam question asks for a topo sort of a cyclic graph, write "No Solution". الـ Topological Sort مستحيل إذا كان الرسم البياني يحتوي على دورة (Cycle). يعمل فقط على الـ DAGs. إذا طلب الاختبار فرزاً طوبولوجياً لرسم بياني دوري، اكتب "لا يوجد حل (No Solution)".
SECRET: Binary Search Ceiling سر: Binary Search Ceiling
When calculating mid $\lfloor (L+R)/2 \rfloor$, if the array size is even, it picks the left middle. Be consistent in your trace tables. عند حساب المنتصف $\lfloor (L+R)/2 \rfloor$، إذا كان حجم المصفوفة زوجياً، فإنه يختار المنتصف الأيسر. كن متسقاً في جداول التتبع الخاصة بك.
SECRET: Constant Factors سر: العوامل الثابتة (Constant Factors)
Why use Insertion Sort if it's $O(n^2)$? Because for very small $n$ (like $n < 20$), its small constant factor makes it faster than MergeSort or QuickSort. لماذا نستخدم Insertion Sort إذا كان $O(n^2)$؟ لأنه بالنسبة لـ $n$ صغير جداً (مثل $n < 20$)، فإن عامله الثابت الصغير يجعله أسرع من MergeSort أو QuickSort.