SIU srivteiy""* CARBONDALE Discrete Mathematics: Algorithms Mehrdad Nojoumian Department of Computer Science Southern Illinois University CS 215: Discrete Mathematics Mehrdad Nojoumian-— Section Summary Properties of Algorithms e Algorithms for Searching and Sorting e Linear Search e Binary Search ° Bubble Sort e Insertion Sort © Greedy Algorithms-— Algorithms Definition: an algorithm is a finite set of precise instructions for performing a computation or for solving a problem. Example: describe an algorithm for finding the maximum value in a finite sequence of integers. Solution: perform the following steps: s. Set atemporary maximum equal to the first integer in the sequence, 2, Compare the next integer in the sequence to the temporary maximum. * Ifitis larger than the temp max, set the temp max equal to this integer. 3. Repeat the previous step if there are more integers. If not, stop. When the algorithm terminates, the temporary maximum is the largest integer in the sequence.Specifying Algorithms e Algorithms can be specified in different ways. Their steps can be described in English or in pseudocode. e Pseudocode is an intermediate step between an English description of the steps and a coding of these steps using a programming language. ¢ Pseudocode uses some of the structures found in popular languages such as C++ and Java. ¢ Programmers usually use pseudocode to construct a program ina particular language. e Pseudocode helps us analyze the time required to solve a problem using an algorithm, independent of the programming language used to implement the algorithm._—— Properties of Algorithms Input: an algorithm has input values from a specified set. Output: from the input values, the algorithm produces the output values from a specified set. The output values are the solution. Correctness: an algorithm should produce the correct output values for each set of input values. Finiteness: an algorithm should produce the output after a finite number of steps for any input. Effectiveness: it must be possible to perform each step of the algorithm correctly and ina finite amount of time. Generality: the algorithm should work for all problems of the desired form.Finding the Max Element in a set © The algorithm in pseudocode: procedure max (4,, d,, ...., dy: integers) max := a, fori:=2ton if max < a; then max := a; return max © This algorithm returns the largest element in the set.- Some Example Algorithm Problems © Three classes of problems will be studied in this section. 1. Searching Problems: finding the position of a particular element ina list. 2. Sorting problems: putting the elements of a list into an increasing order. 3. Optimization Problems: determining the optimal value of a particular quantity over all possible inputs. e Optimal value means maximum or minimumnee -— Z Linear Search Algorithm © It locates an item ina list by examining elements in the list one at a time: ¢ First compare x with a,. If they are equal, return the position 1. ¢ Ifnot, try a,. If x =a,, return the position 2. ¢ Keep going, if no match is found when the entire list is scanned, return 0. procedure linear search (x: integer, a,, @,, ...,d,: distinct integers) return location [Link]Jae Binary Search ° Assume the input isa list of items in increasing order. e The algorithm begins by comparing the element to be found with the middle element. a) Ifthe middle element is lower, the search proceeds with the upper half of the list. b) If the middle element is not lower, the search proceeds with the lower half of the list. e Repeat this process until we have a list of size 1. ¢ If the procedure finds the element in the list, the position is returned. ¢ Otherwise, 0 is returned to indicate that the element was not found.‘Binary Search e Here is a description of the binary search algorithm in pseudocode: procedure binary search (x: integer, a,, a, i {iis the left endpoint of interval} {j is right endpoint of interval} , +) d,; increasing integers) J m:= |(i+j)/2] ifx>a,, then i:=m+1 if x = a, then location else location := 0 return location [Link]-— Binary Search Example: 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 1. The list has 16 elements, therefore the midpoint is 8. The value in the 8" position is 10. Since 19> 10, further search is restricted to positions 9 through 16. 123567 8 10 12 13 15 16 18 19 20 22 2. The midpoint of the list (positions 9 through 16) is now the 12" position with a value of 16. Since 19 > 16, further search is restricted to the 13" position and above. 1235678 10 12 13 15 16 18 19 20 22 3. The midpoint of the current list is now the 14" position with a value of 19. Since 19 + 19, further search is restricted to the portion from the 13" through the 14*" positions 1235678 10 12 13 15 16 18 19 20 22 4. The midpoint of the current list is now the 13" position with a value of 18. Since 19> 18, search is restricted to the portion from the 18" position through the 18". 123567810 12 13 15 16 18 19 20 22 5. Now the list has one element and the loop ends. Since 19=19, the location 16 is returned.Bubble Sort procedure bubblesort (a,,...,a,,: real numbers with n = 2) fori:=1ton-1 forj:=1ton—i if a; > a;,, then interchange a; and g,,, First pass 3 2 p 2 Second pass ¢2 2 ° 2 3 3 3 2 3 1 4 4 4 1 1 1 3 1 1 re 4 a & 5 5 5 5 3 5 5 Third pass ~2 1 Fourth pass ¢1 , ae @ PSG © sam imerchange 3 3 3 4 4 4) (pair in correct order 5. [5 O [Link]Insertion Sort « Insertion sort begins with the 2"¢ element. The algorithm then selects each element and put it in its proper position. procedure insertion sort (q,,...,a,: real numbers with n 2 2) 32415 a 23415 be 234.155 12445 Gs eao [Link]Greedy Algorithms © Optimization problems minimize or maximize some parameter over all possible inputs. For instance, we can refer to: ¢ Finding a route between two cities with the smallest total mileage. Finding the fiber links among nodes using the least amount of fiber. © Optimization problems can be solved using a greedy algorithm, which makes the “best” choice at each step. ¢ Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem, but in many instances, it does. © The greedy approach is an algorithmic paradigm, which isa general approach for designing an algorithm.Greedy Algorithms: Making Change Ramble: design a greedy algorithm for making change of n cents with the following coins: quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), using the least number of coins. Solution: at each step choose the coin with the largest possible value that does not exceed the amount of change left. For instance: 1. Ifn=67 cents, first choose a quarter leaving 67—25 = 42 cents. Then choose another quarter leaving 42 —25 = 17 cents. 2. Then choose a dime, leaving 17 — 10 = 7 cents. 3. Choose a nickel, leaving 7 - 5 = 2 cents. Choose a penny, leaving 1 cent. Choose another penny leaving 0 cents. In total, it requires 6 coins.es Greedy Change-Making Algorithm Solution: greedy change-making algorithm for n cents. The algorithm works with any coin denominations c, Cc, ...¢,. procedure change (c,, c,, ..., ¢,: values of coins, where C,> C,> ... > C,;M:a positive integer) for i:=1tor d:=0 while n >c;‘Proving Optimality for US Coins es Lemma 1: if n is a positive integer, n cents in change using quarters, dimes, nickels, and pennies, using the fewest coins possible has © at most 2 dimes (2x10c), 1 nickel (1x5c), 4 pennies (4x1c), © cannot have 2 dimes and a nickel (2x10c + 5¢), and © total amount of change in dimes, nickels, pennies must not exceed 24¢. Proof: by contradiction If we had 3 dimes, we could replace them with a quarter and a nickel. If we had 2 nickels, we could replace them with 1 dime. Ifwe had 5 pennies, we could replace them with a nickel (5c). Ifwe had 2 dimes and 1 nickel, we could replace them with a quarter. The allowable combinations, have a maximum value of 24 cents. Otherwise, we could replace them with a quarter.pe —— ie roving Optimality for US Coins Theorem: the greedy change-making algorithm for US coins produces change using the fewest coins possible. Proof: by contradiction. 1, Assume there is an optimal way and a positive integer n such that change can be made for n cents using quarters, dimes, nickels, and pennies, with a fewer total number of coins than the greedy algorithm. 2. Then, q' Sq where q’ is the number of quarters used in this optimal way and q is the number of quarters in the greedy algorithm, ie., less number of quarters in the optimal way. But this is not possible by Lemma 1 since the value of coins other than quarters can not be > 24c. 3. Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, and pennies.Greedy Change-Making Algorithm © Optimality depends on the denominations available. ¢ For US coins, optimality still holds if we add half dollar coins (50 cents) and dollar coins (100 cents). ¢ But if we allow only quarters (25 cents), dimes (10 cents), and pennies (1 cent) but not nickels (5 cent), the algorithm no longer produces the minimum number of coins. ¢ Consider 30 cents when we only have 25c, 10c, and 1c: © 30=254+1+1+1+1+1 (6coins!) e But we could use 30=10+10+10 (3 coins)‘Greedy Scheduling Example: we have a group of proposed talks with start and end times. Construct a prcedy algorithm to schedule as many as possible in a lecture hall, under the following assumptions: ¢ When a talk starts, it continues till the end. ¢ Two talks cannot occur at the same time. ¢ A talk can begin at the same time that another ends. e Once we have selected some of the talks, we cannot add a talk which is incompatible with those already selected. How should we make the “best choice” at each step of the algorithm? That is, which talk should we pick?° Picking the shortest talk doesn’t work: T, Start: 8:00 AM Talk 1 Bnd 945 AM End: 10:00. AM End: 11:00 AM But picking the one that ends soonest does work: T, , T,Greedy Scheduling algorithm Solution: at each step, choose the talks with the earliest ending time among the talks compatible with those selected. procedure schedule (s, < ... < s,: start times, e, < ... < e,: end times) sort talks by end times and reorder so that e, Se, S ... Se, S=0 for j:=1ton if talk j is compatible with S then S:=SU {talk j} return S