آموزش تقسیم و غلبه، مرتب‌سازی و جستجو، و الگوریتم‌های تصادفی - آخرین آپدیت

هفته اول Week 1

• چرا الگوریتم‌ها را مطالعه می‌کنیم؟ Why Study Algorithms?

• ضرب اعداد صحیح Integer Multiplication

• ضرب کاراتسوبا Karatsuba Multiplication

• درباره دوره About the Course

• مرتب‌سازی ادغامی: انگیزه و مثال Merge Sort: Motivation and Example

• مرتب‌سازی ادغامی: شبه‌کد Merge Sort: Pseudocode

• مرتب‌سازی ادغامی: تحلیل Merge Sort: Analysis

• اصول راهنما برای تحلیل الگوریتم‌ها Guiding Principles for Analysis of Algorithms

• خلاصه مطالب The Gist

• نماد Big Oh Big-Oh Notation

• مثال‌های پایه Basic Examples

• نمادهای Big Omega و Theta Big Omega and Theta

• مثال‌های اضافی [مرور اختیاری] Additional Examples [Review - Optional]

هفته دوم Week 2

• الگوریتم O(n log n) برای شمارش وارونگی‌ها I O(n log n) Algorithm for Counting Inversions I

• الگوریتم O(n log n) برای شمارش وارونگی‌ها II O(n log n) Algorithm for Counting Inversions II

• الگوریتم ضرب ماتریسی زیر مکعبی استراسن Strassen's Subcubic Matrix Multiplication Algorithm

• الگوریتم O(n log n) برای نزدیک‌ترین جفت I [پیشرفته و اختیاری] O(n log n) Algorithm for Closest Pair I [Advanced - Optional]

• الگوریتم O(n log n) برای نزدیک‌ترین جفت II [پیشرفته و اختیاری] O(n log n) Algorithm for Closest Pair II [Advanced - Optional]

• انگیزه و هدف Motivation

• بیان رسمی Formal Statement

• مثال‌ها Examples

• اثبات I Proof I

• تفسیر ۳ حالت Interpretation of the 3 Cases

• اثبات II Proof II

هفته سوم Week 3

• مرتب‌سازی سریع (Quicksort): بررسی اجمالی Quicksort: Overview

• افزایش (Partitioning) حول محور (Pivot) Partitioning Around a Pivot

• درستی الگوریتم Quicksort [مرور اختیاری] Correctness of Quicksort [Review - Optional]

• انتخاب یک محور مناسب Choosing a Good Pivot

• تحلیل I: اصل تجزیه Analysis I: A Decomposition Principle

• تحلیل II: بینش کلیدی Analysis II: The Key Insight

• تحلیل III: محاسبات نهایی Analysis III: Final Calculations

• مرور احتمالات I Probability Review I

• مرور احتمالات II Probability Review II

هفته چهارم Week 4

• الگوریتم انتخاب تصادفی Randomized Selection - Algorithm

• تحلیل انتخاب تصادفی Randomized Selection - Analysis

• الگوریتم انتخاب قطعی [پیشرفته و اختیاری] Deterministic Selection - Algorithm [Advanced - Optional]

• تحلیل انتخاب قطعی I [پیشرفته و اختیاری] Deterministic Selection - Analysis I [Advanced - Optional]

• تحلیل انتخاب قطعی II [پیشرفته و اختیاری] Deterministic Selection - Analysis II [Advanced - Optional]

• کران پایین Omega(n log n) برای مرتب‌سازی مبتنی بر مقایسه [پیشرفته و اختیاری] Omega(n log n) Lower Bound for Comparison-Based Sorting [Advanced - Optional]

• گراف‌ها و حداقل برش‌ها Graphs and Minimum Cuts

• نمایش‌های گراف Graph Representations

• الگوریتم انقباض تصادفی Random Contraction Algorithm

• تحلیل الگوریتم انقباض Analysis of Contraction Algorithm

• شمارش حداقل برش‌ها Counting Minimum Cuts