Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn
Data Structures and Algorithm Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn
Polynomial time algorithms Almost all the algorithms we have studied thus far have been polynomial-time algorithms On input of size n, their worst-case running time is O(nk) for some constant k
Pol l lh ynomia l time a lgorit hms Al ll h l i h h di d h f Almost all t he a lgor i t hms we have studi e d t hus far have been polynomial-time algorithms. y Oi fi n input o f s ize n, th i e ir worst-case runniii ng t ime i s O ( n k ) for some constant k
Undecidable HALTS(P, X DIAGONAL(X 1. a: if HALTS(X, X) then goto a else halt How about DIAGONAL(DIAGONAL)
Und d bl ecidable HALTS(P, X) DIAGO AN L(X) 1. a: if HALTS(X, X) 2. then goto a 3. else halt How about DIAGONAL(DIAGONAL)
Shortest vs longest simple paths Shortest simple path Given a directed graph G=(V, E), find the shortest simple path between two vertices Longest simple path Given a directed graph G=(v, E), find the longest simple path between two vertices
Sh l l h Shortest vs. longest simp le pat h s Sh i l h Shortest s imp le pat h Given a directed graph G = ( V, E ) , find the shortest si l hb i imp le pat h between two vert ices. Longest simple path Longest simple path Given a directed graph G = ( V, E ) , find the longest simple path between two vertices simple path between two vertices
Konigsberg's Bridges problem D B The river Pregel divides the town of Konigsberg into four separate land masses, A, B, C, and D Seven bridges connect the various parts of town, C and some of the town's curious citizens wondered if it were possible to take a journey across all seven bridges without having to cross B any bridge more than once
Konigsb ' d bl berg's Bri dges Problem A C D B The river Pregel divides the town of Konigsberg The river Pregel divides the town of Konigsberg A into four separate land masses, A, B, C, and D. Seven bridges connect the various parts of town, C D Seven bridges connect the various parts of town, and some of the town's curious citizens wondered if it were possible to take a journey B across all seven bridges without having to cross any bridge more than once