CSE 830: Design and Theory of AlgorithmsOverviewWhat is an Algorithm?Slide 4What is a problem?Types of ProblemsTwo desired properties of algorithmsExample: Odd or Even?Example: TSPExample CircuitNot Correct!A better algorithm?Still Not Correct!A Correct AlgorithmAreas of study of algorithmsHow to devise algorithmsExpressing AlgorithmsVerifying algorithm correctnessAnalyzing algorithmsThe RAM ModelMeasuring ComplexityBest, Worst, and Average CaseCase Study: Insertion SortCorrectness AnalysisExact AnalysisBest CaseWorst CaseAverage CaseAverage Case (Zoom Out)Slide 31Slide 32Best Case AnalysisAverage case analysisSlide 35Worst case analysisCSE 830:Design and Theory of AlgorithmsDr. Eric TorngOverview•Administrative stuff…•Lecture schedule overview •What is an algorithm? What is a problem?•How we study algorithms•Some examplesWhat is an Algorithm?According to the Academic American Encyclopedia:An algorithm is a procedure for solving a usually complicated problem by carrying out a precisely determined sequence of simpler, unambiguous steps. Such procedures were originally used in mathematical calculations (the name is a variant of algorism, which originally meant the Arabic numerals and then "arithmetic") but are now widely used in computer programs and in programmed learning.What is an Algorithm?Algorithms are the ideas behind computer programs. An algorithm is the thing that stays the same whether the program is in C++ running on a Cray in New York or is in BASIC running on a Macintosh in Katmandu! To be interesting, an algorithm has to solve a general, specified problem.What is a problem?•Definition–A mapping/relation between a set of input instances (domain) and an output set (range)•Problem Specification–Specify what a typical input instance is–Specify what the output should be in terms of the input instance•Example: Sorting–Input: A sequence of N numbers a1…an–Output: the permutation (reordering) of the input sequence such that a1  a2  …  an .Types of ProblemsSearch: find X in the input satisfying property YStructuring: Transform input X to satisfy property YConstruction: Build X satisfying YOptimization: Find the best X satisfying property YDecision: Does X satisfy Y?Adaptive: Maintain property Y over time.Two desired properties of algorithms•Correctness–Always provides correct output when presented with legal input•Efficiency–What does efficiency mean?Example: Odd or Even?What is the best way to determine if a number is odd or even? Some of the algorithms we can try are:• Count up to that number from one and alternate naming each number as odd or even.• Factor the number and see if there are any twos in the factorization.• Keep a lookup table of all numbers from 0 to the maximum integer.• Look at the last bit (or digit) of the number.Example: TSP•Input: A sequence of N cities with the distances dij between each pair of cities•Output: a permutation (ordering) of the cities <c1’, …, cn’> that minimizes the expression {j =1 to n-1} dj’,j’+1 + dn’,1’Example CircuitNot Correct!A better algorithm?What if we always connect the closest pair of points that do not result in a cycle or a three-way branch? We finish when we have a single chain.Still Not Correct!A Correct AlgorithmWe could try all possible orderings of the points, then select the ordering which minimizes the total length:d = For each of the n! permutations, Pi of the n points,if cost(Pi) < d thend = cost(Pi)Pmin = Pireturn PminAreas of study of algorithms1. How to devise correct and efficient algorithms for solving a given problem2. How to express algorithms3. How to validate/verify algorithms4. How to analyze algorithms5. How to prove (or at least indicate) no correct, efficient algorithm exists for solving a given problemHow to devise algorithms•Something of an art form•Cannot be fully automated•We will describe some general techniques and try to illustrate when each is appropriate•Major focus of courseExpressing Algorithms•Implementations•Pseudo-code•English•NOT our point of emphasis in this courseVerifying algorithm correctness•Proving an algorithm generates correct output for all inputs•One technique covered in textbook–Loop invariants•We will do some of this in the course, but it is not emphasized as much as algorithm design or algorithm analysisAnalyzing algorithms•The “process” of determining how much resources (time, space) are used by a given algorithm•We want to be able to make quantitative assessments about the value (goodness) of one algorithm compared to another•We want to do this WITHOUT implementing and running an executable version of an algorithm•Major point of emphasis of course–Question: How can we study the time complexity of an algorithm if we don’t run it or even choose a specific machine to measure it on?The RAM Model•Each "simple" operation (+, -, =, if, call) takes exactly 1 step.•Loops and subroutine calls are not simple operations, but depend upon the size of the data and the contents of a subroutine. We do not want “sort” to be a single step operation.•Each memory access takes exactly 1 step.Measuring Complexity•The worst case complexity of the algorithm is the function defined by the maximum number of steps taken on any instance of size n.•The best case complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n. •The average-case complexity of the algorithm is the function defined by an average number of steps taken on any instance of size n.Best, Worst, and Average CaseCase Study: Insertion SortOne way to sort an array of n elements is to start with an empty list, then successively insert new elements into their proper position, scanning from the “right end” back to the “left end”Loop invariant used to prove correctnessHow efficient is insertion sort?Correctness AnalysisWhat is the loop invariant? That is, what is true before each execution of the loop?for i = 2 to nkey = A[i]j = i - 1while j > 0 AND A[j] > keyA[j+1] = A[j] j = j -1A[j+1] = keyExact AnalysisCount the number of times each line will be executed:Num Exec.for i = 2 to n (n-1) + 1key = A[i] n-1j = i - 1 n-1while j > 0 AND A[j] > key ?A[j+1] = A[j] ?j = j -1 ?A[j+1] = key n-1Best CaseWorst CaseAverage CaseAverage Case (Zoom Out)1: for i = 2 to n2: key = A[i] 3: j = i - 14: while j > 0