教学大纲
发布时间: 2013-03-25 浏览次数: 22

课程涵盖了数据结构与算法的基础性内容,主要包括:算法分析(含递归分析);堆栈、队列、链表、树等基础数据结构;排序算法;散列函数与散列表;二叉树与平衡二叉树(含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