CSE115/ENGR160 Discrete Mathematics 02/24/113.1 AlgorithmsAlgorithmExamplePseudo codeProsperities of algorithmSearching algorithmsLinear SearchBinary searchSlide 10Slide 11SortingBubble sortCSE115/ENGR160 Discrete Mathematics02/24/11Ming-Hsuan YangUC Merced13.1 Algorithms•When presented a problem, e.g., given a sequence of integers, find the larges one•Construct a model that translates the problem into a mathematical context–Discrete structures in such models include sets, sequences, functions, graphs, relations, etc.•A method is needed that will solve the problem (using a sequence of steps)•Algorithm: a sequence of steps2Algorithm•Algorithm: a finite set of precise instructions for performing a computation or for solving a problem•Example: describe an algorithm for finding the maximum (largest) value in a finite sequence of integers3Example•Perform the following steps–Set up temporary maximum equal to the first integer in the sequence–Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the temporary maximum equal to this–Repeat the previous step if there are more integers in the sequence–Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.4Pseudo code•Provide an intermediate step between English and real implementation using a particular programming language procedure max(a1, a2, …, an: integers) max := a1 for i:=2 to n if max < ai then max:=ai {max is the largest element}5Prosperities of algorithm•Input: input values from a specified set•Output: for each set of input values, an algorithm produces output value from a specified set•Definiteness: steps must be defined precisely•Correctness: should produce the correct output values for each set of input values•Finiteness: should produce the desired output after a finite number of steps•Effectiveness: must be possible to perform each step exactly and in a finite amount of time•Generality: applicable for all problems of the desired form, not just a particular set of input values6Searching algorithms•Locate an element x in a list of distinct elements, a1, a2, …, an, or determine it is not in the list •Solution is the location of the term in the list that equals x, and is 0 if x is not in the list7Linear Search procedure linear search(x:integer, a1, a2, …, an: distinct integers) i := 1 while (i≤n and x≠ai) i:=i+1 if i < n then location:=n else location:=0 {location is the index of the term equal to x, or is 0 if x is not found}8Binary search•By comparing the element to be located to the middle term of the list•The list is split into two smaller sublists (of equal size or one has one fewer term)•Continue by restricting the search to the appropriate sublist•Search for 19 in the list 1 2 3 5 67 8 10 12 13 15 16 18 19 20 229Binary search•First split the list 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22•Then compare 19 and the largest term in the first list, and determine to use the list•Continue 12 13 15 16 18 19 20 22 18 19 20 22 19 (down to one term)10Binary searchprocedure binary search(x:integer, a1, a2, …, an: increasing integers) i:=1 (left endpoint of search interval) j:=1 (right end point of search interval) while (i<j) begin m:=⌞(i+j)/2⌟ if x>am then i:=m+1 else j:=m end if x=ai then location:=i else location:=0 {location is the index of the term equal to x, or is 0 if x is not found}11SortingBubble sort: First pass guarantees the largest element is in correct position12Bubble sortprocedure bubble sort(a1, a2, …, an: real numbers with n≥2)for i:=1 to n-1 for j:=1 to n-i if aj>aj+1 then interchange aj and aj+1 {a1, a2, …, an is in increasing