Decrease-and-Conquer Decrease-and-Conquer (التقليص والسيطرة)

Exploiting the relationship between a problem of size $n$ and a smaller instance to solve it efficiently. استغلال العلاقة بين مشكلة بحجم $n$ ونموذج أصغر منها لحلها بكفاءة.

Insertion Sort Insertion Sort Topological Sort Topological Sort Binary Search Binary Search QuickSelect QuickSelect

Three Variations of Reduction ثلاثة أنواع من التقليص (Reduction)

Decrease by Constant تقليص بمقدار ثابت

Reduce problem size by a fixed amount (usually 1). تقليل حجم المشكلة بمقدار ثابت (عادة 1).

$f(n) \rightarrow f(n-1)$

Ex: Insertion Sort, DFS, BFS أمثلة: Insertion Sort, DFS, BFS

Decrease by Factor تقليص بعامل (Factor)

Reduce problem size by a factor (usually 2, i.e., half). تقليل حجم المشكلة بعامل (عادة 2، أي النصف).

$f(n) \rightarrow f(n/2)$

Ex: Binary Search أمثلة: Binary Search

Variable Decrease تقليص متغير (Variable)

Size reduction pattern varies at each step. نمط تقليل الحجم يختلف في كل خطوة.

$f(n) \rightarrow f(?)$

Ex: Euclid's GCD, Selection Problem أمثلة: Euclid's GCD, Selection Problem

Insertion Sort Insertion Sort (الفرز بالإدراج)

The Logic المنطق

Think of sorting cards in your hand. You pick the next card ($A[i]$) and insert it into the correct position among the already sorted cards to its left ($A[0..i-1]$). This is a recursive idea implemented iteratively (Bottom-Up) . فكر في ترتيب البطاقات في يدك. تلتقط البطاقة التالية ($A[i]$) وتدخلها في الموضع الصحيح بين البطاقات المرتبة بالفعل على يسارها ($A[0..i-1]$). هذه فكرة عودية (Recursive) تنفذ بشكل تكراري (Bottom-Up).

for i $\leftarrow$ 1 to n-1 do
  v $\leftarrow$ A[i]
  j $\leftarrow$ i - 1
  while j $\ge$ 0 and A[j] > v do
    A[j+1] $\leftarrow$ A[j] // Shift right
    j $\leftarrow$ j - 1
  A[j+1] $\leftarrow$ v // Insert

Worst Case الحالة الأسوأ (Worst Case)

Reverse sorted array. Each element must move all the way to the start.
$C_{worst}(n) \in O(n^2)$ مصفوفة مرتبة عكسياً. يجب أن يتحرك كل عنصر طوال الطريق إلى البداية.
$C_{worst}(n) \in O(n^2)$

Best Case الحالة الأفضل (Best Case)

Already sorted array. Only 1 comparison per element.
$C_{best}(n) = n - 1 \in O(n)$ مصفوفة مرتبة بالفعل. مقارنة واحدة فقط لكل عنصر.
$C_{best}(n) = n - 1 \in O(n)$

Average Case الحالة المتوسطة (Average Case)

Random data. Average $\approx n^2/4$. Still quadratic, but twice as fast as Selection Sort on average . بيانات عشوائية. المتوسط $\approx n^2/4$. لا تزال تربيعية، ولكن أسرع مرتين من Selection Sort في المتوسط.

Topological Sorting الفرز الطوبولوجي (Topological Sorting)

The problem of ordering vertices in a Directed Acyclic Graph (DAG) such that for every edge $u \to v$, $u$ comes before $v$ in the ordering. Used for scheduling tasks with prerequisites . مشكلة ترتيب الرؤوس (Vertices) في Directed Acyclic Graph (DAG) بحيث أنه لكل حافة $u \to v$، يأتي $u$ قبل $v$ في الترتيب. يستخدم لجدولة المهام ذات المتطلبات المسبقة.

Method 1: Source Removal الطريقة 1: إزالة المصدر (Source Removal)

  1. Identify a Source (vertex with in-degree 0). تحديد المصدر (Source) (رأس بدرجة دخول 0).
  2. Delete it and all outgoing edges. حذفه وجميع الحواف الخارجة منه.
  3. Repeat until graph is empty. التكرار حتى يصبح الرسم البياني فارغاً.
  4. Order of deletion = Topological Sort . ترتيب الحذف = الفرز الطوبولوجي.

Method 2: DFS Based الطريقة 2: معتمدة على DFS

  1. Perform DFS traversal. إجراء اجتياز DFS.
  2. Note the order in which vertices are popped (dead ends). ملاحظة الترتيب الذي يتم فيه إخراج (pop) الرؤوس (النهايات المسدودة).
  3. Reverse that order. عكس ذلك الترتيب.

Binary Search Binary Search (البحث الثنائي)

The ultimate example of efficiency. Reduces problem size by half at every step. Requires a sorted array. المثال الأسمى للكفاءة. يقلل حجم المشكلة بمقدار النصف في كل خطوة. يتطلب مصفوفة مرتبة.

Recurrence Relation:
 علاقة التكرار:
 $C_{worst}(n) = C_{worst}(\lfloor n/2 \rfloor) + 1$
$C_{worst}(1) = 1$
$O(\log_2 n)$

Search Space Halves Every Step مساحة البحث تتنصف كل خطوة

Selection Problem (QuickSelect) مشكلة الاختيار (QuickSelect)

Finding the $k$-th Smallest Element إيجاد العنصر الـ $k$ الأصغر

Can we find the median without sorting the whole array? هل يمكننا إيجاد الوسيط دون ترتيب المصفوفة بالكامل؟

Lomuto Partition Lomuto Partition

Uses Partitioning (like QuickSort). Pick a pivot $p$. Rearrange array so elements $< p$ are left, $> p$ are right. يستخدم التقسيم (Partitioning) (مثل QuickSort). اختر محوراً (pivot) $p$. أعد ترتيب المصفوفة بحيث تكون العناصر $< p$ يساراً، والعناصر $> p$ يميناً.

  • If pivot index $s = k-1$, we found it! إذا كان مؤشر المحور $s = k-1$، لقد وجدناه!
  • If $s > k-1$, look in left part (discard right). إذا كان $s > k-1$، ابحث في الجزء الأيسر (تجاهل الأيمن).
  • If $s < k-1$, look in right part (discard left). إذا كان $s < k-1$، ابحث في الجزء الأيمن (تجاهل الأيسر).
Best/Avg Case أفضل/متوسط حالة $O(n)$
Worst Case أسوأ حالة $O(n^2)$

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Insertion Sort Efficiency فخ: كفاءة Insertion Sort

"Is Insertion Sort always slow?"
No! On an almost sorted array, it runs in $O(n)$ time (Best Case). It is often faster than QuickSort for very small arrays ($n < 20$) . "هل Insertion Sort بطيء دائماً؟"
لا! في مصفوفة شبه مرتبة، يعمل في وقت $O(n)$ (أفضل حالة). وغالباً ما يكون أسرع من QuickSort للمصفوفات الصغيرة جداً ($n < 20$).

TRAP: Cycles in Topo Sort فخ: الدورات في Topo Sort

Topological Sort is IMPOSSIBLE if the graph has a Cycle. It only works on DAGs (Directed Acyclic Graphs). If an exam question asks you to topo-sort a graph with a loop, the answer is "No Solution". الفرز الطوبولوجي مستحيل إذا كان الرسم البياني يحتوي على دورة (Cycle). يعمل فقط على DAGs. إذا طلب منك سؤال اختبار فرز رسم بياني به حلقة طوبولوجياً، فالإجابة هي "لا يوجد حل".

SECRET: Binary Search Ceiling سر: سقف البحث الثنائي

When calculating mid, we usually do $\lfloor (l+r)/2 \rfloor$. If the array size is even, this picks the left middle. Be careful tracing this manually in exams; picking the wrong middle index changes the trace path. عند حساب المنتصف، عادة ما نستخدم $\lfloor (l+r)/2 \rfloor$. إذا كان حجم المصفوفة زوجياً، فهذا يختار المنتصف الأيسر. كن حذراً عند تتبع هذا يدوياً في الاختبارات؛ اختيار مؤشر المنتصف الخاطئ يغير مسار التتبع.

KEY CONCEPT: The Pivot مفهوم مفتاحي: المحور (The Pivot)

The efficiency of QuickSelect (and QuickSort) depends entirely on the Pivot. If the pivot splits the array into 0 and $n-1$ elements every time, you hit the $O(n^2)$ worst case . كفاءة QuickSelect (و QuickSort) تعتمد كلياً على المحور (Pivot). إذا قسم المحور المصفوفة إلى 0 و $n-1$ عنصر في كل مرة، فإنك تصل إلى أسوأ حالة $O(n^2)$.