1、,1,Transform and Conquer,This group of techniques solves a problem by a transformation to a simpler/more convenient instance of the same problem (instance simplification) a different representation of the same instance (representation change) a different problem for which an algorithm is already ava

2、ilable (problem reduction),2,Instance simplification - Presorting,Solve a problems instance by transforming it into another simpler/easier instance of the same problem Presorting Many problems involving lists are easier when list is sorted, e.g. searching computing the median (selection problem) che

3、cking if all elements are distinct (element uniqueness) Also: Topological sorting helps solving some problems for dags. Presorting is used in many geometric algorithms.,3,How fast can we sort ?,Efficiency of algorithms involving sorting depends on efficiency of sorting. Theorem (see Sec. 11.2): log2

4、 n! n log2 n comparisons are necessary in the worst case to sort a list of size n by any comparison-based algorithm. Note: About nlog2 n comparisons are also sufficient to sort array of size n (by mergesort).,4,Searching with presorting,Problem: Search for a given K in A0.n-1 Presorting-based algori

5、thm: 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 directories, etc. sorted?,5,Element Uniqueness with presorting,Presorting-based algorithm Stage 1: sort by effi

6、cient sorting algorithm (e.g. mergesort) Stage 2: scan array to check pairs of adjacent elements Efficiency: (nlog n) + O(n) = (nlog n) Brute force algorithm Compare all pairs of elements Efficiency: O(n2) Another algorithm? Hashing,Instance simplification Gaussian Elimination,Given: A system of n l

7、inear equations 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 + + a1

8、nxn = b1 a1,1x1+ a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 a22x2 + + a2nxn = b2 an1x1 + an2x2 + + annxn = bn annxn = bn,6,Gaussian Elimination (cont.),The transformation is accomplished by a sequence of elementary operations on the systems coefficient matrix (which dont change the systems so

9、lution): for i 1 to 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 0,7,Example of Gaussian Elimination,Solve 2x1 - 4x2 + x3 = 6 3x1 - x2 + x3 = 11

10、 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 row3 (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 = 2,8,Pseudocode and Effi

11、ciency of Gaussian Elimination,Stage 1: Reduction to an upper-triangular matrix for i 1 to n-1 do for j i+1 to n do for k i to n+1 do Aj, k Aj, k - Ai, k * Aj, i / Ai, i /improve! Stage 2: Back substitutionsfor 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 Efficien

12、cy: (n3) + (n2) = (n3),9,10,Searching Problem,Problem: Given a (multi)set S of keys and a search key K, find an occurrence of K in S, if any Searching must be considered in the context of: file size (internal vs. external) dynamics of data (static vs. dynamic) Dictionary operations (dynamic data): f

13、ind (search) insert delete,11,Taxonomy of Searching Algorithms,List searching sequential search binary search interpolation search Tree searching binary search tree binary balanced trees: AVL trees, red-black trees multiway balanced trees: 2-3 trees, 2-3-4 trees, B trees Hashing open hashing (separa

14、te chaining) closed hashing (open addressing),12,Binary Search Tree,Arrange keys in a binary tree with the binary search tree property:,K,K,K,Example: 5, 3, 1, 10, 12, 7, 9,13,Dictionary Operations on Binary Search Trees,Searching straightforward Insertion search for key, insert at leaf where search

15、 terminated Deletion 3 cases: deleting key at a leaf deleting key at node with single child deleting key at node with two children 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) avera

16、ge case efficiency: (log n) Bonus: inorder traversal produces sorted list,14,Balanced Search Trees,Attractiveness of binary search tree is marred by the bad (linear) worst-case efficiency. Two ideas to overcome it are: to rebalance binary search tree when a new insertion makes the tree “too unbalanc

17、ed” 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,15,Balanced trees: AVL trees,Definition An AVL tree is a binary search tree in which, for every node, the difference between the heights of its left and right subtrees, called the balance

18、 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 tree,16,Rotations,If a key insertion violates the balance requirement at some node, the subtree rooted at that node is transformed via one of the four rotations. (The rotation is al

19、ways performed for a subtree rooted at an “unbalanced” node closest to the new leaf.),Single R-rotation,Double LR-rotation,17,General case: Single R-rotation,18,General case: Double LR-rotation,19,AVL tree construction - an example,Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7,20,AVL tree c

20、onstruction - an example (cont.),21,Analysis of AVL trees,h 1.4404 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 is more complicated but is also O(log n) Disadvantages: frequent rotations complexity A similar idea: r

21、ed-black trees (height of subtrees is allowed to differ by up to a factor of 2),22,Multiway Search Trees,Definition A multiway search tree is a search tree that allowsmore than one key in the same node of the tree. Definition A node of a search tree is called an n-node if it contains n-1 ordered key

22、s (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, k1,k1, k2 ), kn-1,23,2-3 Tree,Definition A 2-3 tree is a search tree that may have 2-nodes and 3-nodes height-balanced (a

23、ll 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 key promoted to the parent.,24,2-3 tree construction an example,Construct a 2-3 tree

24、the list 9, 5, 8, 3, 2, 4, 7,25,Analysis of 2-3 trees,log3 (n + 1) - 1 h log2 (n + 1) - 1 Search, 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-trees,26,Heaps and Heapsort,Definition A heap is a binary tree with keys at it

25、s 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 missing The key at each node is keys at its children,27,Illustration of the heaps definition,a heap,not a heap,not a heap,Note: Heaps

26、elements are ordered top down (along any path down from its root), but they are not ordered left to right,28,Some Important Properties of a Heap,Given n, there exists a unique binary tree with n nodes that is essentially complete, with h = log2 n The root contains the largest key The subtree rooted

27、at any node of a heap is also a heap A heap can be represented as an array,29,Heaps Array Representation,Store heaps elements in an array (whose elements indexed, for convenience, 1 to n) in top-down left-to-right order Example: Left child of node j is at 2j Right child of node j is at 2j+1 Parent o

28、f node j is at j/2 Parental nodes are represented in the first n/2 locations,9,1,5,3,4,2,30,Step 0: Initialize the structure with keys in the order given Step 1: Starting with the last (rightmost) parental node, fix the heap rooted at it, if it doesnt satisfy the heap condition: keep exchanging it w

29、ith its largest child until the heap condition holds Step 2: Repeat Step 1 for the preceding parental node,Heap Construction (bottom-up),31,Example of Heap Construction,Construct a heap for the list 2, 9, 7, 6, 5, 8,32,Pseudopodia of bottom-up heap construction,33,Stage 1: Construct a heap for a giv

30、en list of n keys Stage 2: Repeat operation of root removal n-1 times: Exchange keys in the root and in the last (rightmost) leaf Decrease heap size by 1 If necessary, swap new root with larger child until the heap condition holds,Heapsort,34,Sort the list 2, 9, 7, 6, 5, 8 by heapsort Stage 1 (heap

31、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 5 | 7 8 9 5 2 | 6 7 8 9 5 2 | 6 7 8 9 2 | 5 6 7 8 9,Example of Sorting by Heapsort,35,Stage 1: Build heap for a g

32、iven list of n keys worst-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: yesStability: no (e.g., 1 1),2(h-i) 2i = 2 ( n log2(n + 1) (n),i=0,h-1,# nodes at level i,i=1,n-1,2log2 i (nlogn),Anal

33、ysis of Heapsort,36,A priority queue is the ADT of a set of elements with numerical priorities with the following operations: find element with highest priority delete element with highest priority insert element with assigned priority (see below) Heap is a very efficient way for implementing priori

34、ty queues Two ways to handle priority queue in which highest priority = smallest number,Priority Queue,37,Insertion of a New Element into a Heap,Insert the new element at last position in heap. Compare it with its parent and, if it violates heap condition,exchange them Continue comparing the new ele

35、ment with nodes up the tree until the heap condition is satisfied Example: Insert key 10 Efficiency: O(log n),38,Horners Rule For Polynomial Evaluation,Given a polynomial of degree n p(x) = anxn + an-1xn-1 + + a1x + a0 and a specific value of x, find the value of p at that point. Two brute-force alg

36、orithms: p 0 p a0; power 1 for 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 * power return p,39,Horners Rule,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 -

37、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 as follows: coefficients2-1 3 1-5 x=3,40,Horners Rule pseudocode,Efficiency of Horners Rule: # multiplications = #

38、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),41,Computing an (revisited),Left-to-right binary exponentiation Initialize product 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