当前位置: 教学大纲
 课程涵盖了数据结构与算法的基础性内容，主要包括：算法分析（含递归分析）；堆栈、队列、链表、树等基础数据结构；排序算法；散列函数与散列表；二叉树与平衡二叉树（含AVL树、红黑树和B树）；递延算法分析；关于图的算法（含广度和深度优先搜索、最小生成树、最短路径、最小费用最大流）；字符串匹配算法；算法设计思想（分而治之法、动态规划法和贪婪算法）。 Chapter 1. Algorithm analysis and recurrences 1.1 Definition of algorithm 1.2 Insertion sort and merge sort 1.3 Running time and asymptotic analysis 1.4 Θ-notation, Ω-notation, and O-notation 1.5 Recurrences 1.6 Substitution, recursion-tree method, and master method Chapter 2. Divide and conquer 2.1 Divide-and-conquer design paradigm 2.2 Recurrence for merge sort and binary search 2.3 Powering a number 2.4 Fibonacci numbers 2.5 Recursive squaring 2.6 Matrix multiplication 2.7 Strassen's algorithm Chapter 3. Basic data structure 3.1 Definition of data structure 3.2 Stacks 3.3 Queues 3.4 Linked lists 3.5 Trees 3.6 Postfix expression 3.7 Infix to postfix conversion Chapter 4. Sorting 4.1 Randomized algorithm 4.2 Quicksort and randomized quicksort 4.3 Expected running time of quicksort 4.4 Max-heaps and min-heaps 4.5 Heap operations: heapify, building, and key increasing 4.6 heap sort and priority queues 4.7 Comparisons of sort algorithms: heap sort, quick sort, insertion sort, and merge sort 4.8 Comparison sort and decision tree model 4.9 Sorting in linear time: counting-sort, radix sort, and bucket sort Chapter 5. Hash tables 5.1 Dictionary problem 5.2 Hash functions 5.3 Collisions resolution by chaining 5.4 Open addressing 5.5 Probing strategies: linear, quadratic, and double hashing 5.6 Analysis of open addressing Chapter 6. Binary search trees 6.1 Binary trees and binary search tree 6.2 Inorder, preorder, and postorder tree walk 6.3 Successor and predecessor of BST 6.4 Operations of BST: search, Minimum and maximum, constructing, deletion and insertion 6.5 Balanced search trees 6.6 AVL trees 6.7 Single and double rotation 6.8 Red-black trees 6.9 B-tree (2-3-4 tree) Chapter 7. Amortized analysis 7.1 Introduction to amortized analysis 7.2 Aggregate method 7.3 Accounting method 7.4 Potential method 7.5 Dynamic tables Chapter 8. Dynamic programming 8.1 Manufacturing problem 8.2 Matrix-chain multiplication 8.3 Elements of dynamic programming 8.4 Four steps of development 8.5 Longest common subsequence problem Chapter 9. Greedy algorithms  9.1 Activity-selection problem 9.2 Introduction to greedy solution 9.3 Steps of the greedy strategy 9.4 Knapsack problem 9.5 Huffman code Chapter 10. Graph algorithms 10.1 Graph representations 10.2 Breadth-first and depth-first search algorithms 10.3 Topological sort 10.4 Disjoint sets and strategy of union by rank and path compression 10.5 Minimum spanning tree 10.6 Prim's and Kruskal's algorithm 10.7 Single-source shortest-paths algorithms: breadth-first search, Dag shortest paths, Dijkstra algorithm, and Bellman-Ford algorithm 10.8 All-pairs shortest-paths algorithms: brute-force, dynamic programming, Floyd-Warshall algorithm, and Johnson algorithm 10.9 Ford-Fulkerson max-flow algorithm and Edmonds-Karp algorithm Chapter 11. String Matching 11.1 String matching problem 11.2 Naive string-matching algorithm 11.3 Rabin-Karp algorithm 11.4 Finite automaton 11.5 Knuth-Morris-Pratt algorithm Chapter 12. NP-complete problems 12.1 Polynomial time algorithms 12.2 Undecidable 12.3 NP-complete 12.4 Approximation algorithms 12.5 Dealing with hard problems 