|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/algorithms-searching-sorting-indexing
课程评论：没有评论
课程名称：搜索、排序和索引算法 概述：本课程涵盖算法设计和分析的基础知识，以及排序数组的算法、优先队列等数据结构、哈希函数和应用程序（如布隆过滤器）。 “搜索、排序和索引算法”课程可作为科罗拉多大学博尔德分校数据科学硕士学位（MS-DS）的一部分获得学分，该学位通过Coursera平台提供。该项目是一个跨学科的学位项目，汇聚了来自科罗拉多大学博尔德分校应用数学、计算机科学、信息科学等多个部门的教师。由于采用基于表现的录取方式且没有申请流程，MS-DS非常适合具有广泛本科教育背景和/或计算机科学、信息科学、数学及统计等专业经验的个人。有关MS-DS项目的更多信息，请访问：https://www.coursera.org/degrees/master-of-science-data-science-boulder。 课程大纲： 1. **算法基础：通过搜索和排序** - 学生将通过插入排序、二分查找和归并排序等三个实例学习算法的基础知识。通过这些算法，学生将接触算法分析，证明算法的正确性和执行时间的增长界限，并理解更快算法及渐近复杂性（通过大O、小Ω和大Θ符号）。 2. **堆和哈希表数据结构** - 学生将学习组织数据以加快某些操作的数据结构的基本知识，包括先进先出队列和后进先出栈等简单数据结构。接着，引入堆数据结构及其基本性质，并学习堆的插入、删除和查找最小元素的算法及时间复杂度，最后研究优先队列数据结构及其应用。 3. **随机化：快速排序、快速选择和哈希表** - 学习快速排序和快速选择算法，以有效地对数组进行排序和选取第k小元素，同时介绍随机化在算法设计中的作用。随后，学习哈希表这一非常实用的数据结构，以实现对大量数据的高效搜索和检索。 4. **哈希表的应用** - 学习随机化枢轴选择用于快速排序和快速选择，分析随机化快速排序/快速选择算法的复杂性。同时，学习开放地址哈希，这是一种简化哈希表设计的技术，并研究哈希函数的设计及其分析。最后，介绍并分析布隆过滤器，这些过滤器在流数据查询和计数等各种应用中非常有用。
Name:Basics of Algorithms Through Searching and Sorting
Description:In this module the student will learn the very basics of algorithms through three examples: insertion sort (sort an array in ascending/descending order); binary search: search whether an element is present in a sorted array and if yes, find its index; and merge sort (a faster method for sorting an array). Through these algorithms the student will be introduced to the analysis of algorithms -- i.e, proving that the algorithm is correct for the task it has been designed for and establishing a bound on how the time taken to execute the algorithm grows as a function of input. The student is also exposed to the notion of a faster algorithm and asymptotic complexity through the O, big-Omega and big-Theta notations.
Name:Heaps and Hashtable Data Structures
Description:In this module, the student will learn about the basics of data structures that organize data to make certain types of operations faster. The module starts with a broad introduction to data structures and talks about some simple data structures such as first-in first out queues and last-in first out stack. Next, we introduce the heap data structure and the basic properties of heaps. This is followed by algorithms for insertion, deletion and finding the minimum element of a heap along with their time complexities. Finally, we will study the priority queue data structure and showcase some applications.
Name:Randomization: Quicksort, Quickselect, and Hashtables
Description:We will go through the quicksort and quickselect algorithms for sorting and selecting the kth smallest element in an array efficiently. This will also be an introduction to the role of randomization in algorithm design. Next, we will study hashtables: a highly useful data structure that allows for efficient search and retrieval from large amounts of data. We will learn about the basic principles of hash-table and operations on hashtables.
Name:Applications of Hashtables
Description:In this module, we will learn randomized pivot selection for quicksort and quickselect. We will learn how to analyze the complexity of the randomized quicksort/quickselect algorithms. We will learn open address hashing: a technique that simplifies hashtable design. Next we will study the design of hash functions and their analysis. Finally, we present and analyze Bloom filters that are used in various applications such as querying streaming data and counting.
This course covers basics of algorithm design and analysis, as well as algorithms for sorting arrays, data structures such as priority queues, hash functions, and applications such as Bloom filters. Algorithms for Searching, Sorting, and Indexing can be taken for academic credit as part of CU Boulder’s Master of Science in Data Science (MS-DS) degree offered on the Coursera platform. The MS-DS is an interdisciplinary degree that brings together faculty from CU Boulder’s departments of Applied Mathematics, Computer Science, Information Science, and others. With performance-based admissions and no application process, the MS-DS is ideal for individuals with a broad range of undergraduate education and/or professional experience in computer science, information science, mathematics, and statistics. Learn more about the MS-DS program at https://www.coursera.org/degrees/master-of-science-data-science-boulder.
