(clrs)：introduction To Algorithms——instructor’s Manual@2002 (第2版)

這份資料是一份針對《演算法導論 第二版》（Introduction to Algorithms, Second Edition，由 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 合著）所編寫的講師手冊（Instructor’s Manual）。其主要論點與用途可歸納為以下幾個面向：

  1. 核心目的與定位： 本手冊的核心宗旨是作為《演算法導論 第二版》教科書的配套資源，旨在協助講師進行演算法課程的教學。它提供了一系列與教科書章節對應的補充材料，以支援講師準備課程內容及習題解答。

  2. 內容組織架構： 手冊的內容結構是按照教科書的章節進行組織。對於教科書中的大部分章節，手冊提供了相應的「授課筆記」（Lecture Notes）和「習題解答」（Solutions）。這種按章節劃分的編排方式，賦予了講師高度的彈性，可以根據自己的課程安排和教學重點來選擇和使用手冊中的材料。值得注意的是，手冊並非涵蓋教科書中的所有章節，而是選擇了與演算法核心課程更為相關的部分進行詳盡闡述。例如，基礎性或較為進階、非核心的章節（如第一章、第十章、第十八章至二十章等）並未包含在內，這也體現了手冊旨在聚焦於主流演算法課程的需求。

  3. 授課筆記的特性與來源： 手冊中的授課筆記部分旨在提供一個更為口語化、非正式的教學呈現風格，以貼合課堂講授的實際需求。這些筆記來源多元，部分沿用了第一版講師手冊的材料（基於 Charles Leiserson 在 MIT 的課程），部分來自 Thomas H. Cormen 在 Dartmouth College 的課程筆記，也有部分是專門為第二版手冊新編寫的內容。筆記在表達上相對教科書更為簡潔，有時會簡化或省略某些細節，以提高課堂效率。其中提到的偽程式碼（pseudocode）也採用了與教科書略有差異的習慣，例如行不編號、陣列長度作為參數而非屬性，這些調整是為了更方便在黑板或白板上書寫演示。

  4. 習題解答的編寫風格與範圍： 手冊為選定的章節提供了習題（Exercise）和問題（Problem）的解答。解答的編寫風格比授課筆記正式，但比教科書略為非正式。偽程式碼部分為了與教科書保持一致，仍使用了陣列長度屬性，但同樣不編號。手冊並未提供所有習題和問題的解答，這既是出於及時發布手冊的考量，也是為了避免手冊過於龐大。索引部分列出了手冊中包含解答的所有習題和問題，方便講師查閱。解答中也偶爾包含給講師的提示（asides）。

  5. 涵蓋的核心演算法主題： 儘管手冊不包含所有章節，但從其目錄和提供的部分內容可以看出，它涵蓋了演算法領域的許多核心主題。這包括：

    • 基礎概念與分析： 演算法入門、函數成長的分析（漸近記號 O、Ω、Θ 等）、遞迴式的求解方法（替換法、遞迴樹、主方法）。
    • 排序演算法： 插入排序、合併排序、堆積排序、快速排序等比較排序演算法的分析與實現，以及線性時間排序演算法（計數排序、基數排序、桶排序）的原理。
    • 基本資料結構： 堆積（heap）、二元搜尋樹、紅黑樹（一種平衡二元搜尋樹）、雜湊表、不相交集合資料結構等。
    • 演算法設計技術： 分而治之（例如合併排序、快速排序）、動態規劃（例如裝配線排程、最長共同子序列、最佳二元搜尋樹）、貪婪演算法（例如活動選擇、背包問題的對比）。
    • 進階分析技術： 機率分析與隨機演算法（例如雇用問題、隨機排列）、攤銷分析（Aggregate、Accounting、Potential 方法）。
    • 圖形演算法： 基本圖形演算法（廣度優先搜尋 BFS、深度優先搜尋 DFS、拓撲排序、強連通分量）、最小生成樹（Kruskal 演算法、Prim 演算法）、單源最短路徑（Bellman-Ford 演算法、Dijkstra 演算法、差分約束）、所有頂點對最短路徑（矩陣乘法方法、Floyd-Warshall 演算法、Johnson 演算法）。
    • 專題： 擴充資料結構（在紅黑樹基礎上增加屬性以支援新操作，如順序統計樹、區間樹）、網路流（最大流、最小割、Ford-Fulkerson 方法、Edmonds-Karp 演算法、最大二分匹配）、排序網路。

  6. 強調的分析與證明方法： 手冊在講解演算法的同時，也貫徹了教科書中對分析和正確性的重視。授課筆記和解答中經常運用環狀不變數（loop invariant）來論證演算法的正確性，並詳細分析演算法的時間複雜度，包括最壞情況、平均情況（在隨機演算法或機率分析中）以及攤銷分析。遞迴式的求解方法作為分析遞迴演算法（如分而治之）效能的關鍵工具，也得到了專門的闡述。

總而言之，這份講師手冊不僅僅是教科書習題的解答集，更是一個結構化的教學輔助資源，為講師提供了經過編排和分析的課程筆記以及精選的習題範例。它旨在幫助講師有效率地準備和講授《演算法導論》課程的核心內容，特別是複雜演算法的分析和設計。