การวิเคราะห์อัลกอริทึมเชิงทดลอง
(Experimental Analysis of Algorithms)

• แนะนำตัว
• บทนำ
• FindMin
• Majority
• การวิเคราะห์อัลกอริทึม
• Build Heap
• การสร้างฮีปด้วยการค่อย ๆ "ปรับ"
• การสร้างฮีปด้วยการค่อย ๆ "เพิ่ม"
• Selection Sort
• Insertion Sort
• GCD (Euclid algorithm)
• BinarySearch
• Recurrences
• t(n) = 2t(n/2) + O(n)
• t(n) = 2t(n/2) + O(n²)
• t(n) = t(an) + t(bn) + O(n), (a+b) < 1
• t(n) = t(n/3) + O(1) กับ t(n) = t(n/2) + O(1)
• การวิเคราะห์แบบถัวเฉลี่ย
• Multi-Pop Stack
• Binary Counter
• Expandable Stack
• การแบ่งแยกและเอาชนะ
• BinarySearch
• Merge Sort
• Quick Sort (เลือกตัวซ้ายสุดเป็น pivot)
• Quick Sort (median-of-three)
• Selection (m^th smallest element): randomly-chosen pivot
• PowerMod (aⁿ mod m)
• Matrix Multiplication (simple vs. Strassen)
• Celebrity
• กำหนดการพลวัต
• Fibonacci number
• Combination: C(n,k) : n choose k
• OptimalBST (n แค่ 15, dynamic prog. เร็วขึ้นหลายหมื่นเท่า)
• Longest Increasing Subsequence
• Longest Common Subsequence
• Matrix Chain Multiplication
• Shortest Path
  • Single-Source Shortest Paths
  • All-Pair Shortest Paths
• อัลกอริทึมเชิงละโมบ
• Fractional Knapsack
• Dijkstra Algorithm (เปรียบเทียบกับ Bellman-Ford)
• Prim & Kruskal Algorithm
• Huffman Coding
• การค้นในปริภูมิสถานะ
• Permutation, Subset and Partition Enumerations
• Sorting
• Insertion Sort
• Bubble Sort
• Selection Sort
• Heap Sort
• Merge Sort
• Quick Sort (เลือกตัวซ้ายสุดเป็น pivot)
• Quick Sort (median-of-three)
• ...