Divide-and-Conquer Divide-and-Conquer (فرق تسد)

The most famous algorithm design paradigm. Divide the problem into equal sub-problems, solve them recursively, and combine the results. أشهر نموذج لتصميم الخوارزميات. قسم المشكلة إلى مشاكل فرعية متساوية، حلها بشكل متكرر (recursively)، وادمج النتائج.

Mergesort Mergesort Quicksort Quicksort Master Theorem Master Theorem (النظرية الأساسية) Strassen's Matrix Strassen's Matrix

The Strategy & Analysis الاستراتيجية والتحليل

The 3-Step Process العملية ذات الخطوات الثلاث

  • 1

    Divide Divide (التقسيم)

    Split problem into several subproblems of the same type (ideally equal size). تقسيم المشكلة إلى عدة مشاكل فرعية من نفس النوع (مثالياً بحجم متساوٍ).

  • 2

    Conquer Conquer (الحل/السيطرة)

    Solve subproblems recursively. حل المشاكل الفرعية بشكل تكراري (Recursively).

  • 3

    Combine Combine (الدمج)

    Merge solutions to get the original answer. دمج الحلول للحصول على الإجابة الأصلية.

The Master Theorem The Master Theorem (النظرية الأساسية)

For recurrence $T(n) = aT(n/b) + f(n)$ where $f(n) \in O(n^d)$: للعلاقة التكرارية $T(n) = aT(n/b) + f(n)$ حيث $f(n) \in O(n^d)$:

Case 1: $a < b^d$ $T(n) \in O(n^d)$
Case 2: $a = b^d$ $T(n) \in O(n^d \log n)$
Case 3: $a > b^d$ $T(n) \in O(n^{\log_b a})$

The Sorting Titans عمالقة الفرز (The Sorting Titans)

Mergesort Mergesort

Stable

Divides array into two halves, sorts recursively, then merges sorted halves. يقسم المصفوفة إلى نصفين، يفرزهما بشكل تكراري، ثم يدمج (merges) النصفين المرتبين.

Recurrence: $T(n) = 2T(n/2) + cn$
Complexity: $O(n \log n)$ (Always)
Drawback: Requires $O(n)$ extra space.

Quicksort Quicksort

In-place

Divides based on a pivot. Elements $<$ pivot go left, $>$ pivot go right. Then sorts partitions. يقسم بناءً على محور (pivot). العناصر $<$ المحور تذهب لليسار، $>$ المحور تذهب لليمين. ثم يفرز الأقسام.

Best/Avg: $O(n \log n)$
Worst: $O(n^2)$ (Sorted Array)
Note: Faster than Mergesort on random data.

Advanced Applications تطبيقات متقدمة

Large Integer Multiplication ضرب الأعداد الصحيحة الكبيرة

Brute force multiplication takes $O(n^2)$. By using a algebraic trick to compute $(A_1+A_2)(B_1+B_2)$, we reduce multiplications from 4 to 3. الضرب بالقوة الغاشمة يستغرق $O(n^2)$. باستخدام خدعة جبرية لحساب $(A_1+A_2)(B_1+B_2)$، نقلل عمليات الضرب من 4 إلى 3.

Recurrence: $T(n) = 3T(n/2)$ $O(n^{1.585})$

Strassen's Matrix Multiplication ضرب مصفوفات ستراسن (Strassen)

Standard matrix multiplication takes $O(n^3)$ (8 mults for 2x2). Strassen found a way to do it with 7 multiplications. ضرب المصفوفات القياسي يستغرق $O(n^3)$ (8 عمليات ضرب لـ 2x2). وجد Strassen طريقة للقيام بذلك بـ 7 عمليات ضرب.

Recurrence: $T(n) = 7T(n/2)$ $O(n^{2.807})$

Binary Tree Traversals اجتياز الأشجار الثنائية

Recursive algorithms defined by when the Root is visited . خوارزميات تكرارية (Recursive) تُعرف بناءً على متى تتم زيارة الجذر (Root).

Preorder Preorder

Root $\to$ Left $\to$ Right

Inorder Inorder

Left $\to$ Root $\to$ Right

Postorder Postorder

Left $\to$ Right $\to$ Root

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

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

TRAP: Quicksort's Worst Case فخ: أسوأ حالة لـ Quicksort

"Is Quicksort always $O(n \log n)$?"
NO! If the array is already sorted (or reverse sorted) and you pick the first element as pivot, it degrades to $O(n^2)$. This is the most common trick question . "هل Quicksort دائماً $O(n \log n)$؟"
لا! إذا كانت المصفوفة مرتبة بالفعل (أو مرتبة عكسياً) واخترت العنصر الأول كمحور، فإنها تتدهور إلى $O(n^2)$. هذا هو السؤال الخادع الأكثر شيوعاً.

TRAP: Mergesort Space فخ: مساحة Mergesort

Mergesort is "perfect" in time ($O(n \log n)$), but it is NOT in-place. It requires $O(n)$ extra auxiliary space for the merge step. If memory is tight, QuickSort is preferred . Mergesort "مثالية" في الوقت ($O(n \log n)$)، لكنها ليست في المكان (in-place). تتطلب مساحة إضافية $O(n)$ لخطوة الدمج. إذا كانت الذاكرة ضيقة، يفضل QuickSort.

SECRET: Master Theorem Shortcut سر: اختصار Master Theorem

Compare $a$ vs $b^d$.
If $a > b^d$, the recursion (leaves) dominates ($O(n^{\log_b a})$).
If $a < b^d$, the work at root dominates ($O(n^d)$).
If equal, multiply by $\log n$ ($O(n^d \log n)$). قارن $a$ مقابل $b^d$.
إذا كان $a > b^d$، فإن التكرار (الأوراق) هو المسيطر ($O(n^{\log_b a})$).
إذا كان $a < b^d$، فإن العمل عند الجذر هو المسيطر ($O(n^d)$).
إذا تساويا، اضرب في $\log n$ ($O(n^d \log n)$).

KEY CONCEPT: Strassen's Limit مفهوم مفتاحي: حد Strassen

Strassen's algorithm ($O(n^{2.8})$) is asymptotically faster than Brute Force ($O(n^3)$), but it has a huge constant factor. It is only faster in practice for very large matrices ($N > 100$) . خوارزمية Strassen ($O(n^{2.8})$) أسرع مقاربة من القوة الغاشمة ($O(n^3)$)، لكن لديها عامل ثابت ضخم. هي أسرع فقط عملياً للمصفوفات الكبيرة جداً ($N > 100$).