Transform-and-Conquer Transform-and-Conquer
Solve a difficult problem by transforming it into a simpler or more convenient form. "If you can't solve the problem, change the problem." حل مشكلة صعبة عن طريق تحويلها إلى شكل أبسط أو أكثر ملاءمة. "إذا لم تستطع حل المشكلة، قم بتغيير المشكلة."
The Three Variations الاختلافات الثلاثة (Three Variations)
Instance Simplification Instance Simplification (تبسيط الحالة)
Transform the instance into a simpler/more convenient property.
تحويل الحالة (instance) إلى خاصية أبسط / أكثر ملاءمة.
Ex: Presorting, Gaussian Elim. Ex: Presorting, Gaussian Elim.
Representation Change Representation Change (تغيير التمثيل)
Transform the instance into a different representation.
تحويل الحالة إلى تمثيل مختلف (different representation).
Ex: AVL Trees, Heaps, 2-3 Trees. Ex: AVL Trees, Heaps, 2-3 Trees.
Problem Reduction Problem Reduction (تقليص المشكلة)
Transform the problem into a totally different problem for which an algorithm is known. تحويل المشكلة إلى مشكلة مختلفة تماماً يوجد لها خوارزمية معروفة.
Ex: LCM via GCD, Linear Prog. Ex: LCM via GCD, Linear Prog.
Presorting Presorting
Many problems become trivial if the input array is sorted first. The cost of sorting ($O(n \log n)$) is often justified if it avoids an $O(n^2)$ brute-force solution. تصبح العديد من المشاكل بديهية إذا تم فرز مصفوفة الإدخال (sorted) أولاً. غالباً ما تكون تكلفة الفرز ($O(n \log n)$) مبررة إذا كانت تجنبنا حل الـ Brute-Force ذو التكلفة $O(n^2)$.
| Problem المشكلة | Brute Force Brute Force | Presorting Approach نهج الـ Presorting | Total Efficiency الكفاءة الكلية |
|---|---|---|---|
| Element Uniqueness Element Uniqueness | $O(n^2)$ | Sort, then check neighbors ($A[i] == A[i+1]$). قم بالفرز، ثم افحص الجيران ($A[i] == A[i+1]$). | $O(n \log n)$ |
| Computing Mode Computing Mode | $O(n^2)$ | Sort, then find longest run of equal values. قم بالفرز، ثم ابحث عن أطول سلسلة من القيم المتساوية. | $O(n \log n)$ |
| Searching Searching | $O(n)$ | Sort, then Binary Search. قم بالفرز، ثم استخدم Binary Search. | $O(n \log n)$ + $O(\log n)$ |
Gaussian Elimination Gaussian Elimination
Used to solve systems of linear equations $Ax = b$, find matrix inverses, or computing determinants. تستخدم لحل أنظمة المعادلات الخطية $Ax = b$، إيجاد معكوس المصفوفة، أو حساب المحددات (Determinants).
The Transformation التحويل (The Transformation)
Transform the matrix $A$ into an Upper Triangular Matrix (all zeros below diagonal) using elementary row operations. Then solve via backward substitution. حول المصفوفة $A$ إلى Upper Triangular Matrix (كل ما تحت القطر أصفار) باستخدام عمليات الصف الأولية. ثم قم بالحل عبر التعويض العكسي (backward substitution).
AVL Trees AVL Trees
The Problem with standard BST المشكلة في الـ BST القياسية
If you insert sorted data ($1, 2, 3, 4, 5$) into a Binary Search Tree, it becomes a linked list (skewed). Search becomes $O(n)$ instead of $O(\log n)$. إذا قمت بإدراج بيانات مفروزة ($1, 2, 3, 4, 5$) في Binary Search Tree، فإنها تصبح قائمة مرتبطة (مائلة/Skewed). يصبح البحث $O(n)$ بدلاً من $O(\log n)$.
AVL Tree (Adelson-Velsky and Landis) AVL Tree (Adelson-Velsky and Landis)
A BST that maintains Balance. For every node, the height difference between left and right subtrees (Balance Factor) must be $-1, 0, \text{ or } 1$. If it becomes $\pm 2$, we Rotate.
شجرة BST تحافظ على التوازن (Balance). لكل عقدة، يجب أن يكون فرق الارتفاع بين الأشجار الفرعية اليسرى واليمنى (Balance Factor) هو $-1 \text { وأ } 0 \text { وأ } 1$
إذا أصبح $\pm 2$، نقوم بعملية تدوير (Rotate).
Used for LL or RR imbalance. One move fixes the tree. تستخدم لعدم التوازن LL أو RR. حركة واحدة تصلح الشجرة.
Used for LR or RL imbalance. Two moves (Left-Right or Right-Left) required. تستخدم لعدم التوازن LR أو RL. حركتان (Left-Right أو Right-Left) مطلوبتان.
The Exam Vault خزنة الاختبار
Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ
TRAP: Presorting Cost فخ: تكلفة الـ Presorting
"If we presort the array, searching is $O(\log n)$."
Technically true, but misleading. The total cost is Sort + Search = $O(n \log n) + O(\log n) = O(n \log n)$. Do not ignore the sorting cost in your analysis.
"إذا قمنا بفرز المصفوفة مسبقاً (Presort)، يصبح البحث $O(\log n)$."
صحيح تقنياً، لكنه مضلل. التكلفة الكلية هي الفرز + البحث = $O(n \log n) + O(\log n) = O(n \log n)$. لا تتجاهل تكلفة الفرز في تحليلك.
TRAP: Gaussian Division فخ: قسمة Gaussian
In Gaussian Elimination, we divide by the pivot $A[i,i]$. If $A[i,i] = 0$, the algorithm fails. We must swap rows (Partial Pivoting) to fix this. This is a common "edge case" exam question. في Gaussian Elimination، نقسم على الـ pivot $A[i,i]$. إذا كان $A[i,i] = 0$، تفشل الخوارزمية. يجب تبديل الصفوف (Partial Pivoting) لإصلاح ذلك. هذا سؤال "حالة طرفية" شائع في الاختبارات.
SECRET: AVL vs Red-Black سر: AVL vs Red-Black
AVL trees are strictly balanced (height diff $\le 1$). Red-Black trees are loosely balanced (height diff up to factor of 2). AVL provides faster lookups, but slower insertions/deletions due to frequent rotations. أشجار AVL متوازنة بصرامة (فرق الارتفاع $\le 1$). أشجار Red-Black متوازنة بشكل فضفاض (فرق الارتفاع يصل لعامل 2). توفر AVL بحثاً أسرع، ولكن إدراج/حذف أبطأ بسبب التدوير المتكرر.
KEY CONCEPT: LU Decomposition مفهوم أساسي: LU Decomposition
Gaussian Elimination effectively decomposes matrix $A$ into Lower ($L$) and Upper ($U$) triangular matrices ($A = LU$). This transformation allows solving $Ax=b$ quickly for multiple different vectors $b$. تقوم Gaussian Elimination فعلياً بتحليل المصفوفة $A$ إلى مصفوفات مثلثية سفلى ($L$) وعليا ($U$) ($A = LU$). هذا التحويل يسمح بحل $Ax=b$ بسرعة لمتجهات $b$ مختلفة متعددة.