计算模型与算法技术：6-Transform-and-Conquer

1、Chapter 6 Transform-and-ConquerCopyright 2007 Pearson Addison-Wesley. All rights reserved.Transform and ConquerThis group of techniques solves a problem by a transformationto a simpler/more convenient instance of the same problem (instance simplification) to a different representation of the same in

2、stance (representation change)to a different problem for which an algorithm is already available (problem reduction) Transform-and-conquer strategy3Problems instanceSimpler instanceAnother representationAnother problems instanceSolution446.1 PresortingInstance simplification - PresortingSolve a prob

3、lems instance by transforming it into another simpler/easier instance of the same problemPresortingMany problems involving lists are easier when list is sorted.searching computing the median (selection problem)checking if all elements are distinct (element uniqueness)Also: Topological sorting helps

4、solving some problems for dags.Presorting is used in many geometric algorithms.How fast can we sort ?Efficiency of algorithms involving sorting depends on efficiency of sorting.Theorem (see Sec. 11.2): log2 n! n log2 n comparisons are necessary in the worst case to sort a list of size n by any compa

5、rison-based algorithm.Note: About nlog2 n comparisons are also sufficient to sort array of size n (by mergesort).Example 1 Checking element uniqueness in an arrayThe brute-force algorithm compared pairs of arrays elements until either two equal elements were found or no more pairs were left.Its wors

6、t-case efficiency was in O(n2) 7Element Uniqueness with PresortingPresorting-based algorithm Stage 1: sort by efficient sorting algorithm (e.g. mergesort) Stage 2: scan array to check pairs of adjacent elements Efficiency: Brute force algorithm Compare all pairs of elements Efficiency: O(n2) Another

7、 algorithm? HashingSearching with presortingProblem: Search for a given K in A0.n-1 Presorting-based algorithm:Stage 1 Sort the array by an efficient sorting algorithm Stage 2 Apply binary search Efficiency: (nlog n) + O(log n) = (nlog n) Good or bad?Why do we have our dictionaries, telephone direct

8、ories, etc. sorted?Example 2 Computing a modeA mode is a value that occurs most often in a given list of numbers.For example, for 5, 1, 5, 7, 6, 5, 7,the mode is 5.The brute-force approach to computing a mode would scan the list and compute the frequencies of all its distinct values, then find the v

9、alue with the largest frequency.11It is not difficult to see that the worst-case input for this algorithm is a list with no equal elements.1214The analysis here is similar to the analysis of Example 1: the running time of the algorithm will be dominated by the time spent on sorting since the remaind

10、er of the algorithm takes linear time (why?). Consequently, with an sort, this methods worst-case efficiency will be in a better asymptotic class than the worst case efficiency of brute-force algorithm.n log n15Consider the problem of searching for a given value v in a given array of n sortable item

11、s.The brute-force solution here is sequential search (Section 3.1), which needs n comparisons in the worst case.Example 3 Searching problemT(n)=Tsort(n)+Tsearch(n)=(n log n)+(log n)=(n log n)16166.2 Gaussian EliminationInstance simplification Gaussian EliminationGiven: A system of n linear equations

12、 in n unknowns with an arbitrary coefficient matrix.Transform to: An equivalent system of n linear equations in n unknowns with an upper triangular coefficient matrix. Solve the latter by substitutions starting with the last equation and moving up to the first one.a11x1 + a12x2 + + a1nxn = b1 a11x1+

13、 a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 a22x2 + + a2nxn = b2 an1x1 + an2x2 + + annxn = bn annxn = bn Gaussian Elimination (cont.)The transformation is accomplished by a sequence of elementary operations on the systems coefficient matrix (which dont change the systems solution): for i 1 to

14、 n-1 do replace each of the subsequent rows (i.e., rows i+1, , n) by a difference between that row and an appropriate multiple of the i-th row to make the new coefficient in the i-th column of that row 0Elementary operations(1)Exchanging two equation of the system(2)Replacing an equation with its no

15、nzero multiple(3)Replacing an equation with a sum or difference of this equation and some multiple of another equation19Example of Gaussian EliminationSolve 2x1 - 4x2 + x3 = 6 3x1 - x2 + x3 = 11 x1 + x2 - x3 = -3 Gaussian elimination 2 -4 1 6 2 -4 1 6 3 -1 1 11 row2 (3/2)*row1 0 5 -1/2 2 1 1 -1 -3 r

16、ow3 (1/2)*row1 0 3 -3/2 -6 row3(3/5)*row2 2 -4 1 6 0 5 -1/2 2 0 0 -6/5 -36/5 Backward substitution x3 = (-36/5) / (-6/5) = 6 x2 = (2+(1/2)*6) / 5 = 1 x1 = (6 6 + 4*1)/2 = 2Example of Gaussian EliminationSolve 2x1 - x2 + x3 = 1 4x1 + x2 - x3 = 5 x1 + x2 + x3 = 0 Gaussian elimination 2 -1 1 1 2 -1 1 1

17、 4 1 -1 5 row2 (4/2)*row1 0 3 -3 3 1 1 1 0 row3 (1/2)*row1 0 3/2 1/2 -1/2 row3(1/2)*row2 2 -1 1 1 0 3 -3 3 0 0 2 -2 Backward substitution x3 = (-2) /2 = -1 x2 = (3-(-3)*x3) / 3 = 0 x1 = (1 x3 (-1)x2)/2 = 123First, it is not always correct: if Ai,i=0, we cannot divide by it and hence cannot use the i

18、-th row as a pivot for the i-th iteration of the algorithm.In such case, we should take advantage of the first elementary operation and exchange the i-th row with some row below it that has a nonzero coefficient in the i-th column. 24The modification, called partial pivoting, guarantees that the mag

19、nitude of the scaling factor will never exceed 1.The second observation in the fact that the innermost loop is written with a glaring inefficiency.Pseudocode and Efficiency of Gaussian EliminationStage 1: Reduction to the upper-triangular matrixfor i 1 to n-1 do for j i+1 to n do for k i to n+1 do A

20、j, k Aj, k - Ai, k * Aj, i / Ai, i /improve!Stage 2: Backward substitutionfor j n downto 1 do t 0 for k j +1 to n do t t + Aj, k * xk xj (Aj, n+1 - t) / Aj, j Efficiency: (n3) + (n2) = (n3) 2728286.3 Balance Search TreeBalanced Search Trees Attractiveness of binary search tree is marred by the bad (

21、linear) worst-case efficiency. Two ideas to overcome it are: to rebalance binary search tree when a new insertion makes the tree “too unbalanced” AVL trees red-black trees to allow more than one key per node of a search tree 2-3 trees 2-3-4 trees B-trees Searching ProblemProblem: Given a (multi)set

22、S of keys and a search key K, find an occurrence of K in SSearching must be considered in the context of:file size (internal vs. external)dynamics of data (static vs. dynamic)Dictionary operations (dynamic data):find (search)insertdeleteTaxonomy of Searching AlgorithmsList searchingsequential search

23、binary searchinterpolation searchTree searching binary search treebinary balanced trees: AVL trees, red-black treesmultiway balanced trees: 2-3 trees, 2-3-4 trees, B treesHashingopen hashing (separate chaining)closed hashing (open addressing)Binary Search TreeArrange keys in a binary tree with the b

24、inary search tree property:KKExample: 5, 3, 1, 10, 12, 7, 9Dictionary Operations on Binary Search TreesSearching straightforwardInsertion search for key, insert at leaf where search terminatedDeletion 3 cases:deleting key at a leafdeleting key at node with single childdeleting key at node with two c

25、hildren Efficiency depends of the trees height: log2 n h n-1,with height average (random files) be about 3log2 n Thus all three operations have worst case efficiency: (n) average case efficiency: (log n) Bonus: inorder traversal produces sorted listBalanced trees: AVL treesDefinition An AVL tree is

26、a binary search tree in which, for every node, the difference between the heights of its left and right subtrees, called the balance factor, is at most 1 (with the height of an empty tree defined as -1)Tree (a) is an AVL tree; tree (b) is not an AVL treeRotationsIf a key insertion violates the balan

27、ce requirement at some node, the subtree rooted at that node is transformed via one of the four rotations. (The rotation is always performed for a subtree rooted at an “unbalanced” node closest to the new leaf.)Single R-rotationDouble LR-rotationGeneral case: Single R-rotationGeneral case: Double LR

28、-rotationAVL tree construction - an exampleConstruct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7 AVL tree construction - an example (cont.)Analysis of AVL treesh 1.4405 log2 (n + 2) - 1.3277 average height: 1.01 log2n + 0.1 for large n (found empirically)Search and insertion are O(log n) Deletion i

29、s more complicated but is also O(log n)Disadvantages: frequent rotationscomplexityA similar idea: red-black trees (height of subtrees is allowed to differ by up to a factor of 2) Multiway Search TreesDefinition A multiway search tree is a search tree that allowsmore than one key in the same node of

30、the tree.Definition A node of a search tree is called an n-node if it contains n-1 ordered keys (which divide the entire key range into n intervals pointed to by the nodes n links to its children): Note: Every node in a classical binary search tree is a 2-node k1 k2 kn-1 k1k1, k2 ) kn-12-3 Tree Defi

31、nition A 2-3 tree is a search tree that may have 2-nodes and 3-nodes height-balanced (all leaves are on the same level)A 2-3 tree is constructed by successive insertions of keys given, with a new key always inserted into a leaf of the tree. If the leaf is a 3-node, its split into two with the middle

32、 key promoted to the parent. 2-3 tree construction an exampleConstruct a 2-3 tree the list 9, 5, 8, 3, 2, 4, 7 44Analysis of 2-3 treeslog3 (n + 1) - 1 h log2 (n + 1) - 1Search, insertion, and deletion are in (log n) The idea of 2-3 tree can be generalized by allowing more keys per node 2-3-4 trees B

33、-trees46466.4 Heap and HeapsortHeaps and HeapsortDefinition A heap is a binary tree with keys at its nodes (one key per node) such that:It is essentially complete, i.e., all its levels are full except possibly the last level, where only some rightmost keys may be missingThe key at each node is keys

34、at its childrenIllustration of the heaps definitiona heapnot a heapnot a heapNote: Heaps elements are ordered top down (along any path down from its root), but they are not ordered left to rightSome Important Properties of a HeapGiven n, there exists a unique binary tree with n nodes that is essenti

35、ally complete, with h = log2 nThe root contains the largest keyThe subtree rooted at any node of a heap is also a heapA heap can be represented as an arrayHeaps Array RepresentationStore heaps elements in an array (whose elements indexed, for convenience, 1 to n) in top-down left-to-right orderExamp

36、le:Left child of node j is at 2jRight child of node j is at 2j+1Parent of node j is at j/2 Parental nodes are represented in the first n/2 locations9153421 2 3 4 5 69 5 3 1 4 2Step 0: Initialize the structure with keys in the order givenStep 1: Starting with the last (rightmost) parental node, fix t

37、he heap rooted at it, if it doesnt satisfy the heap condition: keep exchanging it with its largest child until the heap condition holdStep 2: Repeat Step 1 for the preceding parental nodeHeap Construction (bottom-up)Example of Heap ConstructionConstruct a heap for the list 2, 9, 7, 6, 5, 8Pseudopodi

38、a of bottom-up heap constructionTherefore, the total number of key comparisons in the worst case will be54Maximum Key Deletion from a heapStep 1. Exchange the roots key with the last key K of the leap.Step 2. Decrease the heaps size by 1.Step 3. “Heapify” he smaller tree by sifting K down the tree e

39、xactly in the same way we did it in the bottom-up heap construction algorithm.O(nlogn)55Stage 1: Construct a heap for a given list of n keysStage 2: Repeat operation of root removal n-1 times:Exchange keys in the root and in the last (rightmost) leafDecrease heap size by 1If necessary, swap new root

40、 with larger child until the heap condition holdsHeapsortSort the list 2, 9, 7, 6, 5, 8 by heapsortStage 1 (heap construction) Stage 2 (root/max removal) 1 9 7 6 5 8 9 6 8 2 5 7 2 9 8 6 5 7 7 6 8 2 5 | 9 2 9 8 6 5 7 8 6 7 2 5 | 9 9 2 8 6 5 7 5 6 7 2 | 8 9 9 6 8 2 5 7 7 6 5 2 | 8 9 2 6 5 | 7 8 9 6 2

41、5 | 7 8 9 5 2 | 6 7 8 9 5 2 | 6 7 8 9 2 | 5 6 7 8 9Example of Sorting by Heapsort58Stage 1: Build heap for a given list of n keysworst-case C(n) = Stage 2: Repeat operation of root removal n-1 times (fix heap)worst-case C(n) = Both worst-case and average-case efficiency: (nlogn) In-place: yesStabili

42、ty: no (e.g., 1 1)2(h-i) 2i = 2 ( n log2(n + 1) (n)i=0h-1# nodes at level ii=1n-1 2log2 i (nlogn) Analysis of HeapsortA priority queue is the ADT of a set of elements with numerical priorities with the following operations:find element with highest prioritydelete element with highest priorityinsert

43、element with assigned priority (see below)Heap is a very efficient way for implementing priority queuesTwo ways to handle priority queue in which highest priority = smallest numberPriority QueueInsertion of a New Element into a HeapInsert the new element at last position in heap. Compare it with its

44、 parent and, if it violates heap condition,exchange themContinue comparing the new element with nodes up the tree until the heap condition is satisfiedExample: Insert key 10Efficiency: O(log n)62626.5 Horners Rule and Binary ExponentiationHorners Rule For Polynomial EvaluationGiven a polynomial of d

45、egree np(x) = anxn + an-1xn-1 + + a1x + a0and a specific value of x, find the value of p at that point.Two brute-force algorithms:p 0 p a0; power 1for i n downto 0 do for i 1 to n do power 1 power power * x for j 1 to i do p p + ai * power power power * x return p p p + ai * powerreturn pHorners Rul

46、e Example: p(x) = 2x4 - x3 + 3x2 + x - 5 = = x(2x3 - x2 + 3x + 1) - 5 = = x(x(2x2 - x + 3) + 1) - 5 = = x(x(x(2x - 1) + 3) + 1) - 5 Substitution into the last formula leads to a faster algorithm Same sequence of computations are obtained by simply arranging the coefficient in a table and proceeding

47、as follows:coefficients2-1 3 1-5 x=3 Horners Rule pseudocodeEfficiency of Horners Rule: # multiplications = # additions = n Synthetic division of of p(x) by (x-x0) Example: Let p(x) = 2x4 - x3 + 3x2 + x - 5. Find p(x):(x-3) Computing an (revisited)Left-to-right binary exponentiation Initialize produ

48、ct accumulator by 1.Scan ns binary expansion from left to right and do the following: If the current binary digit is 0, square the accumulator (S);if the binary digit is 1, square the accumulator and multiply it by a (SM).Example: Compute a13. Here, n = 13 = 11012. binary rep. of 13: 1 1 0 1 SM SM S

49、 SM accumulator: 1 12*a=a a2*a = a3 (a3)2 = a6 (a6)2*a= a13 (computed left-to-right)Efficiency: (b-1) M(n) 2(b-1) where b = log2 n + 1Computing an (cont.)Right-to-left binary exponentiation Scan ns binary expansion from right to left and compute an as the product of terms a2 i corresponding to 1s in

50、 this expansion. Example Compute a13 by the right-to-left binary exponentiation. Here, n = 13 = 11012. 1 1 0 1 a8 a4 a2 a : a2 i terms a8 * a4 * a : product (computed right-to-left)Efficiency: same as that of left-to-right binary exponentiation Problem ReductionThis variation of transform-and-conque

51、r solves a problem by a transforming it into different problem for which an algorithm is already available.To be of practical value, the combined time of the transformation and solving the other problem should be smaller than solving the problem as given by another method. Examples of Solving Problems by Reductioncomputing lcm(m, n) via computing gcd(m, n)countin