資料結構與演算法

Contents

掌握演算法程式技術。通過編寫程式和解謎學習演算法，提升您的軟體工程或資料科學職業生涯。通過實施本專業化中的每個演算法挑戰來進行程式面試。將新學到的演算法技術應用於現實生活中的問題，例如分析龐大的社交網絡或對致命病原體的基因組進行測序。

關於此專業課程

計算機科學傳奇人物唐納德·高德納 (Donald Knuth) 曾說過：“除非嘗試編寫程式，否則我無法理解事物。” 我們還認為，學習演算法的最佳方式是對其進行程式編寫。然而，許多優秀的演算法書籍和在線課程，擅長介紹演算法思想，但還沒有成功地教你如何實現演算法，這是你在下一次工作面試中必須掌握的關鍵計算機科學技能。我們試圖通過組建一支多元化的講師團隊來填補這一空白，其中包括 UCSD 的世界領先的理論和應用演算法專家（Daniel Kane、Alexander Kulikov 和 Pavel Pevzner）和谷歌的前軟體工程師（Neil Rhodes）。這種獨特的技能組合使該專業不同於其他優秀的演算法 MOOC，這些課程都是由理論計算機科學家開發的。雖然這些 MOOC 側重於理論，但我們的專業化是演算法理論/實踐/應用與軟體工程的結合。您將通過使用您選擇的程式語言實施近 100 個程式設計問題來學習演算法。據我們所知，沒有任何其他演算法在線課程能夠為您提供大量的程式編寫挑戰（和難題！），您可能會在下一次工作面試中遇到這些挑戰。我們投入了 3000 多個小時來設計我們的挑戰，以替代您通常在 MOOC 中找到的多項選擇題。

到官方網站了解本課程與上課

應用的學習專案

該專業包含兩個真實世界的專案：Big Networks 和 Genome Assembly。您將分析道路網絡和社交網絡，並將學習如何計算紐約和舊金山之間的最短路徑，比您在標準演算法 101 課程中學習的最短路徑演算法快 1000 倍！之後，您將學習如何從數百萬個 DNA 短片段組裝基因組，以及組裝演算法如何推動個性化醫療的最新發展。

你將學到的內容有

在您的智慧手機上玩 50 個演算法謎題來培養您的演算法直覺！應用演算法技術（貪心演算法、二分查找、動態規劃等）和資料結構（堆棧、佇列、樹、圖等）解決高科技公司面試中經常出現的100個程式挑戰。獲得有關您的解決方案是否正確的即時反饋。
應用新學到的演算法來解決現實世界的挑戰：在大網路中導航或從其 DNA 的數百萬個短子串中組裝致命病原體的基因組。
在頂尖大學的“演算法 101”中學習與本科生完全相同的材料等等！我們很高興來自世界各地的學生現在正在他們大學的 Algorithms 101 課程中學習我們的在線資料。這是伊朗科技大學 Sauleh Eetemadi 教授網站上的一句話：“在研究了包括史丹佛大學、普林斯頓大學和麻省理工學院在內的頂尖大學的教學大綱和課程材料後，我們選擇了 UCSD 的資料結構和演算法專業，由於出色的課程材料及其實用的方法。”
如果您決定冒險超越演算法 101，請嘗試解決更複雜的程式挑戰（連網流、線性規劃、串流演算法等）並完成相當於演算法研究生課程的課程！

你將獲得的技能：

除錯	軟體測試	演算法
資料結構	電腦程式設計	動態程式設計
二元搜尋樹	優先佇列	雜湊表
堆棧(抽像資料類型)	列表

字幕

英文

製作方

University of California, San Diego

加州大學聖地亞哥分校 ( UC San Diego ) 是一個學術強國和經濟引擎，被“美國新聞與世界報導”評為十大公立大學之一。加州大學聖地亞哥分校計算機科學與工程系的教師是演算法、生物資訊學、密碼學、機器學習等計算機科學領域的領軍人物。

行業合作夥伴

第 1 門課程演算法工具箱

本課程涵蓋了在實際應用中經常出現的計算問題的基本演算法技術和想法：排序和搜索、分而治之、貪心算法、動態規劃。我們將學習很多理論：如何對資料進行排序以及如何幫助搜索; 如何將一個大問題分解並遞歸解決; 當貪婪地進行時是有道理的; 在基因組研究中如何使用動態規劃。你將練習解決計算問題、設計新的演算法，並有效地實施解決方案（以便運行時間不到一秒）

第 2 門課程資料結構

一個好的演算法通常與一組好的資料結構一起實現，使演算法能夠有效地操作資料。我們在此課程中討論在各種計算問題中常用的資料結構。你將學習如何使用不同的程式語言實現這些資料結構，並將在我們的程式設計任務中實踐它們。這將幫助你了解在資料結構的特定內建執行內部發生了什麼，以及期望從中獲得什麼。你還將學習這些資料結構的典型使用案例。

我們將在本課中討論的一些問題的例子如下：

什麼是調整動態陣列大小的好策略？
如何在 C ++、Java 和 Python中實踐先後順序的排隊？
如何實踐哈希表 ( hash table )，使所有操作的平均運行時間平均為 O(1) ？
什麼是保持二叉樹平衡 ( binary tree balanced )的好策略？

你還將學習如 Dropbox 等服務如何馬上管理上傳的一些大文件，並節省大量的儲存空間！

第 3 門課程圖的演算法

如果你曾經使用導航服務來查詢最佳路線並估計到達目的地的時間，那麼你已經使用過圖的演算法。圖的演算法在現實世界有許多應用，如道路網絡、計算機網絡和最近的社交網絡等。如果你想找出最快的上班路徑、連接一組計算機成為一個網絡最便宜的方法，或有效率地自動找出在 Facebook 的社群和意見領袖，你將需要圖的演算法。

在本課程中，你將首先了解圖是什麼，以及哪些是其最重要的屬性。然後，你將學習幾種周遊(traverse) 圖的方法，以及如何在按照某種順序周遊圖時執行有用的操作。然後，我們將討論最短路徑算法 – 從基礎算法到這些為 Google 地圖和其他導航服務使用的，比基礎快100萬倍的演算法。如果你參加“最快最短路徑產業總整專案” ( Fast Shortest Routes industrial capstone project )，將會應用到這些演算法。我們將用最小生成樹 ( spanning trees : 應用在規畫公路、電話和計算機網路的 ) 來完成並做叢集與概略演算法的應用。

第 4 門課程字串演算法

世界和網際網路充滿了文字訊息。我們使用文本查詢搜索資料，我們閱讀網站、書籍和電子郵件。從計算機科學的角度來看，這些都是字串。為了理解所有這些資訊並提高搜索效率，搜索引擎使用許多字串演算法。此外，個性化醫療的新興領域使用許多搜索演算法來發現人類基因組中的致病突變。

第 5 門課程進階的演算法和復雜性

你現在已經學習了基本演算法，並準備進入更複雜的問題並運用演算法來解決。進階的演算法建立在基本的演算法上，並使用新的想法。我們將從網路流 ( networks flows ) 開始，在比較典型的應用，例如最佳匹配、尋找不相交的路徑和航班調度，以及像電腦視覺中的圖像分割那種令人驚奇的應用。然後，我們繼續進行線性規劃、優化預算分配、組合優化、找到滿足所有要求的最便宜的飲食等等。接下來，我們討論固有的難以解決的難題，這些難題還沒有找到真正的解決方案（也不太可能被發現）以及如何實際地解決。我們最後將簡單介紹處理大數據中大量使用的串流演算法 (streaming algorithms) 。這種演算法通常被設計成能夠處理巨量的資料但不能儲存起來。

第 6 門課程基因組裝計劃的挑戰

畢業專案

2011年春季，德國成千上萬的人因為食物中毒的嚴重腹瀉引發致命的腎衰竭而住院。這是近來歷史上最致命的疫情爆發的開始，這是由一種神秘的細菌菌株引起的，我們將其稱為大腸桿菌X. 不久，德國官員將這一爆發與 Lübeck 的一家餐館聯繫起來，在這家餐館中，近 20％的顧客在一週內出現嚴重腹瀉。在這一點上，生物學家知道他們正面臨一個以前不為人知的病原體，傳統的方法是不夠的 – 生物資訊學家將需要組裝和分析新出現的病原體的基因組。

為了調查暴發變種的菌株進化起源和致病潛力，研究人員開始了眾包研究計劃。他們從一名病人身上釋放細菌 DNA 序列資料，引發了四大洲的生物資訊學家進行的一系列分析。他們甚至使用GitHub 做這專案：https：//github.com/ehec-outbreak-crowdsourced/BGI-data-analysis/wiki

2011年的德國爆發是流行病學家與計算生物學家合作制止疫情的早期例子。在此“基因組裝配計劃挑戰” ( Genome Assembly Programming Challenge) 中，你將通過開發一個程式從數百萬大腸桿菌X的基因的重疊子串中，來組裝大腸桿菌X基因組，追蹤生物資訊學家調查疫情爆發的足跡。