Lecture05DecreaseandConquer--5.1-5.3

1、 Decrease and ConquerDecrease and Conquer Decrease and conquer technique 5.1Insertion sort 5.2DFS and BFS 5.3Topological Expected OutcomesStudents should be able to Explain the idea and steps of decrease and conquer Explain the ideas of insertion sort, DFS, BFS, topological sort Analyze the time com

2、plexity of the above Decrease and Conquer Exploring the relationship between a solution to a given instance of (e.g., P(n) )a problem and a solution to a smaller instance (e.g., P(n/2) or P(n-1) )of the same problem. Use top down(recursive) or bottom up (iterative) to solve the problem. Example, n!

3、A top down (recursive) solution A bottom up (iterative) Examples of Decrease and Conquer Decrease by a constant: the size of the problem is reduced by the same constant on each iteration/recursion of the algorithm.Insertion sortGraph search algorithms: DFS BFS Algorithms for generating permutations,

4、 subsets Decrease by a constant factor: the size of the problem is reduced by the same constant factor on each iteration/recursion of the algorithm.Binary search Fake-coin problems Variable-size decrease: the size reduction pattern varies from one iteration of an algorithm to another.Euclids A Typic

5、al Decrease by One Techniquesubproblem of size n-1a solution to thesubproblem a solution tothe original problema problem of size ne.g., n! A Typical Decrease by a Constant Factor (half) Techniquesubproblem of size n/2a solution to the subproblem a solution tothe original problema problem of size ne.

6、g., Binary search 7A Typical Divide and Conquer Techniquesubproblem 2 of size n/2subproblem 1 of size n/2a solution to subproblem 1a solution tothe original problema solution to subproblem 2a problem of size ne.g., mergesort Whats the Difference?Consider the problem of exponentiation: Compute an Dec

7、rease by one Bottom-up: iterative (brute Force) Top-down:recursive Divide and conquer: Decrease by a constant factor:an= a*a*a*a*.*aan= an-1* aif n 1 = aif n = 1an= a n/2 * a n/2 if n 1 = aif n = 1an = (an/2 ) 2 if n is even and positive = (a(n-1)/2 ) 2 * a if n is odd and 1 = a if n = 1 Insertion S

8、ortA decrease by one algorithm A bottom-up (iterative) solution A top-down (recursive) Insertion Sort: an Iterative SolutionALGORITHM InsertionSortIter(A0.n-1)/An iterative implementation of insertion sort/Input: An array A0.n-1 of n orderable elements/Output: Array A0.n-1 sorted in nondecreasing or

9、derfor i 1 to n 1 do/ i: the index of the first element of the unsorted part.key = Aifor j i 1 to 0 do/ j: the index of the sorted part of the arrayif (key 1InsertionSortRecur(A0.n-2, n-2)Insert(A0.n-2, n-1) /insert An-1 to A0.n-2ALGORITHM Insert(A0.m-1, m)/Insert Am to the sorted subarray A0.m-1 of

10、 A0.n-1/Input: A subarray A0.m of A0.n-1/Output: Array A0.m sorted in nondecreasing orderkey = Amfor j m 1 to 0 doif (key Aj)Aj+1 AjelsebreakAj +1 keyRecurrence relation?Index of the element/key to be inserted.Index of the last Chap 05 Exercises減治法的定義？減法法的三種類型是什么，分別舉例說明？減治法和分治法的區(qū)別是什么，可舉例說明了？5.1章第1題

11、擺渡的士兵5.1章第2題 交替放置的玻璃杯減治法實(shí)現(xiàn)插入排序，比較順序和逆序情況下鍵值比較次數(shù)，并輸出比較次數(shù)。給出無向圖DFS和BFS的遍歷順序 Graph Traversal Many problems require processing all graph vertices in a systematic fashionGraph traversal algorithms: Depth-first search Breadth-first Depth-first search The idea traverse “deeper” whenever possible. On each i

12、teration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. If there are more than one neighbors, break the tie by the alphabetic order of the vertices. When reaching a dead end ( a vertex with no adjacent unvisited vertices), the algorithm backs up one ed

13、ge to the parent and tries to continue visiting unvisited vertices from there. The algorithm halts after backing up to the starting vertex, with the latter being a dead end. Similar to preorder tree traversals Its convenient to use a stack to trace the operation of depth-first search. Push a vertex

14、onto the stack when the vertex is reached for the first time. Pop a vertex off the stack when it becomes a dead Example undirected graphsDepth-first traversal:Give the order in which the vertices were reached.abefcdgha b f e g c d Depth-first search (DFS) Pseudocode for Depth-first-search of graph G

15、=(V,E)dfs(v)/Use depth-first to visit a connected component starting /from vertex v.count count + 1mark v with count /visit vertex vfor each vertex w adjacent to v doif w is marked with 0 /w has not been visited yet.dfs(w)DFS(G) / Use depth-first to visit a graph, which might / contain multiple conn

16、ected components.count 0 /visiting sequence number mark each vertex with 0 / (unvisited)for each vertex v V doif v is marked with 0 /w has not been visited yet.dfs(v) Another Algorithm: Four Arrays for DFS Algorithmcoloru: the color of each vertex visitedWHITE means undiscoveredGRAY means discovered

17、 but not finished processingBLACK means finished processing.u: the predecessor of u, indicating the vertex from which u is discovered.du: discovery time, a counter indicating when vertex u is discovered.fu: finishing time, a counter indicating when the processing of vertex u (and the processing of a

18、ll its descendants ) is DFS A DFS Algorithm (Continued) DFS Algorithm (Example)abfecgd1/ Example(continued)1/abfecgd2/ Example(continued)abfecgd2/1/3/ Example(Continued)abfecgd2/1/3/4/ Example(Continued)abfecgd2/1/3/4/ Example(Continued)abfecgd2/1/3/64/ Example(Continued)abfecgd2/71/3/64/ Example(Co

19、ntinued)abfecgd2/71/83/64/ Example(Continued)abfecgd2/71/83/64/59/ Example(Continued)abfecgd2/71/83/64/59/10/ Example(Continued)abfecgd2/71/83/64/59/10/ Example(continued)abfecgd2/71/83/64/59/10/1112/ Example(Continued)abfecgd2/71/83/64/59/1410/1112/13 What does DFS do?Given a graph G, it traverses

20、all vertices of G and Constructed a collection of rooted trees together with a set of source vertices (roots)Outputs two arrays d /f Note: forest is stored in array , the value of a root is null.DFS forest: DFS creates a forest F = (V, Ef), where Ef = (u, u)| where is computed in the DFS-VISIT Prope

21、rties of DFS Definition: in a rooted forest, on the simple path from the root to each vertex, a vertex u is called ancestor of all the vertices following it, and descendant of all the vertices preceding it. Note: u = v if and only if DFS-VISIT(v) was called during a search of us adjacency list. u is

22、 called the parent of v. So:vertex v is a descendant of vertex u in the depth-first forest if and only if v is discovered during the time in which u is Exampleabfecgd2/71/83/64/59/1410/1112/13 Properties of DFSParenthesis Theorem: In any DFS of a graph, for each pair of vertices u, v, exactly one of

23、 the following conditions holds: u is a descendant of v, and du, fu is a subinterval of dv, fv. u is an ancestor of v, and dv, fv is a subinterval of du, fu.1. Neither u is a descendant of v nor v is a descendant of u, and du, fu and dv, fv are disjoint. The nth Catalan Number: nnnnC211)( Nesting of

24、 descendants intervalsCorollary: vertex v is a proper descendant of vertex u in the depth-first forest for a graph G if and only if du dv fv White-path theorem Theorem: In a depth-first forest of a graph G = (V, E), vertex v is a descendant of u if and only if at time du, vertex v can be reached fro

25、m u along a path consisting entirely of white Example directed graphDepth-first traversal: Give the order in which the vertices were reached.abefcdgha b f g h e c Depth-first search: NotesDFS can be implemented with graphs represented as: Adjacency matrices: (|V |2) Adjacency linked lists: (|V |+|E|

26、 ) Applications of DFS Find the strongly connected components of a directed graph. Find the articulation points of an undirected graph Topological sort of a directed graph Classification of edges. Verify if an undirected graph is connected or not. Verify if a directed graph is semi-connected or not.

27、 Verify if a directed graph is singly connected or not. Breadth-first search (BFS) Archetype for Prims minimum-spanning-tree algorithm Archetype for Dijkstras single-source shortest-paths algorithm The idea Traverse “wider” whenever possible. Discover all vertices at distance k from s (on level k) b

28、efore discovering any vertices at distance k +1 (at level k+1) Similar to level-by-level tree traversals Instead of a stack, breadth-first uses a Example undirected graphBreadth-first traversal:abefcdgha b e f g c h Breadth-first search algorithmbfs(v)count count + 1mark v with count /visit vinitial

29、ize queue with v /enqueuewhile queue is not empty do a front of queue /dequeue for each vertex w adjacent to a do if w is marked with 0 /w hasnt been visited.count count + 1mark w with count /visit wadd w to the end of the queue /enqueue remove a from the front of the queueBFS(G)count 0mark each ver

30、tex with 0for each vertex v V do if v is marked with 0 bfs(v) Example directed graphBreadth-first traversal:abefcdgha b e f g h c Another Implementation: The Breadth-First SearchThe idea of the BFS:Visit the vertices as follows: Visit all vertices directly connected to starting vertex Visit all vert

31、ices that are two edges away from the starting vertex Visit all vertices that are three edges away from the starting vertex wInitially, s is made GRAY, others are colored WHITE.wWhen a gray vertex is processed, its color is changed to black, and the color of all white neighbors is changed to gray.1.

32、Gray vertices are kept in a queue Q What does the BFS do? Given a graph G = (V, E), the BFS returns: The shortest distance dv from s to v The predecessor or parent v, which is used to derive a shortest path from s to vertex v. In addition to the two arrays dv and v, BFS also uses another array color

33、v, which has three possible values: WHITE: represented “undiscovered” vertices; GRAY: represented “discovered” but not “processed” vertices; BLACK: represented “processed” vertices. The Breadth-First Search(more details) G is given by its adjacency-lists. Initialization: First Part: lines 1 4 Second

34、 Part: lines 5 - 9 Main Part: lines 10 18 Enqueue(Q, v): add a vertex v to the end of the queue Q Dequeue(Q): Extract the first vertex in the queue Q Breadth-first search: Notes BFS has same efficiency as DFS and can be implemented with graphs represented as: Adjacency matrices: (|V |2) Adjacency li

35、nked lists: (|V |+|E| ) Applications: checking connectivity finding connected components finding paths between two vertices with the smallest number of Topological Sorting Problem: Given a Directed Acyclic Graph(DAG) G = (V, E), find a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering. Example: Give an order of the c