spContent=A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures.
A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures.
—— 课程团队
课程概述
《数据结构与数据库技术》是信息类专业的重要课程之一。数据结构是研究数据组织、存储和运算的一般方法的学科。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据库技术课程讲述了当前数据库技术从基本原理到应用实践的主要内容。
数据结构部分的课程目标是使学生掌握各种常用的数据结构，提高学生程序设计的能力，内容主要包括数据结构的基本概念，线性表，堆栈和队列，树，图，查找和排序。数据库技术课程讲授数据库设计原理，使学生学会在程序设计中使用数据库管理系统。
授课目标
通过对本课程的讲授，一方面将进一步加深学生对各种计算机程序设计算法的理解，熟练运用所学算法及程序设计语言编写满足不同要求的应用程序，启发并诱导学生独立思考及发现新算法的能力。另一方面使学生掌握数据库基础、数据库开发、数据库设计以及数据库管理与维护等方面的理论知识。
通过本课程的学习，要求学生：
1、了解数据的逻辑结构和物理结构之间的关系，数据结构和数据类型的关系，数据结构和算法的关系。
2、熟悉和掌握各种基本数据结构的概念、特点和存储结构，各种基本数据结构的运算及算法设计：根据实际问题提出的要求，选择和设计合理的数据结构。
3、熟悉和掌握排序和查找算法的分析方法，根据实际问题提出的要求学会如何选择合理的排序和查找算法。
4、注重算法的应用，提高学生学以致用的能力。
5、熟悉和掌握关系代数和数据库基础理论。
6、掌握数据库开发、数据库设计及数据库管理与维护等方面的理论与实践知识。
7、加强学生算法与程序实现结合和数据库理论与数据库实践结合的能力。
8、要求学生编写程序，完成数据库设计，提高学生分析问题、解决问题的能力。
成绩 要求
【考核方式】：包括课堂提问，在线答题，在线作业及课程项目报告。
【成绩评定】：其中在线答题占20%，在线作业占40%，项目报告40%。
课程大纲
Efficient algorithms
课时目标：In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!
1.0 Course Overview
1.1 Why Study Algorithms?
1.2 Fibonacci Numbers
1.3 Computing Runtimes
1.4 Asymptotic Notation
Basic data structures
课时目标：In this module, you will learn about the basic data structures used throughout the rest of this course. Arrays and linked lists, stacks and queues, trees and it's implemented. Once you’ve completed this module, you will be able to implement any of these data structures, as well as have a solid understanding of the costs of the operations, as well as the tradeoffs involved in using each data structure.
2.1 Arrays and Linked Lists
2.2 Stacks and Queues
2.3 Trees
Divide and Conquer
课时目标：In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice.
3.1 Greedy Algorithms
3.2 Searching in an Array
3.3 Binary Search
3.4 Sorting Problem
3.5 Quick Sort
Priority Queues and Disjoint Sets
课时目标：We start this module by considering priority queues which are used to efficiently schedule jobs, either in the context of a computer operating system or in real life, to sort huge files, which is the most important building block for any Big Data processing algorithm, and to efficiently compute shortest paths in graphs.
4.1 Priority Queues: Introduction
4.2 Priority Queues: Naive Implementations
4.3 Binary Heaps
4.4 Complete Binary Trees
4.5 Pseudocode
4.6 Heap Sort
Hash Tables
课时目标：In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one.
5.1 Introduction to Hash Table
5.2 Hash Functions
Binary Search Trees
课时目标：In this module we study binary search trees, which are a data structure for doing searches on dynamically changing ordered sets. You will learn about many of the difficulties in accomplishing this task and the ways in which we can overcome them. In order to do this you will need to learn the basic structure of binary search trees, how to insert and delete without destroying this structure, and how to ensure that the tree remains balanced.
6.1 Introduction to Binary Search Trees
6.2 Binary Search Trees
6.3 Basic Operations
6.4 Balance
Decomposition of Graphs
课时目标：Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! In this module, you will learn ways to represent a graph as well as basic algorithms for decomposing graphs into parts.
7.1 Graph Basics
7.2 Representing Graphs
7.3 Exploring Graphs
7.4 Connectivity
7.5 Paths in Graphs
展开全部
预备知识
先修课程：《计算思维(编程基础)》或《编程基础（c语言）》
参考资料
- Alexander S. Kulikov, Pavel Pevzner - Learning Algorithms Through Programming and Puzzle Solving-Leanpub (2018)
- Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani - Algorithms (2011, McGraw-Hill)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms-MIT Press (2009)
- Dr. Charles R. Severance，Python for Everybody，Exploring Data Using Python 3 （2016-Jul-05 First Complete Python 3.0 version）
浙公网安备 33010802012594号
