Final Exam Master Review المراجعة الشاملة للاختبار النهائي

The ultimate synthesis of Modules 7 through 13. From Heaps to NP-Completeness, this is your source of truth. التلخيص النهائي للوحدات من 7 إلى 13. من Heaps إلى NP-Completeness، هذا هو مرجعك الأساسي.

Transform & Space-Time (Mod 7-9) التحويل والزمكان (Mod 7-9)

Heaps & Heapsort Heaps و Heapsort

Heap: An array viewed as a nearly complete binary tree. Heap: مصفوفة تُعرض كشجرة ثنائية شبه كاملة (Nearly Complete Binary Tree).

  • Structure:الهيكل: Filled left-to-right. مملوءة من اليسار لليمين.
  • Order:الترتيب: Parent $\ge$ Children (Max-Heap). الأب $\ge$ الأبناء (Max-Heap).
  • Construction:البناء: Bottom-up heapify takes $O(n)$. بناء الكومة من الأسفل للأعلى يستغرق $O(n)$.
  • Sort:الفرز: Swap root/last, heapify. $O(n \log n)$. تبديل الجذر/الأخير، ثم heapify. $O(n \log n)$.

Input Enhancement تحسين الإدخال (Input Enhancement)

Preprocess input to gain speed. معالجة الإدخال مسبقاً لكسب السرعة.

  • Distribution Counting:عد التوزيع: $O(n+k)$ sort for small range $k$. فرز $O(n+k)$ لنطاق صغير $k$.
  • Horspool:Horspool: String matching. Shift table based on last character of pattern. Avg $O(n)$. مطابقة النصوص. جدول الإزاحة يعتمد على آخر حرف في النمط. المتوسط $O(n)$.

Hashing & B-Trees التحويل (Hashing) و B-Trees

Hashing ($O(1)$ avg) Hashing ($O(1)$ متوسط) Open (Chaining) vs Closed (Open Addressing). مفتوح (Chaining) مقابل مغلق (عنونة مفتوحة).
B-Trees B-Trees Balanced trees for Disk Storage. Nodes have multiple keys to minimize height (disk seeks). أشجار متوازنة لـ تخزين القرص. العقد تحتوي على مفاتيح متعددة لتقليل الارتفاع (disk seeks).

Algorithm Design Paradigms نماذج تصميم الخوارزميات

Dynamic Programming البرمجة الديناميكية (Dynamic Programming)

Solves overlapping subproblems once and stores the result (Memoization/Tabulation). تحل المشاكل الفرعية المتداخلة مرة واحدة وتخزن النتيجة (Memoization/Tabulation).

Problemالمشكلة Logicالمنطق Complexityالتعقيد
Knapsack 0/1 Knapsack 0/1 Max(Exclude, Include) Max(استبعاد، تضمين) $O(nW)$
Warshall Warshall Transitive Closure (OR/AND) الإغلاق المتعدي (OR/AND) $O(n^3)$
Floyd Floyd All-Pairs Shortest Path أقصر مسار لكل الأزواج $O(n^3)$

Greedy Technique تقنية الجشع (Greedy Technique)

Makes the locally optimal choice at each step. Fast, but only works for specific problems (Matroids). تتخذ الخيار الأمثل محلياً في كل خطوة. سريعة، لكنها تعمل فقط لمشاكل محددة (Matroids).

Prim's Algorithm Prim's Algorithm

Grow 1 tree. Use Priority Queue. Good for Dense graphs. تنمية شجرة واحدة. استخدم Priority Queue. جيد للرسوم الكثيفة.

Kruskal's Algorithm Kruskal's Algorithm

Merge forests. Use Union-Find. Good for Sparse graphs. دمج الغابات. استخدم Union-Find. جيد للرسوم المتناثرة.

Dijkstra Dijkstra

Shortest Path. Like Prim's but accumulates weight. No Negative Edges. أقصر مسار. مثل Prim لكن يراكم الوزن. لا أضلاع سالبة.

Huffman Huffman

Lossless Compression. Prefix-free codes. Bottom-up tree build. ضغط بدون فقدان. أكواد خالية من البادئة. بناء الشجرة من الأسفل للأعلى.

The Limits of Computing حدود الحوسبة

P

Class P الفئة P

Solvable in Polynomial Time ($O(n^k)$). قابلة للحل في وقت كثير الحدود ($O(n^k)$).

NP

Class NP الفئة NP

Solution Verifiable in Polynomial Time. (Includes P). الحل قابل للتحقق في وقت كثير الحدود. (تتضمن P).

NPC

NP-Complete NP-Complete

The hardest problems in NP. If one is solved in P, $P=NP$. (e.g., TSP, SAT). أصعب المشاكل في NP. إذا حُلت واحدة في P، فإن $P=NP$. (مثل TSP, SAT).

How to Cope with NP-Hard? كيف نتعامل مع NP-Hard؟

1. Exact Solutions (Smart Brute Force) 1. حلول دقيقة (Smart Brute Force)

Backtracking:Backtracking: DFS state-space tree. Prune non-promising nodes. (N-Queens). شجرة فضاء حالة DFS. قلم العقد غير الواعدة. (N-Queens).
Branch-and-Bound:Branch-and-Bound: Optimization. Use bounds to prune. (Knapsack/TSP). التحسين. استخدم الحدود للتقليم. (Knapsack/TSP).

2. Approximation Algorithms 2. خوارزميات التقريب

Accept a sub-optimal answer for speed. قبول إجابة دون المستوى الأمثل للسرعة.
Nearest Neighbor (TSP):أقرب جار (TSP): Greedy. Unbounded error. جشع. خطأ غير محدود.
Multifragment Heuristic:Multifragment Heuristic: Sort edges, add if no cycle/degree<3. رتب الأضلاع، أضف إذا لم يكن هناك دورة/درجة < 3.

The Mega Exam Vault (Finals Edition) خزنة الاختبار الكبرى (إصدار النهائيات)

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

TRAP: Heapsort Stability فخ: استقرار Heapsort

Heapsort is NOT stable. The operation of swapping the root with the last leaf destroys the relative order of equal elements. Do not use it if stability is required (Use MergeSort instead). الـ Heapsort ليس مستقراً (Not Stable). عملية تبديل الجذر مع الورقة الأخيرة تدمر الترتيب النسبي للعناصر المتساوية. لا تستخدمه إذا كان الاستقرار مطلوباً (استخدم MergeSort بدلاً منه).

TRAP: Hashing "O(1)" فخ: Hashing "O(1)"

Never say "Hashing is O(1)" without adding "on average". In the worst case (all keys collide), it degrades to $O(n)$. This distinction is often a 5-point deduction in exams. لا تقل أبداً "Hashing هو O(1)" دون إضافة "في المتوسط". في أسوأ الحالات (تضارب جميع المفاتيح)، يتراجع إلى $O(n)$. هذا التمييز غالباً ما يخصم 5 درجات في الامتحانات.

TRAP: NP Definition فخ: تعريف NP

NP does NOT mean "Not Polynomial". It stands for Nondeterministic Polynomial. It means a solution can be verified in polynomial time. P is a subset of NP. NP لا تعني "Not Polynomial". إنها تعني Nondeterministic Polynomial. تعني أن الحل يمكن التحقق منه في وقت كثير الحدود. P هي مجموعة فرعية من NP.

SECRET: Prim vs Kruskal سر: Prim مقابل Kruskal

When to use which?
Dense Graphs ($E \approx V^2$): Use Prim's (with Adjacency Matrix).
Sparse Graphs ($E \approx V$): Use Kruskal's (depends on edges). متى تستخدم أياً منهما؟
الرسوم الكثيفة ($E \approx V^2$): استخدم Prim's (مع مصفوفة الجوار).
الرسوم المتناثرة ($E \approx V$): استخدم Kruskal's (يعتمد على الأضلاع).

SECRET: Knapsack Distinction سر: التمييز بين أنواع Knapsack

Fractional Knapsack: Solvable by Greedy (Value/Weight ratio).
0/1 Knapsack: Greedy Fails. Requires Dynamic Programming ($O(nW)$). Fractional Knapsack: قابلة للحل بواسطة Greedy (نسبة القيمة/الوزن).
0/1 Knapsack: تفشل Greedy. تتطلب البرمجة الديناميكية ($O(nW)$).

SECRET: Backtracking vs B&B سر: Backtracking مقابل B&B

Both use state-space trees.
Backtracking: For finding *all* solutions or feasibility (N-Queens).
Branch-and-Bound: For *optimization* (Min/Max cost). Uses bounds to prune more aggressively. كلاهما يستخدم أشجار فضاء الحالة.
Backtracking: لإيجاد *كل* الحلول أو الجدوى (N-Queens).
Branch-and-Bound: لـ *التحسين* (أقل/أقصى تكلفة). يستخدم الحدود للتقليم بقوة أكبر.