算法课件Lecture1章节.pptVIP

ggg ttt Design and Analysis of Algorithms Sch. of Comp. Sci. and Tech. Shandong University Text Book Reference Books Text Book: Introduction to Algorithms (Second Edition) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Higher Education Press, The MIT Press, 68RMB Reference Books 《图算法》：马绍汉编著，山东大学出版社。 Algorithm Design Techniques and Analysis M.H. Alsuwaiyel (Saudi Arabia), 电子工业出版社，40元。 《算法设计与分析》：王晓东编著，清华大学出版社，30元。 《计算机算法导引—设计与分析》：卢开澄编著，清华大学出版社，21元。 《算法设计与分析》：郑宗汉编著，清华大学出版社，32元。 Grading Scheme Total 100 Assignments and Attendance: 5% Project: 10% Final Examination: 85% Caution: Please do not sign attendance for others Please do not copy others’ programs and assignment Otherwise, 0 mark will be given Please keep quiet in class Contents Part I Explore techniques on a graph Breadth-first search algorithm (BFS) Depth-first search algorithm (DFS) Applications of DFS Classifying edges (for directed or undirected) Topological sort (for directed acyclic) Strongly connected components decomposing (for directed) Bi-connected components decomposing (for undirected) Contents (continued) Part II Minimum spanning tree problem (for undirected) Kruskal’s algorithm Prim’s algorithm Bottleneck spanning tree problem Part III Single-source shortest paths problem (for directed) Bellman-Ford algorithm Dijkstra’s algorithm All-pairs shortest paths problem Matrix-multiplication based algorithm Floyd’s algorithm Johnson’s algorithm Contents (continued) Part IV Maximum flow problem (for network) Ford-Fulkerson algorithm Dinic’s algorithm Applications of Max-flow problem Maximum matching algorithm for Bipartite graphs Part V Uniquely decodable coding problem UDC algorithm Huffman’s algorithm Why Study this Course? Closely related to our lives Help to guide how others analyze and solve problems Help to develop the ability of analyzing and solving problems via computers Very interesting if you can concentrate on this course Prerequisite Data Structure