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 ConquerExploring 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! A t

3、op down (recursive) solution A bottom up (iterative) Examples of Decrease and ConquerDecrease 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, sub

4、setsDecrease 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 problemsVariable-size decrease: the size reduction pattern varies from one iteration of an algorithm to another.Euclids A Typical Dec

5、rease 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.g., Bi

6、nary 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 anDecrease b

7、y one Bottom-up: iterative (brute Force) Top-down:recursiveDivide 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 SortA decr

8、ease 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 orderfor i

9、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 A0.n-1/I

10、nput: 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减治法的定义？减法法的三种类型是什么，分别举例说明？减治法和分治法的区别是什么，可举例说明了？1.5.1章第1题 摆渡的士兵2.

11、5.1章第2题 交替放置的玻璃杯3.减治法实现插入排序，比较顺序和逆序情况下键值比较次数，并输出比较次数。4.给出无向图DFS和BFS的遍历顺序 Graph TraversalMany problems require processing all graph vertices in a systematic fashionGraph traversal algorithms: Depth-first search Breadth-first Depth-first searchThe idea traverse “deeper” whenever possible. On each iter

12、ation, 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 edge

13、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 onto

14、 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=(V,E

15、)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 connected

16、 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 but

17、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 all it

18、s 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(Continu

19、ed)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 all v

20、ertices 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 Properties

21、 of DFSDefinition: 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 called

22、 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 the fo

23、llowing conditions holds: 1. u is a descendant of v, and du, fu is a subinterval of dv, fv.2. u is an ancestor of v, and dv, fv is a subinterval of du, fu.3. 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 d

24、escendants 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 theoremTheorem: 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 from u

25、 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 DFSFind the strongly connected components of a directed graph.Find the articulation points of an undirected graphTopological sort of a directed graphClassification of edges.Verify if an undirected graph is connected or not.Verify if a directed graph is semi-connected or not.Verify if

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

28、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 vinitialize queue with v /e

29、nqueuewhile 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 vertex with 0for each

30、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:1.Visit all vertices directly connected to starting vertex2.Visit all vertices that are two

31、 edges away from the starting vertex3.Visit all vertices that are three edges away from the starting vertex4. 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.wGray vertices a

32、re 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 colorv, which has thre

33、e 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 Part: lines 5 - 9M

34、ain Part: lines 10 18Enqueue(Q, v): add a vertex v to the end of the queue QDequeue(Q): Extract the first vertex in the queue Q Breadth-first search: NotesBFS has same efficiency as DFS and can be implemented with graphs represented as: Adjacency matrices: (|V |2) Adjacency linked lists: (|V |+|E| )

35、Applications: checking connectivity finding connected components finding paths between two vertices with the smallest number of Topological SortingProblem: 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 courses s