CSE115/ENGR160 Discrete Mathematics 03/03/113.1 AlgorithmsAlgorithmExamplePseudo codeProsperities of algorithmSearching algorithmsLinear SearchBinary searchSlide 10Slide 11SortingBubble sortInsertion sortSlide 15Slide 16Greedy algorithmSlide 18Greedy change-making algorithmSlide 20Lemma 1Proof (Lemma)TheoremProofSlide 25The halting problemSlide 27Slide 28Turing’s proofSlide 30Slide 31Slide 32CSE115/ENGR160 Discrete Mathematics03/03/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 order}13Insertion sort•Start with 2nd term–Larger than 1st term, insert after 1st term–Smaller than 1st term, insert before 1st term•At this moment, first 2 terms in the list are in correct positions•For 3rd term–Compare with all the elements in the list–Find the first element in the list that is not less than this element• For j-th term–Compare with the elements in the list–Find the first element in the list that is not less than this element14Example•Apply insertion sort to 3, 2, 4, 1, 5•First compare 3 and 2  2, 3, 4, 1, 5•Next, insert 3rd item, 4>2, 4>3  2, 3, 4, 1, 5•Next, insert 4th item, 1<2  1, 2, 3, 4, 5•Next, insert 5th item, 5>1, 5>2, 5>3, 5>41, 2, 3, 4, 515Insertion sortprocedure insertion sort(a1, a2, …, an: real numbers with n≥2) i:=1 (left endpoint of search interval) j:=1 (right end point of search interval) for j:=2 to n begin i:=1 while aj>ai i:=i+1 m:=aj for k:=0 to j-i-1 aj-k:= aj-k-1 ai:= m end {a1 , a2, …, an are sorted}16Greedy algorithm•Many algorithms are designed to solve optimization problems•Greedy algorithm: –Simple and naïve–Select the best choice at each step, instead of considering all sequences of steps–Once find a feasible solution–Either prove the solution is optimal or show a counterexample that the solution is non-optimal 17Example•Given n centers change with quarters, dimes, nickels and pennies, and use the least total number of coins•Say, 67 cents•Greedy algorithm–First select a quarter (leaving 42 cents)–Second select a quarter (leaving 17 cents)–Select a dime (leaving 7 cents)–Select a nickel (leaving 2cnts)–Select a penny (leaving 1 cent)–Select a penny 18Greedy change-making algorithmprocedure change(c1, c2, …, cn: values of denominations of coins, where c1>c2>…>cn; n: positive integer)for i:=1 to r while n≥ci then add a coin with value ci to the change n:=n- ci end19Example•Change of 30 cents•If we use only quarters, dimes, and pennies (no nickels)•Using greedy algorithm:–6 coins: 1 quarter, 5 pennies –Could use only 3 coins (3 dimes)20Lemma 1•If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies using the fewest coins possible has at most two dimes, at most one nickel, at most 4 pennies, and cannot have two dimes and a nickel•The amount of change in dimes, nickels, and pennies cannot exceed 24 cents