Algorithms Analysis and Design Chapter 6 Transform and Conquer PDF

Algorithms Analysis and Design Chapter 6: Transform and Conquer A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved....

Algorithms Analysis and Design Chapter 6: Transform and Conquer A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 3 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 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 available (problem reduction) A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 2 Instance simplification - Presorting Solve a problem’s 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)  checking if all elements are distinct (element uniqueness) Also:  Topological sorting helps solving some problems for dags.  Presorting is used in many geometric algorithms. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 3  Examples of Decrease-and- Conquer Algorithms Decrease by one: – Insertion sort – Graph search algorithms: – DFS – BFS – Topological sorting – Algorithms for generating permutations, subsets 4 Searching with presorting Problem: Search for a given K in A[0..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 directories, etc. sorted? A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 5 Element Uniqueness with presorting  Presorting-based algorithm Stage 1: sort by efficient 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 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 6 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): find (search) insert delete A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 7 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 (separate chaining) closed hashing (open addressing) A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 8 Binary Search Tree Arrange keys in a binary tree with the binary search tree property: K K A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 9  Keys: 30,40, 10, 50, 20, 5, 35  Keys : 50,40,35,30,20,10,5 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 10  Dictionary Operations on Binary Search Trees Searching – straightforward Insertion – search for key, insert at leaf where search 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 tree’s 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 list A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 11 Deletion A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 12 Deletion A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 13 Balanced Search Trees Attractiveness of binary search tree is marred by the bad (linear) worst-case efficiency. Two ideas to overcome it are:  Rebalance binary search tree when a new insertion makes the tree “too unbalanced” (instance-simplification) AVL trees Red-black trees  Allow more than one key per node of a search tree (representation-change) 2-3 trees 2-3-4 trees B-trees A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 14 Balanced trees: AVL trees Definition An AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. 1 2 10 10 0 1 0 0 5 20 5 20 1 -1 0 1 -1 4 7 12 4 7 0 0 0 0 2 8 2 8 (a) (b) Tree (a) is an AVL tree; tree (b) is not an AVL tree 1962, by two Russian scientists, G. M. Adelson-Velsky and E. M. Landis 15 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 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 always performed for a subtree rooted at an “unbalanced” node closest to the new leaf.) Single R-rotation Single L-rotation A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 17 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 always performed for a subtree rooted at an “unbalanced” node closest to the new leaf.) Double LR-rotation Double RL-rotation A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 18 General case: Single R-rotation General form of the R-rotation in the AVL tree. A shaded node is the last one inserted. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 19 General case: Double LR-rotation General form of the double LR-rotation. This rotation is performed after a new key is inserted into the right subtree of the left child of a tree whose root had the balance of +1 before the insertion. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 20 AVL tree construction - an example Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7 0 -1 -2 0 L(5) 5 5 5 6 0 -1 > 0 0 6 6 5 8 0 8 1 2 1 6 6 6 1 0 2 0 R (5) 0 0 5 8 5 8 > 3 8 0 1 0 0 3 3 2 5 0 2 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 21 AVL tree construction - an example (cont.) Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7 2 0 6 5 -1 0 LR (6) 0 -1 3 8 > 3 6 0 1 0 0 0 2 5 2 4 8 0 4 -1 0 5 5 0 -2 0 0 3 6 3 7 RL (6) 0 0 1 > 0 0 0 0 2 4 8 2 4 6 8 0 7 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 22 Multiway Search Trees Definition A multiway search tree is a search tree that allows more 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 keys (which divide the entire key range into n intervals pointed to by the node’s n links to its children): k1 < k2 < … < kn-1 < k1 [k1, k2 )  kn-1 Note: Every node in a classical binary search tree is a 2-node A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 23 2-3 Tree Definition 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) 2-node 3-node K K1, K 2 K < K1 (K1 , K 2 ) > K2 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, it’s split into two with the middle key promoted to the parent. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 24 2-3 tree construction – an example Construct a 2-3 tree the list 9, 5, 8, 3, 2, 4, 7 8 8 > 9 5, 9 5, 8, 9 5 9 3, 5 9 8 3, 8 3, 8 > 2, 3, 5 9 2 5 9 2 4, 5 9 5 3, 8 > 3, 5, 8 > 3 8 2 4, 5, 7 9 2 4 7 9 2 4 7 9 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 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 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 26 Heaps and Heapsort Definition 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 missing  The key at each node is ≥ keys at its children A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 27 Illustration of the heap’s definition 10 10 10 5 7 5 7 5 7 4 2 1 2 1 6 2 1 a heap not a heap not a heap Note: Heap’s elements are ordered top down (along any path down from its root), but they are not ordered left to right A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 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 at any node of a heap is also a heap  A heap can be represented as an array A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 29 Heap’s Array Representation Store heap’s elements in an array (whose elements indexed, for convenience, 1 to n) in top-down left-to-right order Example: 9 1 2 3 4 5 6 5 3 9 5 3 1 4 2 1 4 2  Left child of node j is at 2j  Right child of node j is at 2j+1  Parent of node j is at j/2  Parental nodes are represented in the first n/2 locations A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 30 Heap Construction (bottom-up) 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 doesn’t satisfy the heap condition: keep exchanging it with its largest child until the heap condition holds Step 2: Repeat Step 1 for the preceding parental node A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 31  Example of Heap Construction Construct a heap for the list 2, 9, 7, 6, 5, 8 2 2 2 9 7 > 9 8 9 8 6 5 8 6 5 7 6 5 7 2 9 9 9 8 > 2 8 > 6 8 6 5 7 6 5 7 2 5 7 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 32 Heapsort Stage 1: Construct a heap for a given 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 A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 33 Priority Queue 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 priority queues  Two ways to handle priority queue in which highest priority = smallest number A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 34 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 element with nodes up the tree until the heap condition is satisfied Example: Insert key 10 9 9 10 6 8 > 6 10 > 6 9 2 5 7 10 2 5 7 8 2 5 7 8 Efficiency: O(log n) A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 6 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. 35