View The "Writing Algorithms Applying Analysis And Deduction" Presentation Before Attempting This Assessment Activity!

The Efficiency of Algorithms Chapter 3 1 Learning Objectives Describe algorithm attributes and why they are important Explain the purpose of efficiency analysis and apply it to new algorithms to determine the order of magnitude of their time efficiencies Describe, illustrate, and use the algorithms from the chapter, including: sequential and binary search, selection sort, data cleanup algorithms, pattern-matching Explain which orders of magnitude grow faster or slower than others Describe what a “suspected intractable” problem is, giving one or more examples, and the purpose of approximation algorithms that partially solve them Introduction What makes one algorithm better than another? How can we judge and compare algorithms? Metaphor: purchasing a car vs. attributes of interest Ease of handling Style Fuel efficiency Ease of understanding Elegance Time/space efficiency Attributes of Algorithms (1 of 3) Correctness Is the problem specified correctly? Does the algorithm produce the correct result? Example: pattern matching Problem spec: “given pattern p and text t, determine the location, if any, of pattern p occurring in text t” Algorithm correct: does it always work? Attributes of Algorithms (2 of 3) Ease of understanding: Can somebody other than the author easily understand it? Examples: Checking correctness and program maintenance Elegance: using a clever or nonobvious approach Example: Gauss’s summing of 1 + 2 + … + 100 Attributes may conflict: elegance often conflicts with ease of understanding Attributes may reinforce each other: ease of understanding supports correctness Attributes of Algorithms (3 of 3) Efficiency: an algorithm’s use of time and space resources Timing an algorithm is not always useful Confounding factors: machine speed, size of input Benchmarking: timing an algorithm on standard data sets Testing hardware and operating system, etc. Testing real-world performance limits Measuring Efficiency Sequential Search (1 of 4) Analysis of algorithms: the study of the efficiency of algorithms Searching: the task of finding a specific value in a list of values, or deciding it is not there Sequential search algorithm (from Chapter 2) Given a target value and a random list of values, find the location of the target in the list, if it occurs, by checking each value in the list in turn Measuring Efficiency Sequential Search (2 of 4) Measuring Efficiency Sequential Search (3 of 4) Central unit of work, operations most important for the task, and occurring frequently In sequential search, comparison of the target NUMBER to each number in the list Given a big input list: Best case is smallest amount of work algorithm does Worst case is greatest amount of work algorithm does Average case depends on likelihood of different scenarios occurring Measuring Efficiency Sequential Search (4 of 4) Best case: target found with the first comparison Worst case: target never found or the last value Average case: if each value is equally likely to be searched, work done varies from 1 to n, averages to n/2 Figure 3.2 Best Case Worst Case Average Case 1 n n/2 Number of comparisons to find NUMBER in a list of n numbers using sequential search Measuring Efficiency Order of Magnitude—Order n (1 of 2) Order of magnitude n, Θ(n): the set of functions that grow in a linear fashion Measuring Efficiency Order of Magnitude—Order n (2 of 2) Change in growth as n increases is constant size Measuring Efficiency Selection Sort (1 of 5) Sorting: the task of putting a list of values into numeric or alphabetical order Key idea Pass repeatedly over the unsorted portion of the list Each pass, select the largest remaining value Move that value to the end of the unsorted values Measuring Efficiency Selection Sort (2 of 5) FIGURE 3.6 Get values for n and the n list items Set the maker for the unsorted section at the end of the list While the unsorted section of the list is not empty, do Steps, 4 through 6 Select the largest number in the unsorted section of the list Exchange this number with the last number in the unsorted section of the list Move the marker for the unsorted section left one position Stop Selection sort algorithm Measuring Efficiency Selection Sort (3 of 5) Example: Selection Sort on [5, 1, 3, 9, 4] Pass 1 Select 9 as the largest in the whole list Swap with 4 to place in the last slot [5, 1, 3, 4, 9] Pass 2 Select 5 as the largest in the first four values Swap with 4 to place in the last remaining slot [4, 1, 3, 5, 9] Measuring Efficiency Selection Sort (4 of 5) Example: Selection Sort on [5, 1, 3, 9, 4] Pass 3 Select 4 as the largest in the first three Swap with 3 to place in the last slot [3, 1, 4, 5, 9] Pass 4 Select 3 as the largest in the first two values Swap with 1 to place in last remaining slot [1, 3, 4, 5, 9] Measuring Efficiency Selection Sort (5 of 5) Central unit of work: hidden in “find largest” step Work done to find largest changes as unsorted portion shrinks (n - 1) + (n - 2) + … + 2 + 1 = n (n - 1) / 2 FIGURE 3.7 Length n of List to Sort n2 Number of Comparisons Required 10 100 45 100 10,000 4,950 1,000 1,000,000 499,500 Comparisons required by selection sort Measuring Efficiency Order of Magnitude—Order n2 (1 of 3) Order of magnitude n2, Θ(n2): the set of functions whose growth is on the order of n2 Measuring Efficiency Order of Magnitude—Order n2 (2 of 3) Eventually, every function with order n2 has greater values than any function with order n. Measuring Efficiency Order of Magnitude—Order n2 (3 of 3) FIGURE 3.13 Number of Work Units Required: Number of Work Units Required: Algorithm A Algorithm B n 0.0001 n2 100n 1,000 100 100,000 10,000 10,000 1,000,000 100,000 1,000,000 10,000,000 1,000,000 100,000,000 100,000,000 10,000,000 10,000,000,000 1,000,000,000 A comparison of two extreme Θ(n2) and Θ(n) algorithms Analysis of Algorithms Data Cleanup Algorithms (1 of 12) “Given a collection of age data, where erroneous zeros occur, find and remove all the zeros from the data, reporting the number of legitimate age values that remain” Illustrates multiple solutions to a single problem Use of analysis to compare algorithms Analysis of Algorithms Data Cleanup Algorithms (2 of 12) Shuffle-left algorithm Search for zeros from left to right When a zero is found, shift all values to its right one cell to the left Example: [55, 0, 32, 19, 0, 27] Finds 0 at position 2: [55, 32, 19, 0, 27, 27] Finds 0 at position 4: [55, 32, 19, 27, 27, 27] Analysis of Algorithms Data Cleanup Algorithms (3 of 12) Analysis of Algorithms Data Cleanup Algorithms (4 of 12) Analysis of shuffle-left for time efficiency Count comparisons looking for zero AND movements of values Best case: no zero value, check each value and nothing more: Θ(n) Worst case: every value is a zero, move n - 1 values, then n - 2 values, etc.: Θ(n2) Analysis of shuffle-left for space efficiency Uses no significant space beyond input Analysis of Algorithms Data Cleanup Algorithms (5 of 12) Copy-over algorithm Create a second, initially empty, list Look at each value in the original If it is nonzero, copy it to the second list Example: [55, 0, 32, 19, 0, 27] answer = [55] answer = [55] answer = [55, 32] answer = [55, 32, 19] answer = [55, 32, 19] answer = [55, 32, 19, 27] Analysis of Algorithms Data Cleanup Algorithms (6 of 12) Analysis of Algorithms Data Cleanup Algorithms (7 of 12) Time efficiency for copy-over Best case: all zeros, checks each value but doesn’t copy it: Θ(n) Worst case: no zeros, checks each value and copies it: Θ(n) Space efficiency for copy-over Best case: all zeros, uses no extra space Worst case: no zeros, uses n extra spaces Analysis of Algorithms Data Cleanup Algorithms (8 of 12) Converging-pointers algorithm Keep track of two pointers at the data Left pointer moves left to right and stops when it sees a zero value Right pointer stays put until a zero is found Then its value is copied on top of the zero, and it moves one cell to the left Stop when the left crosses the right Analysis of Algorithms Data Cleanup Algorithms (9 of 12) Analysis of Algorithms Data Cleanup Algorithms (10 of 12) Analysis of Algorithms Data Cleanup Algorithms (11 of 12) Time efficiency for converging-pointers Best case: no zeros, left pointer just moves across to pass the right pointers, examines each value: Θ(n) Worst case: all zeros, examines each value and copies a value over it, right pointer moves left towards left pointer: Θ(n) Space efficiency for converging-pointers No significant extra space needed Analysis of Algorithms Data Cleanup Algorithms (12 of 12) FIGURE 3.17 1. Shuffle-left: 1. Shuffle-left: 2. Copy-over: 2. Copy-over: 3.Converging-pointers: 3.Converging-pointers: Time Space Time Space Time Space Best case Θ(n) n Θ(n) n Θ(n) n Worst case Θ(n2) n Θ(n) 2n Θ(n) n Average case Θ(n2) n Θ(n) n ≤ x ≤ 2n Θ(n) n Analysis of three data cleanup algorithms Analysis of Algorithms Binary Search (1 of 5) Binary Search Algorithm Requires the list to be ordered values. Will find the location of the target in the list, if it occurs, by starting in the middle and splitting the range in two with each comparison Analysis of Algorithms Binary Search (2 of 5) Analysis of Algorithms Binary Search (3 of 5) Analysis of Algorithms Binary Search (4 of 5) Central unit of work: comparisons against target Best case efficiency Value is the first middle value: 1 comparison Worst case efficiency Value does not appear, repeats as many times as we can divide the list before running out of values: Θ(lg n) Analysis of Algorithms Binary Search (5 of 5) Order of magnitude lg n, Θ(lg n), grows very slowly Analysis of Algorithms Pattern Matching (1 of 4) Algorithm from Chapter 2: Finding a pattern in a text document Best case: when first symbol of pattern does not appear in text Worst case: when all but last symbol of pattern make up the text Analysis of Algorithms Pattern Matching (2 of 4) Analysis of Algorithms Pattern Matching (3 of 4) Best case example Pattern = “xyz” text = “aaaaaaaaaaaaaaa” At each step, compare x to a and then move on Θ(n) comparisons Worst case example Pattern = “aab” text = “aaaaaaaaaaaaaaa” At each step, compare m symbols from pattern against text before moving on Θ(m × n) comparisons Analysis of Algorithms Pattern Matching (4 of 4) FIGURE 3.22 Problem Unit of Work Algorithm Best Case Worst Case Average Case Searching Comparisons Sequential search 1 Θ(n) Θ(n) Searching Comparisons Binary search 1 Θ(Ig n) Θ(Ig n) Sorting Comparisons and exchanges Selection sort Θ(n2) Data cleanup Examinations and copies Shuffle-left Θ(n) Θ(n2) Θ(n2) Data cleanup Examinations and copies Copy-over Θ(n) Θ(n2) Θ(n2) Data cleanup Examinations and copies Converging-pointers Θ(n) Θ(n) Θ(n) Pattern matching Character comparisons Forward march Θ(n) Θ(m × n) Order-of-magnitude time efficiency summary When Things Get Out of Hand (1 of 8) Polynomially bounded: an algorithm that does work on the order of Θ(nk) Most common problems are polynomially bounded Hamiltonian circuit is NOT Given a graph, find a path that passes through each vertex exactly once and returns to its starting point When Things Get Out of Hand (2 of 8) When Things Get Out of Hand (3 of 8) Possible paths in the graph are paths through a tree of choices Simplest case has exactly two choices per vertex Number of paths to examine = number of leaves in the tree Height of the tree = n + 1 (n is the number of vertices in the graph) Number of leaves = 2n When Things Get Out of Hand (4 of 8) Exponential algorithm: an algorithm whose order of growth is Θ(2n) Intractable: problems with no polynomially bounded solutions Hamiltonian circuit Traveling salesperson Bin packing Chess When Things Get Out of Hand (5 of 8) When Things Get Out of Hand (6 of 8) FIGURE 3.27 Order 10 50 n 100 1,000 Ig n 0.0003 sec 0.0006 sec 0.0007 sec 0.001 sec n 0.001 sec 0.005 sec 0.01 sec 0.1 sec n2 0.01 sec 0.25 sec 1 sec 1.67 min 2n 0.1024 sec 3,570 years 4 × 1016 centuries Too big to compute!! A comparison of four orders of magnitude When Things Get Out of Hand (7 of 8) When Things Get Out of Hand (8 of 8) Approximation algorithms: algorithms that partially solve, or provide suboptimal solutions to, intractable problems Example: bin packing For each box to be packed: Check each current bin If new box fits in the bin, place it there If no bin can hold the new box, add a new bin Summary We must evaluate the quality of algorithms and compare competing algorithms to each other Attributes: correctness, efficiency, elegance, and ease of understanding Compare competing algorithms for time and space efficiency (time/space tradeoffs are common) Orders of magnitude capture work as a function of input size: Θ(lg n), Θ(n), Θ(n2), and Θ(2n) Problems with only exponential algorithms are intractable