相關閱讀資料

演算法導論(SMA 5503)

因舊版課程無指定課堂作業與考試，因此統整所有作業、講義、考試內容合併列出。

你可以通過在Amazon.com購物來支持麻省理工開放式課程。通過與Amazon.com的夥伴關係，麻省理工學院開放式課程提供課程所需書籍與Amazon.com的直接連結。點擊書名，直接從Amazon.com購書，麻省理工學院開放式課程就會收到購買金額10%的贊助，你的支持將有助於麻省理工學院繼續將其課程開放。下表提供課程的閱讀作業，這些閱讀資料都是來自Cormen, Thomas H.、Charles E. Leiserson、Ronald L. Rivest 和Clifford Stein所著的《演算法導論》第二版，Cambridge, MA: MIT Press，ISBN: 0262032937。除了指定課程閱讀，還有一份有用的參考文獻列表。

Course readings.
課	課程單元	閱讀資料
第一課	課程細節課程介紹演算法分析、插入排序、歸併排序	1-2章
復習一	演算法正確性 Horner定則
第二課	漸進標記法遞迴置換、主方式	3-4章，不包括 4.4小節
第三課	分治法：Strassen、費氏數列、多項式乘法	28.2 和 30.1小節
復習二	遞迴、鬆散性質
第四課	快速排序、隨機演算法	5.1-5.3小節第7章
復習三	堆排序、動態集合、優先佇列	第6章
第五課	線形時間排序：下限、計數排序、根排序	8.1-8.3小節
第六課	順序統計、中位數	第9章
復習四	中位數應用桶式排序	8.4小節
第七課	散列法、哈希函數	11.1-11.3小節
第八課	一般散列，完美散列	11.5小節
復習五	測試1復習
測試1	隨堂測試1
復習六	二元搜索樹、樹的遍曆	12.1-12.3小節
第九課	二元排序樹與快速排序的關係隨機二元排序樹的分析	12.4小節
第十課	紅黑樹、反轉、插入、刪除	第13章
復習七	2-3樹、B-樹
第11課	擴充資料結構、動態順序統計、區間樹	第14章
第12課	跳過的章節	分發跳過的章節 (英PDF)
復習八	範圍樹
第13課	平攤演算法、表的倍增、潛能法	第17章
第14課	競爭分析、自組織列表	Sleator, Daniel D.和 Robert E. Tarjan. 〈列表更新和編頁規則的平攤效率〉，《ACM通訊》28, no. 2 (1985年2月): 202-208.
復習九	競爭分析：滑雪鞋租賃、隨機競爭演算法
第15課	動態規劃、最大公共子序列	第15章
第16課	貪心演算法、最小生成樹	16.1-16.3 和 22.1小節第23章
第17課	最短路徑I：屬性、Dijkstra演算法、廣度優先搜索	22.2小節第24章
第18課	最短路徑II：Bellman-Ford演算法、線形程式寫作、，差異限制
復習十	圖形搜索：深度優先搜索、拓撲排序、DAG最短路徑	22.3-22.4小節
第19課	最短路徑III：所有頂點對間最短路徑演算法、矩陣乘法、Floyd-Warshall演算法、Johnson演算法	第25章
第20課	測試2復習
第21課	道德規範，解答（強制參加）
測試二	隨堂測試2
第22課	高級論題	分發動態多線程演算法(英PDF)
第23課	高級論題（續）
復習11	高級論題
第24課	高級論題（續）	Demaine, Erik D.〈暫存遺忘演算法和資料結構〉，將要出現在《EEF暑期學校巨量資料集合講義》中，是《電腦科學講稿》的一卷。柏林，德國：Springer-Verlag.
第25課	高級論題（續）討論後續的課程
	期末考試

有用的參考文獻

Aho, Alfred V.、John E. Hopcroft和Jeffrey D. Ullman.《電腦演算法的設計與分析》The Design and Analysis of Computer Algorithms.，Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.

這是經典的書籍，但是它缺乏在網路流和線形規劃方面的內容，也沒有較近期發表的演算法。 ———.《資料結構和演算法》Data Structures and Algorithms.，Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.

本書是對《電腦演算法的設計與分析》前六章的一個修訂初級版本。 Baase, Sara.《電腦演算法：設計與分析導論》Computer Algorithms: Introduction to Design and Analysis.，第二版，Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.

一般的參考文獻，但說明有點簡略。 Bentley, Jon Louis《Pearls程式寫作》Programming Pearls.，Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.

軟體工程的演算法設計技術應用。 ———.《更多Peals程式寫作：一個編碼者的自述》More Programming Pearls: Confessions of a Coder.，Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.

更多軟體工程的演算法設計技術應用。 ———.《高效程式寫作》Writing Efficient Programs.. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.

異常注重性能 Brassard, Gilles和Paul Bratley.《演算法：理論與實作》Algorithmics: Theory and Practice.，Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.

很好的例子和問題，關注於方法而不是特定的問題。 Chu

ng, Kai Lai.《隨機過程中的基本機率理論》Elementary Probability Theory with Stochastic Processes.. New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.

對機率最直覺的介紹。 Even, Shimon.《圖形演算法》Graph Algorithms.. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.

對圖形演算法有很廣泛的介紹，包括網路流和平面圖。

Feller, William.《機率理論及應用導論》An Introduction to Probability Theory and Its Applications.，第三版， 2卷. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.

很出色的機率理論參考文獻。 Garey, Michael R.和David S. Johnson.《電腦與難解問題：NP完全理論指南》Computers and Intractibility: A Guide to the Theory of NP-Completeness.. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.

NP完全問題的參考書，第二部分包含NP完全問題擴展列表和多項式時間演算法的參考。 Gonnet, Gaston H.《演算法和資料結構手冊》Handbook of Algorithms and Data Structures.，Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X.

Pascal 和 C編碼，比較實際的運行時間，並指出研究性文章中的分析。 Gusfield, Dan.《字串、樹與序列的演算法：電腦科學和計算生物學》Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology.， Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.

對字串和序列演算法的一般介紹。 Horowitz, Ellis和Sartaj Sahni.《電腦演算法基礎》Fundamentals of Computer Algorithms.，Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226.

很好的資料結構、動態規劃和分支界限法參考資料。 Kingston, Jeffrey H.《演算法和資料結構：設計、正確性和分析》Algorithms and Data Structures: Design, Correctness, Analysis.，Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.

對資料結構進行了很好的介紹，有一章對演算法正確性進行了很好的講解。 Knuth, Donald E.《電腦程式設計的藝術》The Art of Computer Programming.，第三版， 3卷. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850.

三卷如百科全書般的作品：(1) 基礎演算法、 (2) 半數值演算法和 (3) 排序與搜索。 Lawler, Eugene L.《組合最優化：網路和擬陣》Combinatorial Optimization: Networks and Matroids.，New York,NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.

圖形演算法（密集圖形）、網路流和線形規劃，前幾章特別好。 Liu, Chung L.《組合數學導論》Introduction to Combinatorial Mathematics.，New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.

和電腦科學相關的組合數學，包含非常好的問題。 Manber, Udi.《演算法導論：創新的方法》Introduction to Algorithms: A Creative Approach.，Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.

關注創新的初級讀物。 Mehlhorn, Kurt.《資料結構和演算法》Data Structures and Algorithms.，三卷，New York,NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428.

三卷： (1) 排序和搜索、(2) 圖形演算法和NP完全問題及(3) 多維搜索和計算幾何學。對基本論題和高級論題都有所涉及。 Niven, Ivan和Herbert S. Zuckerman.《數論導論》An Introduction to the Theory of Numbers.，第四版，New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.

對數論的易讀介紹。 Papadimitriou, Christos H.和Kenneth Steiglitz.《組合最優化：演算法和複雜性》Combinatorial Optimization: Algorithms and Complexity.，Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.

線形規劃及其變種。 Press, William P.、Brian P. Flannery、Saul A. Teukolsky和William T. Vetterling.《C的數值處方：科學計算的藝術》Numerical Recipies in C: The Art of Scientific Computing.，Cambridge, UK: CambridgeUniversity Press, 1988. ISBN: 052135465X.

數值演算法的編碼。 Reingold, Edwin M.、Jurg Nievergelt和Narsingh Deo.《組合演算法：理論與實作》Combinatorial Algorithms: Theory and Practice.，Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.

對遞迴關係和二元搜索樹進行了很好的介紹。 Sedgewick, Robert.《演算法》Algorithms.，第二版，Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.

選題很廣的基礎性書籍，分析方面做得很好，但是有太多的數據。 Sipser, Michael.《計算理論導論》Introduction to the Theory of Computation，Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X.

可計算性和複雜性理論方面很好的讀物。 Tarjan, Robert Endre.《資料結構和網路演算法》Data Structures and Network Algorithms.，Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.

涵蓋優異內容的進階讀物。