Discrete Structures 2: Algorithms (PDF)

Republic of the Philippines City of Olongapo GORDON COLLEGE Olongapo City Sports Complex, East Tapinac, Olongapo City Tel. No. (047) 224-2089 loc. 314...

Republic of the Philippines City of Olongapo GORDON COLLEGE Olongapo City Sports Complex, East Tapinac, Olongapo City Tel. No. (047) 224-2089 loc. 314 www.gordoncollege.edu.ph DISCRETE STRUCTURES 2 Title: ALGORITHMS Module No. 4 I. INTRODUCTION Many problems can be solved by considering them as special cases of general problems. For instance, consider the problem of locating the largest integer in the sequence 101, 12, 144, 212, 98. This is a specific case of the problem of locating the largest integer in a sequence of integers. To solve this general problem we must give an algorithm, which specifies a sequence of steps used to solve this general problem. We will study algorithms for solving many different types of problems. For example, in this module we will introduce algorithms for two of the most important problems in computer science, searching for an element in a list and sorting a list so its elements are in some prescribed order, such as increasing, decreasing, or alphabetic. II. LEARNING OBJECTIVES After studying this module, you should be able to:  Recall what an algorithm is and how it is used to solve problems in discrete structures;  Determine the different properties that algorithms generally share;  Devise an algorithm that would give solutions to a certain type of problem. III. TOPICS AND KEY CONCEPT A. WHAT IS AN ALGORITHM? There are many general classes of problems that arise in discrete mathematics. For instance: given a sequence of integers, find the largest one; given a set, list all its subsets; given a set of integers, put them in increasing order; given a network, find the shortest path between two vertices. When presented with such a problem, the first thing to do is to construct a model that translates the problem into a mathematical context. Discrete structures used in such models include sets, sequences, and functions as well as such other structures as permutations, relations, graphs, trees, networks, and finite state machines. Setting up the appropriate mathematical model is only part of the solution. To complete the solution, a method is needed that will solve the general problem using the model. Ideally, what is required is a procedure that follows a sequence of steps that leads to the desired answer. Such a sequence of steps is called an algorithm. DEFINITION 1 An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem. The term algorithm is a corruption of the name al-Khowarizmi, a mathematician of the ninth century, whose book on Hindu numerals is the basis of modern decimal notation. Originally, the word algorism was used for the rules for performing Prepared by: Mr. Kenneth V. Bautista 1 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 arithmetic using decimal notation. Algorism evolved into the word algorithm by the eighteenth century. With the growing interest in computing machines, the concept of an algorithm was given a more general meaning, to include all definite procedures for solving problems, not just the procedures for performing arithmetic. ABU JA‘FAR MOHAMMED IBN MUSA AL-KHOWARIZMI (C. 780 – C. 850) al-Khowarizmi wrote books on mathematics, astronomy, and geography. Western Europeans first learned about algebra from his works. The word algebra comes from al-jabr, part of the title of his book Kitab al-jabr w’al muquabala. European authors used a Latin corruption of his name, which later evolved to the word algorithm, to describe the subject of arithmetic with Hindu numerals. EXAMPLE 1 Describe an algorithm for finding the maximum (largest) value in a finite sequence of integers. Even though the problem of finding the maximum element in a sequence is relatively trivial, it provides a good illustration of the concept of an algorithm. Also, there are many instances where the largest integer in a finite sequence of integers is required. For instance, a university may need to find the highest score on a competitive exam taken by thousands of students. Or a sports organization may want to identify the member with the highest rating each month. We want to develop an algorithm that can be used whenever the problem of finding the largest element in a finite sequence of integers arises. We can specify a procedure for solving this problem in several ways. One method is simply to use the English language to describe the sequence of steps used. We now provide such a solution. Solution: We perform the following steps. 1. Set the temporary maximum equal to the first integer in the sequence. (The temporary maximum will be the largest integer examined at any stage of the procedure.) 2. 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 integer. 3. Repeat the previous step if there are more integers in the sequence. 4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence. An algorithm can also be described using a computer language. However, when that is done, only those instructions permitted in the language can be used. This often leads to a description of the algorithm that is complicated and difficult to understand. Furthermore, because many programming languages are in common use, it would be undesirable to choose one particular language. So, instead of using a particular computer language to specify algorithms, a form of pseudocode will be used. (We will also describe algorithms using the English language.) Pseudocode provides an intermediate step between an English language description of an algorithm and an implementation of this algorithm in a programming language. The steps of the Prepared by: Mr. Kenneth V. Bautista 2 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 algorithm are specified using instructions resembling those used in programming languages. However, in pseudocode, the instructions used can include any well- defined operations or statements. A computer program can be produced in any computer language using the pseudocode description as a starting point. The pseudocode used in this module is designed to be easily understood. It can serve as an intermediate step in the construction of programs implementing algorithms in one of a variety of different programming languages. Although this pseudocode does not follow the syntax of Java, C, C++, or any other programming language, students familiar with a modern programming language will find it easy to follow. A key difference between this pseudocode and code in a programming language is that we can use any well-defined instruction even if it would take many lines of code to implement this instruction. A pseudocode description of the algorithm for finding the maximum element in a finite sequence follows. ALGORITHM 1 Finding the Maximum Element in a Finite Sequence. procedure max(a1, a2,...,an: integers) max := a1 for i := 2 to n if max < ai then max := ai return max{max is the largest element} This algorithm first assigns the initial term of the sequence, a1, to the variable max. The “for” loop is used to successively examine terms of the sequence. If a term is greater than the current value of max, it is assigned to be the new value of max. PROPERTIES OF ALGORITHMS There are several properties that algorithms generally share. They are useful to keep in mind when algorithms are described. These properties are: a. Input. An algorithm has input values from a specified set. b. Output. From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem. c. Definiteness. The steps of an algorithm must be defined precisely. d. Correctness. An algorithm should produce the correct output values for each set of input values. e. Finiteness. An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set. f. Effectiveness. It must be possible to perform each step of an algorithm exactly and in a finite amount of time. g. Generality. The procedure should be applicable for all problems of the desired form, not just for a particular set of input values. EXAMPLE 2 Show that Algorithm 1 for finding the maximum element in a finite sequence of integers has all the properties listed. Prepared by: Mr. Kenneth V. Bautista 3 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 Solution: The input to Algorithm 1 is a sequence of integers. The output is the largest integer in the sequence. Each step of the algorithm is precisely defined, because only assignments, a finite loop, and conditional statements occur. To show that the algorithm is correct, we must show that when the algorithm terminates, the value of the variable max equals the maximum of the terms of the sequence. To see this, note that the initial value of max is the first term of the sequence; as successive terms of the sequence are examined, max is updated to the value of a term if the term exceeds the maximum of the terms previously examined. This (informal) argument shows that when all the terms have been examined, max equals the value of the largest term. The algorithm uses a finite number of steps, because it terminates after all the integers in the sequence have been examined. The algorithm can be carried out in a finite amount of time because each step is either a comparison or an assignment, there are a finite number of these steps, and each of these two operations takes a finite amount of time. Finally, Algorithm 1 is general, because it can be used to find the maximum of any finite sequence of integers. B. SEARCHING ALGORITHMS The problem of locating an element in an ordered list occurs in many contexts. For instance, a program that checks the spelling of words searches for them in a dictionary, which is just an ordered list of words. Problems of this kind are called searching problems. The general searching problem can be described as follows: Locate an element x in a list of distinct elements a1, a2,...,an, or determine that it is not in the list. The solution to this search problem is the location of the term in the list that equals x (that is, i is the solution if x = ai) and is 0 if x is not in the list. THE LINEAR SEARCH The first algorithm that we will present is called the linear search, or sequential search, algorithm. The linear search algorithm begins by comparing x and a1. When x = a1, the solution is the location of a1, namely, 1. When x ≠ a1, compare x with a2. If x = a2, the solution is the location of a2, namely, 2. When x ≠ a2, compare x with a3. Continue this process, comparing x successively with each term of the list until a match is found, where the solution is the location of that term, unless no match occurs. If the entire list has been searched without locating x, the solution is 0. The pseudocode for the linear search algorithm is displayed as Algorithm 2. ALGORITHM 2 The Linear Search Algorithm. 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 := i else location := 0 return location{location is the subscript of the term that equals x, or is 0 if x is not found} Prepared by: Mr. Kenneth V. Bautista 4 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 THE BINARY SEARCH We will now consider another searching algorithm. This algorithm can be used when the list has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). This second searching algorithm is called the binary search algorithm. It proceeds by comparing the element to be located to the middle term of the list. The list is then split into two smaller sublists of the same size, or where one of these smaller lists has one fewer term than the other. The search continues by restricting the search to the appropriate sublist based on the comparison of the element to be located and the middle term. Example 3 demonstrates how a binary search works. EXAMPLE 3 To search for 19 in the list 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22, first split this list, which has 16 terms, into two smaller lists with eight terms each, namely, 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. Because 10 < 19, the search for 19 can be restricted to the list containing the 9th through the 16th terms of the original list. Next, split this list, which has eight terms, into the two smaller lists of four terms each, namely, 12 13 15 16 18 19 20 22. Because 16 < 19 (comparing 19 with the largest term of the first list) the search is restricted to the second of these lists, which contains the 13th through the 16th terms of the original list. The list 18 19 20 22 is split into two lists, namely, 18 19 20 22. Because 19 is not greater than the largest term of the first of these two lists, which is also 19, the search is restricted to the first list: 18 19, which contains the 13th and 14th terms of the original list. Next, this list of two terms is split into two lists of one term each: 18 and 19. Because 18 < 19, the search is restricted to the second list: the list containing the 14th term of the list, which is 19. Now that the search has been narrowed down to one term, a comparison is made, and 19 is located as the 14th term in the original list. We now specify the steps of the binary search algorithm. To search for the integer x in the list a1, a2,...,an, where a1 < a2 < ··· < an, begin by comparing x with the middle term am of the list, where m = ⌊(n + 1)/2⌋. (Recall that ⌊x⌋ is the greatest integer not exceeding x.) If x>am, the search for x is restricted to the second half of the list, which is am+1, am+2,...,an. If x is not greater than am, the search for x is restricted to the first half of the list, which is a1, a2,...,am. Prepared by: Mr. Kenneth V. Bautista 5 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 The search has now been restricted to a list with no more than ⌈n/2⌉ elements. (Recall that ⌈x⌉ is the smallest integer greater than or equal to x.) Using the same procedure, compare x to the middle term of the restricted list. Then restrict the search to the first or second half of the list. Repeat this process until a list with one term is obtained. Then determine whether this term is x. Pseudocode for the binary search algorithm is displayed as Algorithm 3. ALGORITHM 3 The Binary Search Algorithm. procedure binary search(x: integer, a1, a2,...,an: increasing integers) i := 1{i is left endpoint of search interval} j := n {j is right endpoint of search interval} while i < j m := ⌊(i + j )/2⌋ if x>am then i := m + 1 else j := m if x  ai then location := i else location := 0 return location{location is the subscript i of the term ai that equals x, or is 0 if x is not found} Algorithm 3 proceeds by successively narrowing down the part of the sequence being searched. At any given stage only the terms from ai to aj are under consideration. In other words, i and j are the smallest and largest subscripts of the remaining terms, respectively. Algorithm 3 continues narrowing the part of the sequence being searched until only one term of the sequence remains. When this is done, a comparison is made to see whether this term equals x. C. SORTING Ordering the elements of a list is a problem that occurs in many contexts. For example, to produce a telephone directory it is necessary to alphabetize the names of subscribers. Similarly, producing a directory of songs available for downloading requires that their titles be put in alphabetic order. Putting addresses in order in an e-mail mailing list can determine whether there are duplicated addresses. Creating a useful dictionary requires that words be put in alphabetical order. Similarly, generating a parts list requires that we order them according to increasing part number. Suppose that we have a list of elements of a set. Furthermore, suppose that we have a way to order elements of the set. Sorting is putting these elements into a list in which the elements are in increasing order. For instance, sorting the list 7, 2, 1, 4, 5, 9 produces the list 1, 2, 4, 5, 7, 9. Sorting the list d, h, c, a, f (using alphabetical order) produces the list a, c, d, f, h. An amazingly large percentage of computing resources is devoted to sorting one thing or another. Hence, much effort has been devoted to the development of sorting algorithms. A surprisingly large number of sorting algorithms have been devised using distinct strategies, with new ones introduced regularly. In his fundamental work, The Art of Computer Programming, Donald Knuth devotes close to 400 pages Prepared by: Mr. Kenneth V. Bautista 6 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 to sorting, covering around 15 different sorting algorithms in depth! More than 100 sorting algorithms have been devised, and it is surprising how often new sorting algorithms are developed. Among the newest sorting algorithms that have caught on is the library sort, also known as the gapped insertion sort, invented as recently as 2006. There are many reasons why sorting algorithms interest computer scientists and mathematicians. Among these reasons are that some algorithms are easier to implement, some algorithms are more efficient (either in general, or when given input with certain characteristics, such as lists slightly out of order), some algorithms take advantage of particular computer architectures, and some algorithms are particularly clever. In this section we will introduce two sorting algorithms, the bubble sort and the insertion sort. We cover sorting algorithms both because sorting is an important problem and because these can serve as examples for many important concepts. THE BUBBLE SORT The bubble sort is one of the simplest sorting algorithms, but not one of the most efficient. It puts a list into increasing order by successively comparing adjacent elements, interchanging them if they are in the wrong order. To carry out the bubble sort, we perform the basic operation, that is, interchanging a larger element with a smaller one following it, starting at the beginning of the list, for a full pass. We iterate this procedure until the sort is complete. Pseudocode for the bubble sort is given as Algorithm 4. We can imagine the elements in the list placed in a column. In the bubble sort, the smaller elements “bubble” to the top as they are interchanged with larger elements. The larger elements “sink” to the bottom. This is illustrated in Example 4. EXAMPLE 4 Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order. First pass 3 2 2 2 Second pass 2 2 2 2 3 3 3 3 3 1 4 4 4 1 1 1 3 1 1 1 4 4 4 4 5 5 5 5 5 5 5 Third pass 2 1 Fourth pass 1 1 2 2 3 3 3 : an interchange 4 4 4 5 5 5 : pair in correct order numbers in color: guaranteed to be in correct order FIGURE 1 The Steps of a Bubble Sort. Solution: The steps of this algorithm are illustrated in Figure 1. Begin by comparing the first two elements, 3 and 2. Because 3 > 2, interchange 3 and 2, producing the list 2, 3, 4, 1, 5. Because 3 < 4, continue by comparing 4 and 1. Because 4 > 1, interchange 1 and 4, producing the list 2, 3, 1, 4, 5. Because 4 < 5, the first pass is complete. The first pass guarantees that the largest element, 5, is in the correct position. The second pass begins by comparing 2 and 3. Because these are in the correct order, 3 and 1 are compared. Because 3 > 1, these numbers are interchanged, producing 2, Prepared by: Mr. Kenneth V. Bautista 7 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 1, 3, 4, 5. Because 3 < 4, these numbers are in the correct order. It is not necessary to do any more comparisons for this pass because 5 is already in the correct position. The second pass guarantees that the two largest elements, 4 and 5, are in their correct positions. The third pass begins by comparing 2 and 1. These are interchanged because 2 > 1, producing 1, 2, 3, 4, 5. Because 2 < 3, these two elements are in the correct order. It is not necessary to do any more comparisons for this pass because 4 and 5 are already in the correct positions. The third pass guarantees that the three largest elements, 3, 4, and 5, are in their correct positions. The fourth pass consists of one comparison, namely, the comparison of 1 and 2. Because 1 < 2, these elements are in the correct order. This completes the bubble sort. ALGORITHM 4 The Bubble Sort. procedure bubble sort(a1,...,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,...,an is in increasing order} THE INSERTION SORT The insertion sort is a simple sorting algorithm, but it is usually not the most efficient. To sort a list with n elements, the insertion sort begins with the second element. The insertion sort compares this second element with the first element and inserts it before the first element if it does not exceed the first element and after the first element if it exceeds the first element. At this point, the first two elements are in the correct order. The third element is then compared with the first element, and if it is larger than the first element, it is compared with the second element; it is inserted into the correct position among the first three elements. In general, in the j th step of the insertion sort, the j th element of the list is inserted into the correct position in the list of the previously sorted j − 1 elements. To insert the j th element in the list, a linear search technique is used; the j th element is successively compared with the already sorted j − 1 elements at the start of the list until the first element that is not less than this element is found or until it has been compared with all j − 1 elements; the j th element is inserted in the correct position so that the first j elements are sorted. The algorithm continues until the last element is placed in the correct position relative to the already sorted list of the first n − 1 elements. The insertion sort is described in pseudocode in Algorithm 5. EXAMPLE 5 Use the insertion sort to put the elements of the list 3, 2, 4, 1, 5 in increasing order. Solution: The insertion sort first compares 2 and 3. Because 3 > 2, it places 2 in the first position, producing the list 2, 3, 4, 1, 5 (the sorted part of the list is shown in bold). At this point, 2 and 3 are in the correct order. Next, it inserts the third element, 4, into the already sorted part of the list by making the comparisons 4 > 2 and 4 > 3. Because Prepared by: Mr. Kenneth V. Bautista 8 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 4 > 3, 4 remains in the third position. At this point, the list is 2, 3, 4, 1, 5 and we know that the ordering of the first three elements is correct. Next, we find the correct place for the fourth element, 1, among the already sorted elements, 2, 3, 4. Because 1 < 2, we obtain the list 1, 2, 3, 4, 5. Finally, we insert 5 into the correct position by successively comparing it to 1, 2, 3, and 4. Because 5 > 4, it stays at the end of the list, producing the correct order for the entire list. ALGORITHM 5 The Insertion Sort. procedure insertion sort(a1, a2,...,an: real numbers with n ≥ 2) for j := 2 to n i := 1 while aj > ai i := i + 1 m := aj for k := 0 to j − i − 1 aj−k := aj−k−1 ai := m {a1,...,an is in increasing order} IV. TEACHING AND LEARNING MATERIALS RESOURCES Hardware Device: Desktop Computer/ Laptop/ Mobile Phone Application Software: GC-LAMP; Google Meet; Facebook V. LEARNING TASKS EXERCISES: 1. List all the steps used by Algorithm 1 to find the maximum of the list 1, 8, 12, 9, 11, 2, 14, 5, 10, 4. 2. Determine which characteristics of an algorithm described in the text (after Algorithm 1) the following procedures have and which they lack. a. procedure double(n: positive integer) while n > 0 n := 2n b. procedure divide(n: positive integer) while n ≥ 0 m := 1/n n := n − 1 Prepared by: Mr. Kenneth V. Bautista 9 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.  Discrete Structures 2: ALGORITHMS | Module No. 4 c. procedure sum(n: positive integer) sum := 0 while i < 10 sum := sum + i d. procedure choose(a, b: integers) x := either a or b 3. Devise an algorithm that finds the sum of all the integers in a list. RUBRIC: 3 2 1 0 Answers all parts of Answers part of the Attempts to answer Does not answer the the question correctly question or is the question but is question and thoroughly partially correct incorrect VI. REFERENCE  Rosen, K. H. (2018). Discrete Mathematics and Its Applications, Eighth Edition. McGraw-Hill. Prepared by: Mr. Kenneth V. Bautista 10 | 10 EXCLUSIVE FOR GORDON COLLEGE ONLY.