MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     

6.046J / 18.410J 演算法導論(SMA 5503) (2005秋季)

6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

譯者:張曉薇

編輯:陳盈,劉契良

6.046J教材封面,《演算法導論》,第二版,Cormen、Leiserson、Rivest和Stein著。(圖片承蒙麻省理工學院出版社提供)。  

課程重點 本課程的重點在課堂講稿部分提供一套完整的講稿和視頻,在作業部分也有課程作業及答案。另外,在閱讀資料部分有該課程指定和推薦閱讀的廣泛參考書目。該課程的教材由Leiserson教授參與編寫。

 

課程描述 該課程主要講授高效演算法的設計和分析技巧,並著重實踐中有用的方法。所包含的主題有:排序演算法;查找樹、堆、散列法;分治法;動態規劃;平攤分析;圖形演算法;最短路徑;網路流;計算幾何學;數論演算法;多項式和矩陣計算;暫存以及平行計算。該課程也是新加坡-麻省理工學院聯盟(SMA)課程的一部分,課程號為SMA 5503(演算法分析和設計)。

 

技術需求 開啟本課程一些文件(.c, .java, .mp3, .rm)時,需要使用特別的軟體。    

 

教學大綱

課程目標和成果

課程目標 本課程向學生介紹電腦演算法的分析和設計,完成本課程的學習之後,學生將能夠:

分析演算法的漸近表現。

熟練掌握主要演算法和資料結構。

應用重要的演算法設計範式及分析方法。

在一般的工程設計條件下合成高效演算法。

 

課程成果 完成本課程學習的學生都應具備以下能力:

利用歸約證明和迴圈變數判斷演算法的正確性。

利用漸進分析方法來分析演算法的最差運行時間。比較由多項式、指數和對數函數組成的複合函數的漸趨行為,並分析最差、平均和最好情況的優缺點。

當演算法的運行時間符合機率分佈時,分析它的平均運行時間。利用指標隨機變數和期望值線形關係來完成分析。用這種分析法來演示演算法分析。

解釋隨機演算法的基本屬性和分析它們的方法。演示使用隨機性的演算法。解釋隨機演算法和含機率輸入演算法之間的區別。

適時利用分攤分析來分析演算法,演示運用此分析方法之簡單演算法的分析。描述分攤分析的不同策略,包括會計法和潛能法。

描述分治法並解釋何時演算法設計情況下會需要進行分治。演示使用此範例的演算法。合成分治法。導出並解決描述分治法性能的遞歸。

描述動態規劃範式並解釋什麼情況下演算法設計會需要使用它。演示使用此範式的演算法。合成並分析動態規劃法。

描述貪心範式並解釋什麼情況下演算法設計會需要使用它。演示使用此演算法。合成及分析貪心法。

解釋主要的排序演算法。演示對這些演算法的分析及它們所包含的設計策略。合成將排序做為副程式的演算法。估算比較排序法執行時間的下限並解釋怎樣克服這些界限。

解釋實現動態集合所需的主要基本資料結構及對其操作進行分析。演示使用資料結構的演算法並瞭解它們的效率是如何依賴於所使用的資料結構。用增強已有資料結構的方法來合成新資料結構。合成將資料結構作為重要成分的演算法。

解釋主要圖形演算法及其分析。適時使用圖形來對工程問題進行建模。合成新的圖形演算法和使用圖形作為關鍵部分的演算法並進行分析。

演示不同領域的幾個重要演算法,熟練掌握若干應用演算法-如:計算幾何學、運作研究、安全與加密、並行與分佈計算、作業系統,及電腦體系結構。

 

必備先修條件 需要對程式寫作有深刻的瞭解且對離散數學有很好的掌握,包括機率,這些都是該課程的必備先修條件。對於麻省理工學院的學生來說,本課程是麻省理工學院電子與電腦學院計算理論工程集中選修課的先導課程,你需要已修過6.001電腦程式結構和詮釋,以及6.042J / 18.062J電腦科學數學這兩門課,而且成績至少達到C以上。如果你不符合上述條件,在註冊該課程前務必先與助教談妥。

 

授課 每週一和週三上課,每次1.5小時。你必需確實掌握講師課上所教的課程,包括講師口述的內容。

 

復習 學生每週必須參加一次復習,每次一個小時。課程教員會安排復習的時間。你必需確實掌握復習課的內容,復習課的出勤一直以來都與考試成績有著緊密的關係。復習也提供更多提問和與教員互動的機會。復習課導師將會負責給出期末成績。復習課於每週五由助教主持。

 

講義 大多數講義都可以從伺服器下載,而且是可以列印的格式。學生應從伺服器上下載並列印講義。我們會通過伺服器或電子郵件通知學生何時在何處可以下載未上傳的講義。

 

教科書 該課程主要的教材為Cormen, Thomas H.、Charles E. Leiserson、Ronald L. Rivest和 Clifford Stein所著的《演算法導論》第二版,Cambridge, MA: MIT Press,ISBN: 0262032937。上一個學期就使用了該書第一版作為教材,但第二版對第一版的基礎上進行了大幅擴充,所以第一版已不再適合作為本課教材。這本教材可以從多間本地和網上書店買到。

 

額外幫助 每個助教會將自己每週的辦公室時間張貼在伺服器上。這學期大家將提供實驗性的作業實驗室,開放時間和地點會明列在相應的作業中。作業實驗室提供了一個地點,讓大家可以和同學一起完成作業。助教會在作業實驗室給大家提供幫助。另外,麻省理工學院電機工程與電腦科學系對很多選修大學基礎課程VI的學生提供一對一的免費服務。在學期開始的前九周,你可以申請一名輔導老師,每週會面幾小時,以幫助你更好地理解課程資料。你和輔導老師自行商量每週見面的時間,更多的資訊請參見HKN網頁。少數族群教育辦公室在輔導服務至也提供了輔導服務,這裏的輔導老師都是大學生和研究生,所有的輔導服務都會在輔導服務室或附近的教室進行。

 

註冊 請在伺服器上註冊,你所提供的資訊會幫助教員更瞭解你並創建一份郵寄清單和課程目錄。註冊是該課程的必需條件,如果沒有註冊成功,那麼通過課程會非常困難。註冊後退課請務必通知助教。旁聽的學生也需完成註冊,以便加入郵寄清單。請務必在第一節之前完成註冊。我們會在第一節課後的隔天將復習作業寄發給你。

 

作業 本學期中將會分發9次作業。教學時程表列明作業的暫時分發時間和提交期限,但是最終的提交期限都會明列在作業上。

一般而言,不能遲交作業。如有特殊情況,請提前與復習輔導老師聯繫並做預先安排。如果未預做安排,則需院長辦公室證明。

每個問題需要寫在另外一張(或多張)紙上,因為每個問題的評分老師可能不同,在每張紙的頂端都需寫下: 你的名字 復習課導老師名字 問題編號該問題的合作人(參見合作規定),如果你獨立解決了該問題,請標注「沒有合作人」。你可以手寫或列印答案,但是必須用三孔紙並提交書面版本。教員會用環夾套住紙孔防止作業丟失。這樣批改後的作業也可以放到你的活頁筆記本中。

在給出問題答案時請盡可能清晰準確,答案的可理解性和正確性同樣重要,因為技術資料的溝通是一項重要的技能。一個簡單直接的分析結果得分會比迂迴的結果更高,因為它較簡單,較不易出錯,而且更易讀易懂。潦草的答案即使正確,分數也不會太高,所以請確認你的手寫字跡清楚。建議你將問題的答案複製一份再提交,這麼做不但可以讓你的作業更工整,也能再次對作業進行完整的檢查,改正錯誤。

作業包括一些需要解決但不需要提交的練習,這可以幫助你進一步掌握課程資料,且對解決需要提交的題目助益很大。練習中涵蓋的內容將會出現在考試中。

 

演算法描述 在解決某個問題時,你經常需要提出一個演算法來解決。你應該採用短文的形式提交問題解答。主題段需要對你解決的問題和解決方法給出綜述。文章的主體應該提供:

1.      英文演算法描述,必要時可用虛擬碼

2.      至少用一個實例或圖解來詳細說明你所給出的演算法成立

3.      演算法正確性的證明(或指示)

4.      演算法運行時間的分析切記,你的目標是溝通。

評分老師可能會因為迂迴及愚鈍的描述而扣你分數。

 

評分規則 期末分數主要根據平時作業、一次隨堂測驗(Q1)、一次課外測驗(Q2)和一次期末考試來決定。平時作業 約為80分、隨堂測試約80分、課外測驗約150分,期末考試約180分。雖然平時作業在最後成績中只佔80分,但你還是得完成。下表給出沒有完成作業對最後成績的影響:

Grading criteria.
漏做作業題數 影響
0 沒有影響
1 一個等級分的1/100
2 一個等級分的1/10
3 一個等級分的1/5
4 一個等級分的1/4
5 一個等級分的1/3
6 一個等級分的1/2
7 一個等級分
8 兩個等級分
9題或以上 不及格

請注意這張表是針對遺漏的作業題數,而非作業次數。如有需要,這項評分規定會進行相應調整。

 

合作規定 平時作業的目的是為了幫助學生掌握課程資料,所以我們鼓勵學生在作業上進行合作。事實上,組成學習小組的學生往往在考試上的表現會比單獨完成作業的學生更好。如果參加學習小組,你應該對自己和小組負責,為學習會議做充份的準備。確切的說,你應該提前花至少30到45分鐘來解決每一個題目,如果你的小組不能解決問題,要和其他小組進行討論或請教復習課導老師。 你必須獨立寫下每道題目的解決方案,無論你是否和其他人合作解決該道問題。在每次作業上都要注明你的合作人。如果你獨立完成作業,也應該註明「沒有合作人」。如果你是通過搜索(如:網路)得到答案,標明來源並用自己的話來作答。如果你不能對問題的答案向教員進行口頭解釋,就算是違背本規則。 考試時,任何形式的合作都不允許。本課程的第二個測驗可以在家裏完成,你必須獨立作答,考試時間長達數天。在第20課中將會有更多關於課外測驗的合作規定。請注意該堂課是測試的一個組成部分,所以強制出席。剽竊和其他違反智慧財產的行為在任何鼓勵個人表現的學術環境中都是無法被容忍的行為,如果你對合作規定有任何疑問或者你覺得你已經違背規定,請告知教員。雖然教員負責處理學術欺騙行為,但是如果我們從學生本人那裏得知違規情況而不是校方,我們的作法相對地會較為寬容些。 該課程有很多內容,所以盡情享受吧!    

 

教學日程 以下日程表提供課程的講授(L)、復習(R)和測試(Q)課程的資訊。  

Course schedule.
課程單元 重要日期
第一課 課程細節 課程介紹 演算法分析、 插入排序、歸併排序 分發作業1
復習一 演算法正確性 Horner定則  
第二課 漸進標記法 遞迴 置換、主方式  
第三課 分治法: Strassen、費氏數列、多項式乘法  
復習二 遞迴、鬆散性質  
第四課 快速排序、隨機演算法 作業1提交 分發作業2
復習三 堆排序、動態集合、優先佇列  
第五課 線形時間排序:下限、計數排序、根排序  
第六課 順序統計、中位數  
復習四 中位數應用 桶式排序  
第七課 散列法、哈希函數 作業2提交 分發作業3
第八課 一般散列、完美散列 今晚有作業實驗室
復習五 測試1復習 作業3提交
測試1 隨堂測試1  
復習六 二元搜索樹、樹的遍歷  
第九課 二元排序樹與快速排序的關係 隨機二元排序樹的分析 分發作業4
第十課 紅黑樹、反轉、插入、刪除  
復習七 2-3樹、B-樹  
第11課 擴充資料結構、動態順序統計、區間樹 作業4提交 分發作業5
第12課 跳過的章節  
復習八 範圍樹  
第13課 平攤演算法、表的倍增、潛能法 作業5提交 分發作業6
第14課 競爭分析、自組織列表  
復習九 競爭分析:滑雪鞋租賃、隨機競爭演算法  
第15課 動態規劃、最大公共子序列 作業6提交 分發作業7
第16課 貪心演算法、最小生成樹  
第17課 最短路徑I:屬性、Dijkstra演算法、廣度優先搜索 作業7提交 分發作業8
第18課 最短路徑II:Bellman-Ford演算法、線形程式寫作、差異限制  
復習十 圖形搜索:深度優先搜索、拓撲排序、DAG最短路徑  
第19課 最短路徑III:所有頂點對間最短路徑演算法、矩陣乘法、Floyd-Warshall演算法、Johnson演算法 作業8提交  
第20課 測試2復習  
第21課 道德規範,解答(強制參加) 分發課外測驗
測試二 隨堂測試2 測驗二的兩天後提交課外測驗
第22課 高級論題 分發作業9
第23課 高級論題(續) 今晚有作業實驗室
復習11 高級論題 作業9提交
第24課 高級論題(續)  
第25課 高級論題(續) 討論後續的課程  
  期末考試  

 

相關閱讀資料 你可以通過在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.


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

 

課程講稿 本部分的一些文件(.rmmp3)需要使用特別的軟體開啟。下表除提供可下載的課堂講稿外,也提供每堂課的視頻和音頻檔。  

Lecture notes files.
課程單元 視頻授課 音頻
第一課 課程細節 課程介紹 演算法分析、 插入排序、歸併排序(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 19.5MB)
第二課 漸進標記法 (英PDF) 遞迴 置換、主方式 (英RM - 56K)
(英RM - 220K)
(英MP3 - 17.1MB)
第三課 分治法:Strassen、費氏數列、多項式乘法 (英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 16.6MB)
第四課 快速排序、隨機演算法(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 19.5MB)
第五課 線形時間排序:下限、計數排序、根排序(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.6MB)
第六課 順序統計、中位數(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 16.7MB)
第七課 散列法、哈希函數(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.9MB)
第八課 一般散列、完美散列(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 17.5MB)
第九課 二元排序樹與快速排序的關係 隨機二元排序樹的分析(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 19.7MB)
第十課 紅黑樹、反轉、插入、刪除(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.3MB)
第11課 擴充資料結構、動態順序統計、區間樹(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.3MB)
第12課 跳過的章節(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.7MB)
第13課 平攤演算法、表的倍增、潛能法(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 19.1MB)
第14課 競爭分析、自組織列表(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.0MB)
第15課 動態規劃、最大公共子序列(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 17.2MB)
第16課 貪心演算法、最小生成樹(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.3MB)
第17課 最短路徑I:屬性、Dijkstra演算法、廣度優先搜索(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.5MB)
第18課 最短路徑II:Bellman-Ford演算法、線形程式寫作、差異限制(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.7MB)
第19課 最短路徑III:所有頂點對間最短路徑演算法、矩陣乘法、 Floyd-Warshall演算法、Johnson演算法(英PDF) (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.2MB)
第20課 測試2復習(英PDF)    
第21課 道德規範,解答(強制參加) (英PDF)    
第22課 高級論題 (英RM - 56K)
(英RM - 220K)
(英MP3 - 18.2MB)
第23課 高級論題(續) (英RM - 56K)
(vRM - 220K)
(英MP3 - 17.6MB)
第24課 高級論題(續) (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.5MB)
第25課 高級論題(續) 討論後續的課程 (英RM - 56K)
(英RM - 220K)
(英MP3 - 20.6MB)

     

作業 本部分的一些文件(.c.java)需要使用特別的軟體才能打開。這部分包含一些不能用螢幕閱讀軟體存取的文檔,「#」符號將用來標注這些文檔。課程作業既包括練作業也包括需要解決的問題。學生只需要提交待解決問題的答案,但我鼓勵同學們試算練作業以掌握課程內容。很多練作業都是來自於教材。

Assignment files.
作業 解答
作業1 (英PDF)# (英PDF)#
作業2 (英PDF) (英PDF)
作業3 (英PDF) (英PDF)
作業4 (英PDF) (英PDF)
作業5 (英PDF) (英PDF)#
作業6 (英PDF) (英PDF)#
作業7 (英PDF)

輸入範例,  sample.txt (TXT)
輸出範例,samplesol.txt (TXT)
輸入1,input1.txt (TXT)
輸入2,input2.txt (TXT)
輸入3,input3.txt (TXT)
(英PDF)

源代碼 editDistance.java (JAVA)
源代碼 editDistance.c (C)
作業8 (英PDF) (英PDF)
作業9 (英PDF) (英PDF)

   

 

測驗 該部分包含一些不能用螢幕閱讀軟體存取的文檔。“#”符號用來標注這些文檔。 這部分提供課程的實際測驗和模擬測驗。  

Exam files.
測驗 解答
模擬測驗 1 (英PDF) (英PDF)#
模擬測驗2 (英PDF)  
模擬期末考試(英PDF) (英PDF)
測驗 1 (PDF) (英PDF)
測驗 2 (PDF) (英PDF)
期末考試 (英PDF) (英PDF)
   

以下為系統擷取之英文原文

6.046J / 18.410J Introduction to Algorithms (SMA 5503)

Fall 2005

Cover of textbook, Introduction to Algorithms.

Cover of 6.046J textbook, Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein. (Image courtesy of MIT Press.)

Course Highlights

This course features a complete set of lecture notes and videos. Homework assignments with solutions are also available in the assignments section. In addition, an extensive bibliography of assigned and recommended readings is provided in the readings section. The course textbook was co-written by Prof. Leiserson.

Previous versions of this course are also available: Fall 2004Fall 2001.



Course Description

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).



Special Features

Video lectures Audio lectures Subtitles/Transcript

Technical Requirements

Special software is required to use some of the files in this course: .c, .java.





Syllabus

Course Objectives and Outcomes

Course Objectives

This course introduces students to the analysis and design of computer algorithms. Upon completion of this course, students will be able to do the following:

Analyze the asymptotic performance of algorithms.

Demonstrate a familiarity with major algorithms and data structures.

Apply important algorithmic design paradigms and methods of analysis.

Synthesize efficient algorithms in common engineering design situations.

Course Outcomes

Students who complete the course will have demonstrated the ability to do the following:

Argue the correctness of algorithms using inductive proofs and loop invariants.

Analyze worst-case running times of algorithms using asymptotic analysis. Compare the asymptotic behaviors of functions obtained by elementary composition of polynomials, exponentials, and logarithmic functions. Describe the relative merits of worst-, average-, and best-case analysis.

Analyze average-case running times of algorithms whose running time is probabilistic. Employ indicator random variables and linearity of expectation to perform the analyses. Recite analyses of algorithms that employ this method of analysis.

Explain the basic properties of randomized algorithms and methods for analyzing them. Recite algorithms that employ randomization. Explain the difference between a randomized algorithm and an algorithm with probabilistic inputs.

Analyze algorithms using amortized analysis, when appropriate. Recite analyses of simple algorithms that employ this method of analysis. Describe different strategies for amortized analysis, including the accounting method and the potential method.

Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.

Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms, and analyze them.

Describe the greedy paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize greedy algorithms, and analyze them.

Explain the major algorithms for sorting. Recite the analyses of these algorithms and the design strategies that the algorithms embody. Synthesize algorithms that employ sorting as a subprocedure. Derive lower bounds on the running time of comparison-sorting algorithms, and explain how these bounds can be overcome.

Explain the major elementary data structures for implementing dynamic sets and the analyses of operations performed on them. Recite algorithms that employ data structures and how their performance depends on the choice of data structure. Synthesize new data structures by augmenting existing data structures. Synthesize algorithms that employ data structures as key components.

Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate. Synthesize new graph algorithms and algorithms that employ graph computations as key components, and analyze them.

Demonstrate a familiarity with applied algorithmic settings - such as computational geometry, operations research, security and cryptography, parallel and distributed computing, operating systems, and computer architecture - by reciting several algorithms of importance to different fields.



Prerequisites

A strong understanding of programming and a solid background in discrete mathematics, including probability, are necessary prerequisites to this course.

For MIT Students, this course is the header course for the MIT/EECS Engineering Concentration of Theory of Computation. You are expected to have taken 6.001 Structure and Interpretation of Computer Programs and 6.042J / 18.062J Mathematics for Computer Science, and received a grade of C or higher in both classes. If you do not meet these requirements, you must talk to a TA before registering for the course.



Lectures

Lectures will be held twice a week on Mondays and Wednesdays for 1.5 hours. You are responsible for material presented in lectures, including oral comments made by the lecturer.



Recitations

Students must attend a one-hour recitation session each week. The course staff will schedule recitations. You are responsible for material presented in recitation. Attendance in recitation has been well correlated in the past with exam performance. Recitations also give you a more intimate opportunity to ask questions and interact with the course staff. Your recitation instructor will assign your final grade. Recitations will be taught by the teaching assistants on Fridays.



Handouts

Most handouts will be made available on the server in formats suitable for printing. Students should download and print out the handouts from the server. You will be informed via the server and/or email where and when the few handouts that are not available from the server can be obtained.



Text

The primary written reference for the course: Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937. In previous semesters the course has used the first edition of this text. The second edition is a substantial revision of the first, making the first edition unsuitable as a substitute.

The textbook can be obtained at various local and online bookstores.



Extra Help

Each Teaching Assistant will post his or her weekly office hours on the server. As an experiment, we will offer homework labs during the term. The time and location will be on the specific problem set. A homework lab is a place where you can go to do your homework with others in the class. Teaching Assistants will be available at the homework lab to help if you have questions about the problem set.

In addition, as a free service to its students, the MIT Department of Electrical Engineering and Computer Science provides one-on-one peer assistance in many basic undergraduate Course VI classes. During the first nine weeks of the term, you may request a tutor who will meet with you for a few hours a week to aid in your understanding of course material. You and your tutor arrange the hours that you meet, for your mutual convenience. More information is available on the HKN Web page.

Tutoring is also available from the Tutorial Services Room (TSR) sponsored by the Office of Minority Education. The tutors are undergraduate and graduate students, and all tutoring sessions take place in the TSR or the nearby classrooms.



Registration

Please fill out a sign-up sheet on the course server. The information you provide will help the course staff to get to know you better and create a mailing list and a course directory. Signing up is a requirement of the course. You will find it difficult to pass the course if you aren't in the class! You should notify your TA immediately if you drop the course after having registered. Listeners should also register for the course in order to be on the mailing list.

You must register before Ses #1. We will email your recitation assignment to you one day after Ses #1.



Problem Sets

Nine problem sets will be assigned during the semester. The course calendar shows the tentative schedule of assignments and due dates, but the actual due date will always be on the problem set itself.

Late homework will generally not be accepted. If there are extenuating circumstances, you should make prior arrangements with your recitation instructor. An excuse from the Dean's Office will be required if prior arrangements have not been made. Each problem should be written up on a separate sheet (or sheets) of paper, since problems may be graded by separate graders. Mark the top of each sheet with the following: your name, the name of your recitation instructor, the problem number, the people you worked with on the problem (see Collaboration Policy), or "Collaborators: none" if you solved the problem completely alone.
You may handwrite or type your answers. You must submit your answers on three-hole punch paper and hand in a physical copy. The course staff puts rings through the holes to avoid losing homework. In addition, your graded homework can easily be included in your loose-leaf course notebook. You should be as clear and precise as possible in your write-up of solutions. Understandability of your answer is as desirable as correctness, because communication of technical material is an important skill.
A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Sloppy answers will receive fewer points, even if they are correct, so make sure that your handwriting is legible. It is a good idea to copy over your solutions to hand in, which will make your work neater and give you a chance to do sanity checks and correct bugs. The problem sets include exercises that should be solved but not handed in. These questions are intended to help you master the course material and will be useful in solving the assigned problems. Material covered in exercises will be tested on exams.



Describing Algorithms

You will often be called upon to "give an algorithm" to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:

A description of the algorithm in English and, if helpful, pseudocode.

At least one worked example or diagram to show more precisely how your algorithm works.

A proof (or indication) of the correctness of the algorithm.

An analysis of the running time of the algorithm.

Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.



Grading Policy

The final grade will be primarily based on problem sets, one in-class quiz (Q1), one take-home quiz (Q2), and a final. The problem sets will together be worth about 80 points, the in-class quiz about 80 points, the take-home quiz about 150 points, and the final exam about 180 points.

Although the problem sets account for only 80 points in your final grade, you must do them. The following table shows the impact of failing to do problems:


Grading criteria. PROBLEMS SKIPPED IMPACT
0 None
1 One-hundredth of a Letter Grade
2 One-tenth of a Letter Grade
3 One-fifth of a Letter Grade
4 One-fourth of a Letter Grade
5 One-third of a Letter Grade
6 One-half of a Letter Grade
7 One Letter Grade
8 Two Letter Grades
9 or more Fail



Please observe that this table is for problems skipped, not problem sets. The specifics of this grading policy are subject to change if the need arises.



Collaboration Policy

The goal of homework is to give you practice in mastering the course material. Consequently, you are encouraged to collaborate on problem sets. In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study group meeting. Specifically, you should spend at least 30-45 minutes trying to solve each problem beforehand. If your group is unable to solve a problem, talk to other groups or ask your recitation instructor.

You must write up each problem solution by yourself without assistance, however, even if you collaborate with others to solve the problem. You are asked on problem sets to identify your collaborators. If you did not work with anyone, you should write "Collaborators: none." If you obtain a solution through research (e.g., on the Web), acknowledge your source, but write up the solution in your own words. It is a violation of this policy to submit a problem solution that you cannot orally explain to a member of the course staff.

No collaboration whatsoever is permitted on exams. The course has a take-home exam for the second quiz which you must do entirely on your own, even though you will be permitted several days in which to do the exam. More details about the collaboration policy for the take-home exam will be forthcoming in lecture 20. Please note that this lecture constitutes part of the exam, and attendance is mandatory.

Plagiarism and other anti-intellectual behavior cannot be tolerated in any academic environment that prides itself on individual accomplishment. If you have any questions about the collaboration policy, or if you feel that you may have violated the policy, please talk to one of the course staff. Although the course staff is obligated to deal with cheating appropriately, we are more understanding and lenient if we find out from the transgressor himself or herself rather than from a third party.

This course has great material, so have fun!





Calendar

The calendar below provides information on the course's lecture (L), recitation (R), and quiz (Q) sessions.


Course schedule. SES # TOPICS KEY DATES
L1 Administrivia

Introduction

Analysis of Algorithms, Insertion Sort, Mergesort
Problem set 1 out
R1 Correctness of Algorithms

Horner's rule
 
L2 Asymptotic Notation

Recurrences

Substitution, Master Method
 
L3 Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication  
R2 Recurrences, Sloppiness  
L4 Quicksort, Randomized Algorithms Problem set 1 due

Problem set 2 out
R3 Heapsort, Dynamic Sets, Priority Queues  
L5 Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort  
L6 Order Statistics, Median  
R4 Applications of Median

Bucketsort
 
L7 Hashing, Hash Functions Problem set 2 due

Problem set 3 out
L8 Universal Hashing, Perfect Hashing Homework lab tonight
R5 Quiz 1 Review Problem set 3 due
Q1 Quiz 1, In-class  
R6 Binary Search Trees, Tree Walks  
L9 Relation of BSTs to Quicksort

Analysis of Random BST
Problem set 4 out
L10 Red-black Trees, Rotations, Insertions, Deletions  
R7 2-3 Trees, B-trees  
L11 Augmenting Data Structures, Dynamic Order Statistics, Interval Trees Problem set 4 due

Problem set 5 out
L12 Skip Lists  
R8 Range Trees  
L13 Amortized Algorithms, Table Doubling, Potential Method Problem set 5 due

Problem set 6 out
L14 Competitive Analysis: Self-organizing Lists  
R9 Competitive Analysis: Ski Rental, Randomized Competitive Algorithm  
L15 Dynamic Programming, Longest Common Subsequence Problem set 6 due

Problem set 7 out
L16 Greedy Algorithms, Minimum Spanning Trees  
L17 Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search Problem set 7 due

Problem set 8 out
L18 Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints  
R10 Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths  
L19 Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson Problem set 8 due
L20 Quiz 2 Review  
L21 Ethics, Problem Solving (Mandatory Attendance) Take-home quiz 2 handed out
Q2 Quiz 2, In-class Take-home quiz 2 due two days after Ses #Q2
L22 Advanced Topics Problem set 9 out
L23 Advanced Topics (cont.) Homework lab tonight
R11 Advanced Topics Problem set 9 due
L24 Advanced Topics (cont.)  
L25 Advanced Topics (cont.)

Discussion of Follow-on Classes
 
  Final Exam  




Readings

Amazon logo Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses.

The table below provides information on the course's reading assignments, which are taken from the course textbook: Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937. In addition to the assigned course readings, see the list of useful references for the course below.


Course readings. SES # TOPICS READINGS
L1 Administrivia

Introduction

Analysis of Algorithms, Insertion Sort, Mergesort
Chapters 1-2
R1 Correctness of Algorithms

Horner's rule
 
L2 Asymptotic Notation

Recurrences

Substitution, Master Method
Chapters 3-4, excluding section 4.4
L3 Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication Sections 28.2 and 30.1
R2 Recurrences, Sloppiness  
L4 Quicksort, Randomized Algorithms Sections 5.1-5.3

Chapter 7
R3 Heapsort, Dynamic Sets, Priority Queues Chapter 6
L5 Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort Sections 8.1-8.3
L6 Order Statistics, Median Chapter 9
R4 Applications of Median

Bucketsort
Section 8.4
L7 Hashing, Hash Functions Sections 11.1-11.3
L8 Universal Hashing, Perfect Hashing Section 11.5
R5 Quiz 1 Review  
Q1 Quiz 1, In-class  
R6 Binary Search Trees, Tree Walks Sections 12.1-12.3
L9 Relation of BSTs to Quicksort

Analysis of Random BST
Section 12.4
L10 Red-black Trees, Rotations, Insertions, Deletions Chapter 13
R7 2-3 Trees, B-trees  
L11 Augmenting Data Structures, Dynamic Order Statistics, Interval Trees Chapter 14
L12 Skip Lists Skip Lists handout (PDF)
R8 Range Trees  
L13 Amortized Algorithms, Table Doubling, Potential Method Chapter 17
L14 Competitive Analysis: Self-organizing Lists Sleator, Daniel D., and Robert E. Tarjan. "Amortized efficiency of list update and paging rules." Communications of the ACM 28, no. 2 (February 1985): 202-208.
R9 Competitive Analysis: Ski Rental, Randomized Competitive Algorithm  
L15 Dynamic Programming, Longest Common Subsequence Chapter 15
L16 Greedy Algorithms, Minimum Spanning Trees Sections 16.1-16.3 and 22.1

Chapter 23
L17 Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search Section 22.2

Chapter 24
L18 Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints  
R10 Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths Sections 22.3-22.4
L19 Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson Chapter 25
L20 Quiz 2 Review  
L21 Ethics, Problem Solving (Mandatory Attendance)  
Q2 Quiz 2, In-class  
L22 Advanced Topics Dynamic Multithreaded Algorithms handout (PDF)
L23 Advanced Topics (cont.)  
R11 Advanced Topics  
L24 Advanced Topics (cont.) Demaine, Erik D. "Cache-Oblivious Algorithms and Data Structures." To appear in Lecture Notes from the EEF Summer School on Massive Data Sets, a volume of Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag.
L25 Advanced Topics (cont.)

Discussion of Follow-on Classes
 
  Final Exam  





Useful References

Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.

———. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.

Baase, Sara. Computer Algorithms: Introduction to Design and Analysis. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.
General reference, although the exposition is sometimes terse or sketchy.

Bentley, Jon Louis. Programming Pearls. Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.
Applications of algorithm design techniques to software engineering.

———. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.
More applications of algorithm design techniques to software engineering.

———. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.
Performance hacking extraordinaire.

Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.

Chung, Kai Lai. Elementary Probability Theory with Stochastic Processes. New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.
Intuitive introduction to probability.

Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.

Feller, William. An Introduction to Probability Theory and Its Applications. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.
Excellent reference for probability theory.

Garey, Michael R., and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.
Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.

Gonnet, Gaston H. Handbook of Algorithms and Data Structures. Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X.
Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.

Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
General treatment of algorithms that operate on character strings and sequences.

Horowitz, Ellis, and Sartaj Sahni. Fundamentals of Computer Algorithms. Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226.
Good on data structures, dynamic programming, and branch-and-bound algorithms.

Kingston, Jeffrey H. Algorithms and Data Structures: Design, Correctness, Analysis. Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.
A nice introductory book on data structures, with a good chapter on algorithm correctness.

Knuth, Donald E. The Art of Computer Programming. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850.
Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.

Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.
Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.

Liu, Chung L. Introduction to Combinatorial Mathematics. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.
Combinatorial mathematics relevant to computer science. Excellent problems.

Manber, Udi. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.
Elementary text with an emphasis on creativity.

Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428.
Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.

Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.
Readable introduction to number theory.

Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.
Linear programming and its variants.

Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipies in C: The Art of Scientific Computing. Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X.
Code for numerical algorithms.

Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.
Good on recurrence relations and binary search trees.

Sedgewick, Robert. Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.
Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.

Sipser, Michael. Introduction to the Theory of Computation. Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X.
A good text on computability and complexity theory.

Tarjan, Robert Endre. Data Structures and Network Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.
Advanced book with tons of good stuff.





Assignments

Special software is required to use some of the files in this section: .c, .java. This section contains documents that could not be made accessible to screen reader software. A "#" symbol is used to denote such documents.

The problem sets for the course included both exercises and problems that students were asked to solve. Students were required to turn in only the problems but were encouraged to solve the exercises to help master the course material. Many of the exercise questions were taken from the course textbook.


Assignment files. ASSIGNMENTS SOLUTIONS
Problem Set 1 (PDF)# (PDF)#
Problem Set 2 (PDF) (PDF)
Problem Set 3 (PDF) (PDF)
Problem Set 4 (PDF) (PDF)
Problem Set 5 (PDF) (PDF)#
Problem Set 6 (PDF) (PDF)#
Problem Set 7 (PDF)

Sample Input, sample.txt (TXT)
Sample Output, samplesol.txt (TXT)
Input 1, input1.txt (TXT)
Input 2, input2.txt (TXT)
Input 3, input3.txt (TXT)
(PDF)

Source Code, editDistance.java (JAVA)
Source Code, editDistance.c (C)
Problem Set 8 (PDF) (PDF)
Problem Set 9 (PDF) (PDF)




Exams

This section contains documents that could not be made accessible to screen reader software. A "#" symbol is used to denote such documents.

This section provides actual and practice quizzes for the course.


Exam files. EXAMS SOLUTIONS
Practice Quiz 1 (PDF) (PDF)#
Practice Quiz 2 (PDF)  
Practice Final Exam (PDF) (PDF)
Quiz 1 (PDF) (PDF)
Quiz 2 (PDF) (PDF)
Final Exam (PDF) (PDF)




Video Lectures

Audio/video for lectures 20 and 21 are not available.


Lecture notes files. SES # TOPICS
1 Administrivia - Introduction - Analysis of Algorithms, Insertion Sort, Mergesort
2 Asymptotic Notation - Recurrences - Substitution, Master Method
3 Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication
4 Quicksort, Randomized Algorithms
5 Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
6 Order Statistics, Median
7 Hashing, Hash Functions
8 Universal Hashing, Perfect Hashing
9 Relation of BSTs to Quicksort - Analysis of Random BST
10 Red-black Trees, Rotations, Insertions, Deletions
11 Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
12 Skip Lists
13 Amortized Algorithms, Table Doubling, Potential Method
14 Competitive Analysis: Self-organizing Lists
15 Dynamic Programming, Longest Common Subsequence
16 Greedy Algorithms, Minimum Spanning Trees
17 Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
18 Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
19 Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson
20 Quiz 2 Review
Note: No audio or video is available for this session.
21 Ethics, Problem Solving (Mandatory Attendance)
Note: No audio or video is available for this session.
22 Advanced Topics
23 Advanced Topics (cont.)
24 Advanced Topics (cont.)
25 Advanced Topics (cont.) - Discussion of Follow-on Classes



留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入3 + 5 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

課程討論
過了四年還是.. not found

Anonymous, 2016-12-21 23:30:07
課程討論
過了三年還是.. not found
Anonymous, 2015-03-29 15:46:28
課程討論
課程連結遺失
Anonymous, 2014-04-26 19:06:19
課程討論
過了兩年還是.. not found
Anonymous, 2014-03-16 14:33:31
課程討論
Still Not Found.
yosh, 2012-02-27 23:05:01
課程討論
目前連結Not found,希望有工作人員注意到,謝謝。
linpershey, 2011-10-01 21:46:52
課程討論
什麼東西也沒有阿.... 連結全都不能連阿...
leocl6, 2011-02-03 02:04:45
课程讨论
没资源啊,都翻译什么了?
andy_gaga, 2010-12-27 13:53:00
課程討論
我覺得您blog很出色呢~  純粹真心推建給您: 如果 您在追求 夢寐以求的 財 富 ,  那你一定要了解這個機會, 一個 名人都敢背書的 創 業 機 會! -> http://azyyeayzz.weebly.com/
workonet, 2010-09-30 13:35:03

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: