算法,第二部分經典課程

Algorithms, Part II

本課程主要涵蓋了所有認真程序員所需知道的算法和數據結構要點,重點強調Java實現的應用和科學性能分析。

普林斯頓大學

Coursera

計算機

普通(中級)

33 小時

Sponsored\Ad:本課程鏈接由Coursera和Linkshare共同提供
  • 英語, 韓語
  • 2263

課程概況

第二部分涵蓋了圖處理算法,包括最小生成樹和最短路徑算法;字符串處理算法,包括字符串排序、trie、子字符串查找、正則表達式、數據壓縮。最后,課程將這些內容放到更大的語境中一覽全貌并以此作結。

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

All the features of this course are available for free. It does not offer a certificate upon completion.

你將學到什么

Graphs

Data Structure

Algorithms

Data Compression

課程大綱

周1
完成時間為 10 分鐘
Introduction
Welcome to Algorithms, Part II.
1 個視頻 (總計 9 分鐘), 2 個閱讀材料
完成時間為 2 小時

Undirected Graphs
We define an undirected graph API and consider the adjacency-matrix and adjacency-lists representations. We introduce two classic algorithms for searching a graph—depth-first search and breadth-first search. We also consider the problem of computing connected components and conclude with related problems and applications.
6 個視頻 (總計 98 分鐘), 2 個閱讀材料, 1 個測驗
完成時間為 4 小時

Directed Graphs
In this lecture we study directed graphs. We begin with depth-first search and breadth-first search in digraphs and describe applications ranging from garbage collection to web crawling. Next, we introduce a depth-first search based algorithm for computing the topological order of an acyclic digraph. Finally, we implement the Kosaraju?Sharir algorithm for computing the strong components of a digraph.
5 個視頻 (總計 68 分鐘), 1 個閱讀材料, 2 個測驗

周2
完成時間為 2 小時
Minimum Spanning Trees
In this lecture we study the minimum spanning tree problem. We begin by considering a generic greedy algorithm for the problem. Next, we consider and implement two classic algorithm for the problem—Kruskal's algorithm and Prim's algorithm. We conclude with some applications and open problems.
6 個視頻 (總計 85 分鐘), 2 個閱讀材料, 1 個測驗
完成時間為 5 小時

Shortest Paths
In this lecture we study shortest-paths problems. We begin by analyzing some basic properties of shortest paths and a generic algorithm for the problem. We introduce and analyze Dijkstra's algorithm for shortest-paths problems with nonnegative weights. Next, we consider an even faster algorithm for DAGs, which works even if the weights are negative. We conclude with the Bellman?Ford?Moore algorithm for edge-weighted digraphs with no negative cycles. We also consider applications ranging from content-aware fill to arbitrage.
5 個視頻 (總計 85 分鐘), 1 個閱讀材料, 2 個測驗

周3
完成時間為 4 小時
Maximum Flow and Minimum Cut
In this lecture we introduce the maximum flow and minimum cut problems. We begin with the Ford?Fulkerson algorithm. To analyze its correctness, we establish the maxflow?mincut theorem. Next, we consider an efficient implementation of the Ford?Fulkerson algorithm, using the shortest augmenting path rule. Finally, we consider applications, including bipartite matching and baseball elimination.
6 個視頻 (總計 72 分鐘), 2 個閱讀材料, 2 個測驗
完成時間為 2 小時

Radix Sorts
In this lecture we consider specialized sorting algorithms for strings and related objects. We begin with a subroutine to sort integers in a small range. We then consider two classic radix sorting algorithms—LSD and MSD radix sorts. Next, we consider an especially efficient variant, which is a hybrid of MSD radix sort and quicksort known as 3-way radix quicksort. We conclude with suffix sorting and related applications.
6 個視頻 (總計 85 分鐘), 1 個閱讀材料, 1 個測驗

周4
完成時間為 2 小時
Tries
In this lecture we consider specialized algorithms for symbol tables with string keys. Our goal is a data structure that is as fast as hashing and even more flexible than binary search trees. We begin with multiway tries; next we consider ternary search tries. Finally, we consider character-based operations, including prefix match and longest prefix, and related applications.
3 個視頻 (總計 75 分鐘), 2 個閱讀材料, 1 個測驗
完成時間為 5 小時

Substring Search
In this lecture we consider algorithms for searching for a substring in a piece of text. We begin with a brute-force algorithm, whose running time is quadratic in the worst case. Next, we consider the ingenious Knuth?Morris?Pratt algorithm whose running time is guaranteed to be linear in the worst case. Then, we introduce the Boyer?Moore algorithm, whose running time is sublinear on typical inputs. Finally, we consider the Rabin?Karp fingerprint algorithm, which uses hashing in a clever way to solve the substring search and related problems.
5 個視頻 (總計 75 分鐘), 1 個閱讀材料, 2 個測驗

周5
完成時間為 2 小時
Regular Expressions
A regular expression is a method for specifying a set of strings. Our topic for this lecture is the famous grep algorithm that determines whether a given text contains any substring from the set. We examine an efficient implementation that makes use of our digraph reachability implementation from Week 1.
5 個視頻 (總計 83 分鐘), 2 個閱讀材料, 1 個測驗
完成時間為 5 小時

Data Compression
We study and implement several classic data compression schemes, including run-length coding, Huffman compression, and LZW compression. We develop efficient implementations from first principles using a Java library for manipulating binary data that we developed for this purpose, based on priority queue and symbol table implementations from earlier lectures.
4 個視頻 (總計 80 分鐘), 1 個閱讀材料, 2 個測驗

周6
完成時間為 1 小時
Reductions
Our lectures this week are centered on the idea of problem-solving models like maxflow and shortest path, where a new problem can be formulated as an instance of one of those problems, and then solved with a classic and efficient algorithm. To complete the course, we describe the classic unsolved problem from theoretical computer science that is centered on the concept of algorithm efficiency and guides us in the search for efficient solutions to difficult problems.
4 個視頻 (總計 40 分鐘), 2 個閱讀材料, 1 個測驗
完成時間為 1 小時

Linear Programming (optional)
The quintessential problem-solving model is known as linear programming, and the simplex method for solving it is one of the most widely used algorithms. In this lecture, we given an overview of this central topic in operations research and describe its relationship to algorithms that we have considered.
4 個視頻 (總計 61 分鐘), 1 個閱讀材料, 1 個測驗
完成時間為 2 小時

Intractability
Is there a universal problem-solving model to which all problems that we would like to solve reduce and for which we know an efficient algorithm? You may be surprised to learn that we do no know the answer to this question. In this lecture we introduce the complexity classes P, NP, and NP-complete, pose the famous P = NP question, and consider implications in the context of algorithms that we have treated in this course.

預備知識

你需要熟悉Java編程和“算法,第一部分”中的算法和數據結構。這門課主要針對的是對工程或科學感興趣的大一大二學年本科生,以及對編程具有興趣和一定基礎的高中學生及專業人員。

參考資料

雖然這門課被設計為自給自足式的,但希望在七周課程以外擴展所學知識的同學,可以在我們編寫的教材中找到更深入廣泛的相關內容:《算法》第四版,艾迪生韋斯利出版社出版。

常見問題

本課程會講到哪些算法和數據結構?
第一部分將集中探討基礎數據結構、排序、查找。主題包括:并查算法、二分查找、棧、隊列、背包、插入排序、選擇排序、希爾排序、快速排序、三路快排、歸并排序、堆排序、二分堆、二分查找樹、紅黑樹、分離鏈接和線性探測哈希表、Graham掃描、kd樹。
第二部分將集中探討圖和字符串處理算法。主題包括:深度優先搜索、寬度優先搜索、拓撲排序、Kosaraju-Sharir算法、Kruskal算法、Prim算法、Dijkistra算法、Bellman-Ford算法、Ford-Fulkerson算法、LSD基數排序算法、MSD基數排序算法、三路基數快排算法、多路trie算法、三元查找trie算法、Knuth-Morris-Pratt算法、Boyer-Moore算法、Rabin-Karp算法、正則匹配、行程長度編碼、Huffman編碼、LZW壓縮、Burrows-Wheeler變換。

網上還有其它相關資源嗎?
有,我們的免費圖書網站包含教材概要、網絡練習、所有相關算法的Java實現(提供一鍵下載)、測試數據以及很多其它資源。

這門課同“算法設計與分析”課程有何不同?
兩門課是互補的,這門課更強調編程和代碼開發,而那門課更注重數學和證明。這門課側重于在實際應用的實現和測試中學習各種算法,而那門課側重于在解釋算法為何有效的數學建模中學習算法。在典型計算機科學課程設計中,這門課針對的是大一和大二學生,而那門課針對的是大三和大四學生。

我想選“算法,第二部分”,但我錯過了“算法,第一部分”。我該怎么做?
這就要看你的基礎了。如果你對基本數據類型和經典排序、查找算法一無所知,你最好是等到下次第一部分開課時進行學習。如果你對基礎知識比較熟悉,你也許能夠通過研讀我們的書籍和圖書網站跟上進度。

我不是計算機專業學生,這門課適合我嗎?
沒問題,這門課適用于任何希望使用計算機解決大型問題的人(因為大型問題需要高效算法)。在普林斯頓的所有學生中,有超過25%的人選過這門課,包括工程、生物、物理、化學、經濟等諸多其它專業的學生。選修這門課的遠遠不只是計算機科學專業的學生。

不熟悉Java編程的話,能選這門課嗎?
我們的核心理念是,算法在實現和測試中是最容易理解的。Java在這里只是用于說明,我們在代碼中特意避開了稀奇古怪的內容。就算你使用其它語言,這門課的代碼你也應該能輕松適應。不過,我們要求這門課的編程作業用Java提交。如果你有其它語言的編程經驗,通過我們的教材《Java編程導論:跨學科研究方法》及相關免費圖書網站來學習我們的編程模型對你應該會有幫助。

沒有任何編程基礎的話,還能選這門課嗎?
也許不行。

Magoosh
聲明:MOOC中國發布之課程均源自下列機構,版權均歸他們所有。本站僅作報道收錄并尊重其著作權益,感謝他們對MOOC事業做出的貢獻!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 網易云課堂
  • 中國大學MOOC
  • 學堂在線
  • 頂你學堂
  • 華文慕課
  • 好大學在線CnMooc
  • 以及更多...
本平臺部分課程由Coursera、Udemy及其推廣聯盟服務商Linkshare共同提供,本平臺合法享有相應的推廣收益。

© 2008-2018 MOOC.CN 慕課改變你,你改變世界

91街机捕鱼网站 足彩套利 安徽时时劫介绍 后三组六规律技巧 黑马计划网页版登录 时时彩毒胆五星 三公平台 球探足球比分手机版 北京pk赛车开奖记 pk10六码的走势技巧规律 烈火江西时时软件