|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/algorithms-part1
课程评论：没有评论
课程名称：算法（第一部分） 课程概述： 本课程涵盖了每位严肃程序员需要掌握的算法和数据结构的基本信息，重点强调Java实现的应用及科学性能分析。第一部分主要涉及基本数据结构、排序和搜索算法；第二部分则专注于图形和字符串处理算法。该课程的所有功能均免费提供，但完成后不提供证书。 课程大纲： 1. 课程介绍：欢迎参加算法（第一部分）。 2. 联合-查找：通过考虑动态连通性问题，介绍基本算法开发与分析方法，讨论不同的联合-查找数据类型实现，并将其应用于物理化学中的渗流问题。 3. 算法分析：基于科学方法分析算法性能，进行计算实验以测量程序运行时间，建立假设并创建数学模型解释行为，同时分析程序的内存使用。 4. 栈与队列：探讨存储对象集合的基本数据类型，通过单链表或动态数组实现，介绍泛型和迭代器等高级Java特性，并讨论其在不同应用中的使用。 5. 初级排序：介绍排序问题和Java的Comparable接口，学习选择排序和插入排序两种基本排序方法，以及与之相关的Graham扫描算法应用。 6. 归并排序：深入研究归并排序算法，其比较次数不超过n lg n，并讨论非递归的自下而上的实现。 7. 快速排序：介绍随机化快速排序算法及其性能分析，讨论快速选择和三路快速排序的变体。 8. 优先队列：介绍优先队列数据类型及其高效实现，并讨论应用于粒子运动的仿真。 9. 初级符号表：定义符号表的API，描述基于排序数组和无序列表的两种基本实现，并分析二叉搜索树的性能。 10. 平衡搜索树：开发具有保证对数性能的符号表，探讨2-3树及红黑树的实现和分析。 11. 平衡搜索树的几何应用：讨论一维和二维范围查询，考虑kd树及其在交集问题中的应用。 12. 哈希表：描述哈希函数的特性及其Java实现，讨论两种哈希表的构建策略。 13. 符号表应用：考虑符号表在集合、字典客户端、索引客户端和稀疏向量等方面的应用。 本课程结构全面，为学习和掌握算法与数据结构打下坚实基础。
Name:Course Introduction
Description:Welcome to Algorithms, Part I.
Name:Union−Find
Description:We illustrate our basic approach to developing and analyzing algorithms by considering the dynamic connectivity problem. We introduce the union−find data type and consider several implementations (quick find, quick union, weighted quick union, and weighted quick union with path compression). Finally, we apply the union−find data type to the percolation problem from physical chemistry.
Name:Analysis of Algorithms
Description:The basis of our approach for analyzing the performance of algorithms is the scientific method. We begin by performing computational experiments to measure the running times of our programs. We use these measurements to develop hypotheses about performance. Next, we create mathematical models to explain their behavior. Finally, we consider analyzing the memory usage of our Java programs.
Name:Stacks and Queues
Description:We consider two fundamental data types for storing collections of objects: the stack and the queue. We implement each using either a singly-linked list or a resizing array. We introduce two advanced Java features—generics and iterators—that simplify client code. Finally, we consider various applications of stacks and queues ranging from parsing arithmetic expressions to simulating queueing systems.
Name:Elementary Sorts
Description:We introduce the sorting problem and Java's Comparable interface. We study two elementary sorting methods (selection sort and insertion sort) and a variation of one of them (shellsort). We also consider two algorithms for uniformly shuffling an array. We conclude with an application of sorting to computing the convex hull via the Graham scan algorithm.
Name:Mergesort
Description:We study the mergesort algorithm and show that it guarantees to sort any array of n items with at most n lg n compares. We also consider a nonrecursive, bottom-up version. We prove that any compare-based sorting algorithm must make at least n lg n compares in the worst case. We discuss using different orderings for the objects that we are sorting and the related concept of stability.
Name:Quicksort
Description:We introduce and implement the randomized quicksort algorithm and analyze its performance. We also consider randomized quickselect, a quicksort variant which finds the kth smallest item in linear time. Finally, we consider 3-way quicksort, a variant of quicksort that works especially well in the presence of duplicate keys.
Name:Priority Queues
Description:We introduce the priority queue data type and an efficient implementation using the binary heap data structure. This implementation also leads to an efficient sorting algorithm known as heapsort. We conclude with an applications of priority queues where we simulate the motion of n particles subject to the laws of elastic collision.
Name:Elementary Symbol Tables
Description:We define an API for symbol tables (also known as associative arrays, maps, or dictionaries) and describe two elementary implementations using a sorted array (binary search) and an unordered list (sequential search). When the keys are Comparable, we define an extended API that includes the additional methods min, max floor, ceiling, rank, and select. To develop an efficient implementation of this API, we study the binary search tree data structure and analyze its performance.
Name:Balanced Search Trees
Description:In this lecture, our goal is to develop a symbol table with guaranteed logarithmic performance for search and insert (and many other operations). We begin with 2−3 trees, which are easy to analyze but hard to implement. Next, we consider red−black binary search trees, which we view as a novel way to implement 2−3 trees as binary search trees. Finally, we introduce B-trees, a generalization of 2−3 trees that are widely used to implement file systems.
Name:Geometric Applications of BSTs
Description:We start with 1d and 2d range searching, where the goal is to find all points in a given 1d or 2d interval. To accomplish this, we consider kd-trees, a natural generalization of BSTs when the keys are points in the plane (or higher dimensions). We also consider intersection problems, where the goal is to find all intersections among a set of line segments or rectangles.
Name:Hash Tables
Description:We begin by describing the desirable properties of hash function and how to implement them in Java, including a fundamental tenet known as the uniform hashing assumption that underlies the potential success of a hashing application. Then, we consider two strategies for implementing hash tables—separate chaining and linear probing. Both strategies yield constant-time performance for search and insert under the uniform hashing assumption.
Name:Symbol Table Applications
Description:We consider various applications of symbol tables including sets, dictionary clients, indexing clients, and sparse vectors.
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.
