双语课程大纲.doc

双语课程大纲 课程号课程名称：数据结构与算法分析 周学时：3.0-2.0 学分：4 教学目的与基本要求：（限100－150字） 教学目的：该课程是研究非数值型数据对象的定义、表达及其有关操作。通过本课程的学习，使学生掌握解决复杂问题的程序设计技巧和性能分析，即学会针对问题的应用背景分析，选择最佳的数据结构与算法，从而培养高级程序设计分析能力。 基本要求：掌握算法的空间复杂度和时间复杂度分析的基本方法，堆栈、队列、表、树、图等的数据结构，排序和查找等算法的实现和分析，并掌握算法设计的常用技术和应用。 主要内容及学时分配： Ch2 Introduction, Algorithm analysis 3学时 Ch3.1-3 ADT, List, Stack (a) 3学时 Ch3.3-4 Stack (b), Queue; Ch4.1-2 Binary Tree 3学时 Ch4.3-4 Search Tree, AVL Tree 3学时 Ch4.5-6 Splay tree, B-tree; Ch7.1 Hash Function 3学时 Ch7.2-5, Separate Chaining, Open addressing, Rehashing Ch5.1-3(a) Binary Heap 3学时 Ch5.3(b)-5 Application Of priority Queues, d-heaps Ch6.1-4 Insertion sort, Shellsort 3学时 Ch6.5-10 Heapsort, Merge Sort, QuickSort, Bucket sort 3学时 Ch8.1-7 Equivalence relation, Union Algorithm, Path Compression Ch9.1 Graph Definitions 3学时 Ch9.2-3 Topological Sort, Shortest-path Algorithm 3学时 Mid-Term Exam 3学时 Ch9.4-5 Network Flow Problem, Minimum Spanning Tree 3学时 Ch9.6-7 Depth-first Search, NP-completeness Ch10.1 Greedy Algorithms (a) 3学时 Ch10.1-2 Greedy Algorithms (b), Divide and Conquer 3学时 Ch10.3-5 Dynamic Programming, Randomized Algorithm*, Backtracking Algorithm 3学时 Ch5.6-8 Leftist Heap, Skew Heap，Binomial Queue 3学时 相关教学环节安排： 1．采用多媒体投影教学。 2．实验课单列，每周2学时。每学期6个projects，要求学生分组合作完成。 3．每周布置作业，作业量2～3小时。 推荐教材或参考书：（含教材名、主编、出版社、出版年） 教材： Data Structures and Algorithm Analysis in C (Second Edition) 数据结构与算法分析——C语言描述（英文版 第2版），Mark Allen Weiss 著，陈越 改编；人民邮电出版社，Pearson Addison Wesley，2005 参考书 [1] 《数据结构与算法分析》(C语言版)，魏宝刚、陈越、王申康编著，浙江大学出版社，2004 [2] Data Structures, Algorithms, and Applications in C++ （数据结构算法与应用——C++语言描述 英文版）by Sartaj Sahni, McGraw-Hill 机械工业出版社，2002 Teaching Program Course Code:Course Name: Data Structures and Algorithm Analysis Weekly Hours: 3.0-2.0 Credits: 4 Teaching Goal and Basic Requirements: Teaching Objective: This course investigates the definitions, implementations, and functions related to non-numerical data objects. Students are s