====== طراحی الگوریتم‌ها ======


===== تحلیل الگوریتم‌ها =====
==== اثبات الگوریتم‌ها با استقرا و ناوردایی ====
==== مفهوم مرتبه (Order) ====
  * پیچیدگی زمان اجرا و حافظه
  * محاسبه‌ی مرتبه‌ی روابط بازگشتی

===== الگوریتم‌های پایه‌ای =====
==== جست‌وجوی دودویی ====
==== مرتب‌سازی و مطالب مرتبط ====
=== مرتب‌سازی خطی ===
  * count-sort
  * bucket-sort
  * radix-sort
=== مرتب‌سازی مبتنی بر مقایسه ===
  * bubble-sort
  * selection-sort
  * insertion-sort
  * merge-sort
  * heap-sort
  * quick-sort
  * حد پایین مرتب‌سازی
=== Order Statistics ===
  * الگوریتم تصادفی شناسایی عنصر $k$ام
  * الگوریتم‌ شناسایی میانه در $O(n)$

===== داده‌ساختارها ===== 
==== داده‌ساختارهای نگه‌دارنده (Container) ====
  * Array و Sorted-Array
  * Linked-List
  * Heap
  * BST
    * RBT
    * Order-Statistic Tree
  * Hash Table
  *  مقایسه‌ی داده‌ساختارهای نگه‌دارنده (خاصیت‌ها: sequential, ordered، عملیات‌ها: search, random-access, iterate, add, batch-add, delete, findMin)

==== داده‌ساختارهای دیگر ====
  * صف و پشته
  * درخت عبارت
  * درخت Trie
  * Distjoint Sets
  * اعداد بزرگ
  * Segment Tree
  * Fenwick Tree
  * ساختارهای Range Minimum Query
  * Binary Indexed Tree
  * Interval Tree
  * Range Tree
  * Heavy-Light Tree Decomposition
===== الگوهای طراحی الگوریتم =====
==== طراحی الگوریتم با روش‌های استقرایی ====
  * مسئله‌ی زیرگراف القایی بیشینه با حداقل درجه $k$
  * مسئله‌ی محاسبه‌ی مقدار چندجمله‌ای در $O(n)$
  * مسئله‌ی زیررشته‌ی با بیشترین مجموع
  * مسئله‌ی شناسایی celebrity
  * مسئله‌ی شناسایی majority
  * مسئله‌ی نمایش در مبنای فاکتوریل

==== بررسی تمام حالات (Brute-Force) ====
  * مسائل مرتبط در USACO به‌خصوص قسمت 1.2
  * back-tracking
    * مسئله‌ی قراردادن وزیر‌ها در صفحه‌ی شطرنج
  * تناظر حالت‌ها با اعداد
    * مسئله‌ی تبدیل جایگشت به عدد و برعکس
==== الگوریتم‌های حریصانه ====
  * فرم کلی اثبات الگوریتم‌های حریصانه
  * مسائل USACO  قسمت 1.3
  * مسئله‌ی زمان‌بندی واحد‌های کاری با ضرب‌العجل و جریمه
  * مسئله‌ی تطابق و مجموعه‌مستقل بیشینه در درخت
  * مسئله‌ی کد هافمن
  * مسئله‌ی ازدواج پایدار
==== الگوریتم‌های بازگشتی ====
  * مسئله‌ی دنباله‌ی Gray
  * الگوریتم محاسبه‌ی $x^n$ در $O(\log n)$
    * مسئله‌ی حل رابطه‌های بازگشتی خطی در $O(\log n)$
==== تقسیم و حل ====
  * مسئله‌ی Sky Line
  * الگوریتم Karatsuba برای ضرب چندجمله‌ای
  * الگوریتم Strassen برای ضرب ماتریس
  * الگوریتم مبتنی‌بر FFT برای ضرب چندجمله‌ای
==== الگوریتم‌های پویا ====
  * الگوریتم‌های بازگشتی با روش یادداشت‌برداری‌شده (memoized)
  * مسئله‌های سایت http://codeforces.com/blog/entry/325
  * مسئله‌های USACO قسمت 2.2 و 2.3
  * مسئله‌ی خرد کردن پول
  * مسئله‌ی OBST
  * مسئله‌ی زمان‌بندی پردازنده‌های وزن‌دار
==== الگوریتم‌های پویای نمایی ====
  * مسئله‌ی پوشاندن جدول ۱۰×n با دومینو
==== طراحی الگوریتم با تحلیل سرشکن ====
==== مفاهیم پیشرفته ====
  * دوگان و minimax
  * ماتروید
  * شناسایی رده‌ی مسئله از روی LP و دوگان آن

===== الگوریتم‌های گراف =====
==== داده‌ساختارهای گراف ====
  * ماتریس مجاورت 
  * لیست مجاورت
==== پیمایش گراف‌ها ====
  * BFS
  * DFS
  * شناسایی مؤلفه‌های همبندی
  * مسئله‌ی شناسایی کمر گراف
  * مسئله‌ی شناسایی مرکز گراف
  * مسئله‌ی شناسایی قطر گراف
==== الگوریتم‌های ویژه‌ی درخت‌ها ====
  * الگوریتم شناسایی مرکز درخت
  * الگوریتم شناسایی قطر درخت
  * افراز درخت به دو درخت‌ تقریبا هم‌اندازه با حذف یال یا رأس
  * مسئله‌ی هم‌ریختی درخت‌ها
==== الگوریتم‌های ویژه‌ی درخت‌های ریشه‌دار ====
  * پیمایش‌های درخت
    * پیش‌ترتیب
    * میان‌ترتیب
    * پس‌ترتیب
    * ترتیب سطح اول
  * الگوریتم شناسایی پایین‌ترین جد مشترک
==== الگوریتم‌های ویژه‌ی گراف‌های بی‌جهت ====
  * رأس‌های برشی
  * یال‌های برشی
  * مؤلفه‌های دوهمبند
==== الگوریتم‌های ویژه‌ی گراف‌های جهت‌دار ====
  * تست DAG بودن گراف
  * Topological Sorting
  * مؤلفه‌های قویاً همبند
  * بستار تعدی
==== تور اویلری ====
  * ساخت تور اویلری با استقرا
  * الگوریتم فلوری برای گراف‌های بی‌جهت
  * الگوریتم فلوری برای گراف‌های جهت‌دار
  * ساخت تور اویلری به‌کمک DFS
  * مسئله‌ی De Bruijn
==== مسائل کوتاه‌ترین مسیر ====
  * معرفی مفاهیم کوتاه‌ترین گشت و دور منفی
=== کوتاه‌ترین مسیر با یک مبدأ مشخص ===
  * Dijkstra
  * Bellman-Ford
  * الگوریتم $A^*$
  * الگوریتم Leviticus (؟؟؟)
=== کوتاه‌ترین مسیر بین هر جفت رأس ===
  * روش ضرب ماتریسی $O(n3logn)$
  * روش تقسیم و حل (؟؟؟)
  * Floyd-Warshall
  * Johnson (برای گراف‌های خلوت)
=== مسائل مرتبط با کوتاه‌ترین مسیر ===
  * مسئله‌ی شناسایی دور منفی
  * مسئله‌ی شناسایی دور با کم‌ترین میانگین وزن 
  * مسئله‌ی حالت خاص LP با نامساوی‌های دوتایی 
==== Minimum Spanning Tree ====
  * Kruskal
  * Prim
  * مسئله‌ی کوتاه‌ترین مسیر با هزینه‌ی گلوگاهی
==== تطابق بیشینه ====
=== تطابق دوبخشی ===
  * مسائل متناظر با تطابق دوبخشی (پوشش رأسی، پوشش یالی، مجموعه مستقل)
  * الگوریتم Kuhn (تطابق دوبخشی با DFS)
  * الگوریتم Hopcroft-Karp (تطابق دوبخشی با BFS)
=== تطابق دوبخشی کامل با وزن بیشینه ===
=== تطابق بیشینه در گراف‌های کلی ===
  * الگوریتم شکوفه ادموند
  * الگوریتم تصادفی با ماتریس Tutte
==== جریان بیشینه و برش کمینه ====
  * الگوریتم Ford-Fulkerson
  * الگوریتم Edmonds-Karp
  * الگوریتم Dinics
  * الگوریتم Push-relabel
  * الگوریتم Relabel-to-front
  * مسئله‌ی مسیرهای یال‌مجزا
  * مسئله‌ی مسیرهای رأس‌مجزا
  * مسئله‌ی Lower-bound Flow
  * مسئله‌ی Min-Cost Flow

===== الگوریتم‌ها وساختارهای رشته‌ای =====
  * روش‌های مبتنی‌بر Hash در کار با رشته‌ها
==== String Matching ====
    * الگوریتم String Matching بدیهی
    * الگوریتم Rabin-Karp
    * الگوریتم KMP
    * الگوریتم DFA-String-Matching
==== Suffix Tree و Suffix Array ====
==== عبارت‌های ریاضی ====
  * شیوه‌ی نمایش عبارت‌های ریاضی
    * prefix
    * infix
    * postfix
  * مسئله‌ی parse کردن عبارت‌های ریاضی در $O(n)$
  * الگوریتم Shunting-yard

==== متفرقه ====
  * مسئله‌های فصل ۷ از کتاب «مسئله‌های الگوریتمی»

===== الگوریتم‌های مرتبط با منطق و ساختارهای گسسته =====
  * Horn-SAT
  * 2SAT
==== مجموعه‌ی مرتب جزئی ====
    * مسئله‌ی شناسایی بزرگ‌ترین زنجیر
    * مسئله‌ی شناسایی بزرگ‌ترین پادزنجیر
    * مسئله‌ی شناسایی کوچک‌ترین افراز به زنجیر
    * مسئله‌ی شناسایی کوچک‌ترین افراز به پادزنجیر

==== بازی‌ها ==== 
  * بازی‌های منصفانه (Nimِ معادل و MEX و ...)
  * alpha-beta-pruning
  * مسئله‌های فصل ۴ از کتاب «مسئله‌های الگوریتمی»

===== نظریه اعداد =====
  * الگوریتم محاسبه‌ی ب.م.م
  * الگوریتم‌های وارون در $Z_p$
    * پیدا کردن وارون با extended-gcd
    * پیدا کردن وارون با رساندن به‌توان $p-2$
  * باقی‌مانده‌ی چینی

===== الگوریتم‌های هندسی =====
  * مفاهیم اولیه در الگوریتم‌های هندسی
  * اعداد مختلط
  * ضرب داخلی
  * ضرب خارجی
==== محاسبات پایه‌ای هندسه‌ی دوبعدی ====
    * مساحت چندضلعی ساده
    * جهت چندضلعی محدب
    * جهت چندضلعی ساده
    * فاصله‌ی دو نقطه
    * یکه‌کردن بردار
    * فاصله‌ی علامت‌دار نقطه از خط (پاره‌خط)
    * وضعیت نقطه نسبت به خط (پاره‌خط)
    * محاسبه‌ی زاویه‌ی بی‌علامت
    * محاسبه‌ی زاویه‌ی علامت‌دار
    * تعیین نقطه
      * تصویر نقطه روی خط (پاره‌خط)
      * نقطه‌ی متقارن یک نقطه نسبت به یک خط
      * تقاطع دو خط (پاره‌خط)
      * تقاطع‌های دایره و خط (پاره‌خط)
      * تقاطع‌های دو دایره
    * تعیین خط (پاره‌خط)
      * خط عبوری از دو نقطه
      * عمودمنصف دو نقطه
      * نیم‌ساز زاویه
      * خط عبوری از یک نقطه، با یک زاویه‌ی مشخص
      * خط عبوری از یک نقطه، موازی یک خط دیگر
      * خط عبوری از یک نقطه، عمود بر یک خط دیگر
      * مماس مشترک‌های نقطه و دایره
      * مماس مشترک‌های دو دایره
    * تعیین دایره
      * دایره‌ی عبوری از سه نقطه (دایره‌ی محیطی مثلث)
      * دایره‌های مماس با سه خط (دایره‌ی محاطی مثلث)
      * دایره‌های عبوری از دو نقطه و مماس با یک خط
      * دایره‌های عبوری از یک نقطه و مماس با دو خط
      * دایره‌های عبوری از دو نقطه با شعاع مشخص
      * دایره‌های مماس با دو خط با شعاع مشخص
      * دایره‌های عبوری از یک نقطه و مماس با یک خط و با شعاع مشخص
    * محاسبه‌ی کمان‌درخور دو نقطه با داشتن زاویه
==== الگوریتم‌های Point-in-Polygon ====
    * Ray Casting (تقاطع با نیم‌خط و قانون زوج‌وفرد)
    * Winding Number (محاسبه‌ی عدد چرخش با تجمیع زوایا)
==== الگوریتم‌های پوش محدب ====
    * Gift-Wrapping
    * Graham’s Scan
    * حد پایین زمان اجرا برای پوش محدب
    * مسئله‌ی دورترین دو نقطه
==== استفاده از تقسیم و حل ====
  * مسئله‌ی نزدیک‌ترین دو نقطه
==== استفاده از خط جاروب ====
    * مسئله‌ی برخورد پاره‌خط‌ها
    * مسئله‌ی برخورد دایره‌ها
    * حل مسئله‌ی Sky-Line با خط جاروب
    * مسئله‌ی اجتماع مستطیل‌ها
==== مباحث دیگر ====
  * مسئله‌های کوتاه‌ترین مسیر در فضای هندسی
  * جمع مینکوفسکی
  * داده‌ساختار DCEL
  * دیاگرام Voronoi
  * Priority Search Tree و k-d Tree
  * Fractional Cascading
  * داده‌ساختار Point-Location
  * مسئله‌های فصل ۳ از کتاب «مسئله‌های الگوریتمی»
==== تبدیل‌های هندسی دوبعدی ====
    * انتقال، تقارن و دوران
    * تبدیل دوگان
    * تبدیل Hough
    * انعکاس
==== هندسه‌ی سه‌بُعدی ====
    * محاسبه‌ی زاویه در فضای سه‌بعدی
    * بردار نرمال (عمود بر) صفحه
    * صفحه‌ی عبوری از سه نقطه
    *‌ وضعیت نقطه نسبت به صفحه
    * وضعیت نقطه نسبت به خط
    * وضعیت خط نسبت به صفحه
    *‌ وضعیت دو خط نسبت به‌هم
    *‌ وضعیت دو صفحه نسبت به‌هم
    * تصویر نقطه روی صفحه
    * تصویر نقطه روی خط
    * تصویر خط روی صفحه
    * خط مشترک دو صفحه
    * نقطه‌ی تقاطع سه صفحه
    * طول کوتاه‌ترین خم بین دو نقطه روی کره

===== جبر خطی =====
  * شناسایی بزرگ‌ترین زیرمجموعه‌ی مستقل خطی
  * محاسبه‌ی دترمینان
  * حل دستگاه خطی با روش حذف گاوسی
    * دستگاه خطی در فضای $Z_p$
  * محاسبه‌ی معکوس ماتریس
  * LP و دوگان
    * Simplex

===== پیچیدگی محاسبات =====
  * مسئله‌های تصمیم‌گیری
  * تعریف دقیق مرتبه‌ی زمان اجرا و حافظه
  * الگوریتم‌های Pseudo-Polynomial
  * مفهوم عدم قطعیت
  * کلاس‌های P و NP
  * مفهوم کاهش (Mapping-Reduction)
  * کلاس‌های C-Hard  و C-Complete
  * مسئله‌ی Circuite-Evaluation
  * مسئله‌ی SAT
  * مسئله‌ی CNF-SAT
  * مسئله‌ی 3SAT
  * مسئله‌ی Integer Programming
  * مسئله‌های معروف NP-Complete (http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)


===== مسائل بهینه‌سازی =====
  * Branch & Bound
  * DFS with Iterative Deepening
  * Hill Climbing
  * Simulated Annealing
  * مسائل USACO قسمت 4.1
  * مسئله‌ی TSP


===== الگوریتم‌های تقریبی =====
  * مسئله‌ی TSP – الگوریتم‌های تقریبی
  * مسئله‌ی پوشش رأسی – الگوریتم‌های تقریبی
  * تقریب ناپذیری

===== الگوریتم‌های تصادفی =====
  * الگوریتم‌های لاس‌وگاس و مونت‌کارلو
  * مسئله استخدام (Hiring Problem)
  * مسئله پیچ و مهره (؟؟؟)
  * درخت بازی (؟؟؟)
  * مسئله کوچک‌ترین دایره محیطی
  * برنامه‌ریزی خطی
  * Power of Two Choices