Discrete Mathematics Lecture 1: Algorithms PDF

University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (1): Algorithms Instructor: Prof. Noureldien Abdelrahman **1.1 Introduction** **M**any problems can be solved by considering...

University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (1): Algorithms Instructor: Prof. Noureldien Abdelrahman **1.1 Introduction** **M**any 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. 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. **[DEFINITION 1]** An *algorithm* is a finite sequence of precise instructions for performing a computation or for solving a problem. **[EXAMPLE 1]** Describe an algorithm for finding the maximum (largest) value in a finite sequence of integers. 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. **[*Solution of Example 1:* 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. Instead of using a particular computer language to specify algorithms, we often use what is called pseudocode. Pseudocode provides an intermediate step between an English language description of an algorithm and an implementation of this algorithm in a programming language. A pseudocode description of the algorithm for finding the maximum element in a finite sequence follows: (Algorithm 1) **1.2 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: \- ***[Input]**.* An algorithm has input values from a specified set. \- ***[Outpu]**t.* From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem. **[- *Definiteness*]***.* The steps of an algorithm must be defined precisely. **[- *Correctness*]***.* An algorithm should produce the correct output values for each set of input values. **[- *Finiteness*]***.* An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set. **[- *Effectiveness*]***.* It must be possible to perform each step of an algorithm exactly and in a finite amount of time. **[- *Generality*]***.* The procedure should be applicable for all problems of the desired form, not just for a particular set of input values. **1.3 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. The general searching problem can be described as follows: Locate an element *x* in a list of distinct elements *a*~1~*, a*~2~*,... , a~n~*, 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* = *a~i~* ) 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 *a*~1~. When *x* = *a*~1~, the solution is the location of *a*1, namely, 1. When *x ≠* *a*1, compare *x* with *a*~2~. If *x* = *a*~2~, the solution is the location of *a*~2~, namely, 2. When *x ≠ a*2, compare *x* with *a*3. 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. **[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 sub lists 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. Algorithm 3 demonstrates how a binary search works. **1.4 Sorting Algorithms** 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. **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. **1.4 The Growth of Functions** The time required to solve a problem depends on: 1. The number of operations it uses. 2. The hardware and software used to run the program that implements the algorithm. However, when we change the hardware and software used to implement an algorithm, we can closely approximate the time required to solve a problem of size *n* by multiplying the previous time required by a constant. **[Big-*O* notation]** Big-*O* notation is used extensively to estimate the number of operations an algorithm uses as its input grows. With the help of this notation, we can: Determine whether it is practical to use a particular algorithm to solve a problem as the size of the input increases. Furthermore, using Big-*O* notation, we can: **Compare two algorithms to determine which is more efficient as the size of the input grows.** For instance, if we have two algorithms for solving a problem, one using 100*n*^2^ + 17*n* + 4 operations and the other using *n*^3^ operations, Big-*O* notation can help us see that the first algorithm uses far fewer operations when *n* is large, even though it uses more operations for small values of *n*, such as *n* = 10. **DEFINITION 2** Let *f* and *g* be functions from the set of integers or the set of real numbers to the set of real numbers. We say that *f (x)* is *O(g(x))* if there are constants *C* and *k* such that \|*f (x)*\| ≤ *C*\|*g(x)*\| whenever *x \> k*. \[This is read as "*f (x)* is big-oh of *g(x)*."\] ***Remark:* the definition that *f (x)* is *O(g(x))* says that *f (x)* grows slower that some fixed multiple of *g(x)* as *x* grows without bound.** **The relationship *f (x)* is *O(g(x))*** The constants *C* and *k* in the definition of Big-*O* notation are called **witnesses** to the relationship *f (x)* is *O(g(x))*. To say that *f (x)* is *O(g(x))* we need only one pair of witnesses to this relationship. That is, to show that *f (x)* is *O(g(x))*, we need find only *one* pair of constants *C* and *k*, the witnesses, such that \|*f (x)*\| ≤ *C*\|*g(x)*\| whenever *x \> k*. **How to find the Witnesses Pair?** A useful approach for finding a pair of witnesses is to first select a **value of *k* for** which the size of \|*f (x)*\| can be readily estimated when *x \> k* and to see whether we can use this estimate to find a value of *C* for which \|*f (x)*\| ≤ *C*\|*g(x)*\| for *x \> k*. This approach is illustrated in Example 1. **[EXAMPLE 2]** Show that *f (x)* = *x*^2^ + 2*x* + 1 is *O(x*^2^*)*. ***Solution:*** We can estimate the size of *f (x)* when *x \>* 1 because if x \> 1 then *x \< x*^2^ and 1 *\< x*^2^. It follows that 0 ≤ *x*^2^ + 2*x* + 1 ≤ *x*^2^ + 2*x*^2^ + *x*^2^ = 4*x*^2^ Consequently, we can take *C* = 4 and *k* = 1 as witnesses to show that *f (x)* is *O(x*^2^*)*. That is, *f (x)* = *x*^2^ + 2*x* + 1 *\* 1. (Note that it is not necessary to use absolute values here because all functions in these equalities are positive when *x* is positive.) **[EXAMPLE 2]** Show that f(x)=7*x*^2^ is *O(x*^3^*)*. ***[Solution]**:* Note that when *x \>* 7, we have 7*x*^2^ *\< x*^3^. (We can obtain this inequality by multiplying both sides of *x \>* 7 by *x*^2^.) Consequently, we can take *C* = 1 and *k* = 7 as witnesses to establish the relationship 7*x*^2^ is *O(x*^3^*)*. Alternatively, when *x \>* 1, we have 7*x*^2^ *\* 1 we have \|*f (x)*\| = \|*a~n~x^n^* + *a~n~*~−1~*x^n^*^−1^ +・ ・ ・+*a*~1~*x* + *a*~0~\| ≤ \|*a~n~*\|*x^n^* + \|*a~n~*~−1~\|*x^n^*^−1^ + ・・・ + \|*a*~1~\|*x* + \|*a*~0~\| = *x^n^* (\|*a~n~*\| + \|*a~n~*~−1~\|*/x* + ・・・ + \|*a*~1~\|*/x^n^*^−1^ + \|*a*~0~\|*/x^n^* ) ≤ *x^n^ (*\|*a~n~*\| + \|*a~n~*~−1~\| + ・・・ + \|*a*~1~\| + \|*a*~0~\|*).* This shows that \|*f (x)*\| ≤ *Cx^n^,* Where *C* = \|*a~n~*\| + \|*a~n~*~−1~\| + ・・・ + \|*a*~0~\| whenever *x \>* 1. Hence, the witness's *C* = \|*a~n~*\| + \|*a~n~*~−1~\|+ ・ ・ ・+\|*a*~0~\| and *k* = 1 show that *f (x)* is *O(x^n^)*. **EXAMPLE 3** How can Big-*O* notation be used to estimate the sum of the first *n* positive integers? ***[Solution]**:* Because each of the integers in the sum of the first *n* positive integers does not exceed *n*, it follows that 1 + 2+・ ・ ・+*n = n + n + n +... +n* ≤ *n* + *n*+・ ・ ・+*n* = *n*^2^*.* From this inequality it follows that 1 + 2 + 3+・ ・ ・+*n* is *O(n*^2^*)*, taking *C* = 1 and *k* = 1 as witnesses. **EXAMPLE 4** Give Big-*O* estimates for the factorial function and the logarithm of the factorial function, where the factorial function *f (n)* = *n*! is defined by *n*! = 1 ・ 2 ・ 3 ・ ・ ・ ・ ・ *n* whenever *n* is a positive integer, and 0! = 1. For example, 1! = 1*,* 2! = 1 ・ 2 = 2*,* 3! = 1 ・ 2 ・ 3 = 6*,* 4! = 1 ・ 2 ・ 3 ・ 4 = 24*.* Note that the function *n*! grows rapidly. For instance, 20! = 2*,*432*,*902*,*008*,*176*,*640*,*000*.* *Solution:* A Big-*O* estimate for *n*! can be obtained by noting that each term in the product does not exceed *n*. Hence, *n*! = 1 ・ 2 ・ 3 ・ ・ ・ ・ ・ *n* ≤ *n* ・ *n* ・ *n* ・ ・ ・ ・ ・ *n* = *n^n^.* This inequality shows that *n*! is *O(n^n^)*, taking *C* = 1 and *k* = 1 as witnesses. Taking logarithms of both sides of the inequality established for *n*!, we obtain log *n*! ≤ log *n^n^* = *n* log *n.* This implies that log *n*! is *O(n* log *n)*, again taking *C* = 1 and *k* = 1 as witnesses. University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (2): Complexity of Algorithms Instructor: Prof. Noureldien Abdelrahman **2.1 Introduction** When does an algorithm provide a satisfactory solution to a problem? - First, it must always produce the correct answer. - Second, it should be efficient. The efficiency of algorithms will be discussed in this section. How can the efficiency of an algorithm be analyzed? - [One measure of efficiency is the time used by a computer to solve a problem using the algorithm], when input values are of a specified size. - [A second measure is the amount of computer memory required to implement the algo]rithm when input values are of a specified size. The above two measures are the **computational complexity** of the algorithm. An analysis of the time required to solve a problem of a particular size is called the **time complexity** of the algorithm. An analysis of the computer memory required is called the **space complexity** of the algorithm. **2.2 Time Complexity** The time complexity of an algorithm can be expressed in terms of the number of operations used by the algorithm when the input has a particular size. The operations used to measure time complexity can be the comparison of integers, the addition of integers, the multiplication of integers, the division of integers, or any other basic operation. Time complexity is described in terms of the number of operations required *[**instead of actual computer time** b]*ecause of the difference in time needed for different computers to perform basic operations. We will illustrate how to analyze the time complexity of an algorithm by considering Algorithm 1, which finds the maximum of a finite set of integers. **EXAMPLE 1** Describe the time complexity of Algorithm 1 of Section 3.1 for finding the maximum element in a finite set of integers. ***[Solution:]*** The number of comparisons will be used as the measure of the time complexity of the algorithm, because comparisons are the basic operations used. To find the maximum element of a set with *n* elements we do the following: \- The temporary maximum is first set equal to the initial term in the list. \- After the comparison (*i* ≤ *n)* has been done to determine that the end of the list has not yet been reached, the temporary maximum and second term are compared. \- The temporary maximum is updated to the value of the second term if it is larger (max *\< a~i~*). \- This procedure is continued, until i \> n. Now, because two comparisons are used *[for each of the second through the nth]* elements and one *[more comparison is used to exit the loop when i = n + 1]*, then exactly **[2*(n* − 1*)* + 1 = 2*n* − 1]** comparisons are used whenever this algorithm is applied. Hence, the algorithm for finding the maximum of a set of *n* elements has time complexity *O(n)*, measured in terms of the number of comparisons used. ▲ **EXAMPLE 2** Describe the time complexity of the linear search algorithm (specified as Algorithm 2 in Section 3.1). ***Solution*** The number of comparisons used by Algorithm 2 in Section 3.1 will be taken as the measure of the time complexity. At each step of the loop in the algorithm, two comparisons are performed: 1. *i* ≤ *n*, to see whether the end of the list has been reached 2. *x* ≠ *a~i~* , to compare the element *x* with a term of the list. 3. Finally, one more comparison *i* ≤ *n* is made outside the loop. Consequently, if *x* = *a~i~*, 2*i* + 1 comparisons are used. The maximum number of comparisons is; 2*n* + 2, which are required when the element is not in the list. In this case, 2*n* comparisons are used to determine that *x* is not *a~i~,* for *i* = 1*,* 2*,... , n*, an additional comparison is used to exit the loop, and one comparison is made outside the loop. So when *x* is not in the list, a total of 2*n* + 2 comparisons are used. Hence, a linear search requires *O(n)* comparisons in [the worst case,] because 2*n* + 2 is *O(n)*. **2.3 Worst-Case Complexity** The type of complexity analysis done in Example 2 is a **worst case** analysis. By the worst-case performance of an algorithm, we mean the largest number of operations needed to solve the given problem using this algorithm on input of specified size. Worst-case analysis tells us how many operations an algorithm requires to guarantee that it will produce a solution. **EXAMPLE 3** What is the worst-case complexity of the bubble sort in terms of the number of comparisons made? ***Solution*** The bubble sort described before Example 4 in Section 3.1 sorts a list by performing a sequence of passes through the list. During each pass the bubble sort successively compares adjacent elements, interchanging them if necessary. When the *^i^*th pass begins, the *i* − 1 largest elements are guaranteed to be in the correct positions. During this pass, *n* − *i* comparisons are used. Consequently, the total number of comparisons used by the bubble sort to order a list of *n* elements is Note that the bubble sort always uses this many comparisons, because it continues even if the list becomes completely sorted at some intermediate step. Consequently, the bubble sort uses *(n* − 1*)n/*2 comparisons, so it has *O(n*^2^*)* worst-case complexity in terms of the number of comparisons used. **2.4 Average-Case Complexity** Another important type of complexity analysis, besides worst-case analysis, is called **average-case** analysis. The average number of operations used to solve the problem over all possible inputs of a given size is found in this type of analysis. Average case time complexity analysis is usually much more complicated than worst-case analysis. **EXAMPLE 4** Describe the average-case performance of the linear search algorithm in terms of the average number of comparisons used, assuming that the integer *x* is in the list and it is equally likely that *x* is in any position. ***Solution*** By hypothesis, the integer *x* is one of the integers *a*~1~*, a*~2~*,... , a~n~* in the list. 1- If *x* is the first term *a*~1~ of the list, three comparisons are needed, one is *i* ≤ *n* to determine whether the end of the list has been reached, one is *x ±* *a~i~* to compare *x* and the first term, and one *i* ≤ *n* outside the loop. 2- If *x* is the second term *a*~2~ of the list, two more comparisons are needed, so that a total of five comparisons are used. In general, if *x* is the *^i^*th term of the list *a~i~* , two comparisons will be used at each of the *i* steps of the loop, and one outside the loop, so that a total of 2*i* + 1 comparisons are needed. Hence, the average number of comparisons used equals Using the formula from line 2 of Table 2 in Section 2.4 (and see Exercise 37(b) of Section 2.4), Hence, the average number of comparisons used by the linear search algorithm (when *x* is known to be in the list) is which is O*(n)*. University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (3): Counting Instructor: Prof. Noureldien Abdelrahman **3.1 Introduction** **[Combinatorics]**, the study of arrangements of objects, is an important part of discrete mathematics. [**Enumeration**,] the counting of objects with certain properties, is an important part of combinatorics. The basic rules of counting, can solve a tremendous variety of problems. For instance, we can use these rules to enumerate the different telephone numbers possible in the Sudan, the allowable passwords on a computer system, and the different orders in which the runners in a race can finish. **3.2 Basic Counting Principles** We first present two basic counting principles, the **product rule** and the **sum rule**. Then we will show how they can be used to solve many different counting problems. The product rule applies when a procedure is made up of separate tasks. **[THE PRODUCT RULE]** Suppose that a procedure can be broken down into a sequence of two tasks. If there are *n*~1~ ways to do the first task and for each of these ways of doing the first task, there are *n*~2~ ways to do the second task, **[then there are *n*1*n*2 ways to]** do the procedure. **EXAMPLE 1** A new company with just two employees, Sanchez and Patel, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees? ***Solution:*** The procedure of assigning offices to these two employees consists of assigning an office to Sanchez, which can be done in 12 ways, then assigning an office to Patel different from the office assigned to Sanchez, which can be done in 11 ways. By the product rule, there are 12 · 11 = 132 ways to assign offices to these two employees. ▲ **EXAMPLE 2** The chairs of an auditorium are to be labeled with an uppercase English letter followed by a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently? ***Solution:*** The procedure of labeling a chair consists of two tasks, namely, assigning to the seat one of the 26 uppercase English letters, and then assigning to it one of the 100 possible integers. The product rule shows that there are 26 · 100 = 2600 different ways that a chair can be labeled. Therefore, the largest number of chairs that can be labeled differently is 2600. An extended version of the product rule is often useful. Suppose that a procedure is carried out by performing the tasks *T*1*, T*2*,... , Tm* in sequence. If each task *Ti* , *i* = 1*,* 2*,... , n*, can be done in *n~i~* ways, regardless of how the previous tasks were done, then there are *n*~1~ · *n*~2~ · · · · · *n~m~* ways to carry out the procedure. **EXAMPLE 3** How many different bit strings of length seven are there? ***Solution:*** Each of the seven bits can be chosen in two ways, because each bit is either 0 or 1. Therefore, the product rule shows there are a total of 2^7^ = 128 different bit strings of length seven. **EXAMPLE 4** How many different license codes can be made if each code contains a sequence of three uppercase English letters followed by three digits? **Solution** There are 26 choices for each of the three uppercase English letters and ten choices for each of the three digits. Hence, by the product rule there are a total of 26 · 26 · 26 · 10 · 10 · 10 = 17*,*576*,*000 possible license plates. **[THE SUM RULE ]** If a task can be done either in one of *n*~1~ ways or in one of *n*~2~ ways, where none of the set of *n*~1~ ways is the same as any of the set of *n*~2~ ways, then there are *n*~1~ + *n*~2~ ways to do the task. **EXAMPLE 5** Suppose that either a member of the mathematics faculty or a student who is a mathematics major is chosen as a representative to a university committee. How many different choices are there for this representative [if there are 37 members] of the mathematics [faculty and 83 mathematics majors] and no one is both a faculty member and a student? ***Solution:*** There are 37 ways to choose a member of the mathematics faculty and there are 83 ways to choose a student who is a mathematics major. Choosing a member of the mathematics faculty is never the same as choosing a student who is a mathematics major because no one is both a faculty member and a student. By the sum rule it follows that there are 37 + 83 = 120 possible ways to pick this representative. We can extend the sum rule to more than two tasks. Suppose that a task can be done in one of *n*~1~ ways, in one of *n*~2~ ways, *...* , or in one of *n~m~* ways, where none of the set of *n~i~* ways of doing the task is the same as any of the set of *n~j~* ways, for all pairs *i* and *j* with 1 ≤ *i \< j* ≤ *m*. Then the number of ways to do the task is *n*~1~ + *n*~2~ +· · ·+*n~m~*. **EXAMPLE 6** A student can choose a computer project from one of three lists. The three lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one list. How many possible projects are there to choose from? ***Solution:*** The student can choose a project by selecting a project from the first list, the second list, or the third list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to choose a project. **EXAMPLE 7** Each user on a computer system has a password, [which is six to eight characters long], where each character is an uppercase letter or a digit. Each password must [contain at least one digit]. How many possible passwords are there? ***Solution:*** Let *P* be the total number of possible passwords, and let *P*6, *P*7, and *P*8 denote the number of possible passwords of length 6, 7, and 8, respectively. By the sum rule, *P* = *P*6 + *P*7 + *P*8. We will now find *P*6, *P*7, and *P*8. Finding *P*6 directly is difficult. To find *P*6 it is easier to find the number of strings of [uppercase letters and digits that are six characters long, including those with no digits, and subtract from this the number of strings with no digits.] By the product rule, the number of strings of six characters is 36^6^, and the number of strings with no digits is 26^6^. Hence, *P*6 = 36^6^ − 26^6^ = 2*,*176*,*782*,*336 − 308*,*915*,*776 = 1*,*867*,*866*,*560*.* Similarly, we have *P*7 = 36^7^ − 26^7^ = 78*,*364*,*164*,*096 − 8*,*031*,*810*,*176 = 70*,*332*,*353*,*920 and *P*8 = 36^8^ − 26^8^ = 2*,*821*,*109*,*907*,*456 − 208*,*827*,*064*,*576 = 2*,*612*,*282*,*842*,*880*.* Consequently, *P* = *P*6 + *P*7 + *P*8 = 2*,*684*,*483*,*063*,*360*.* [**THE SUBTRACTION RULE** I] If a task can be done in either *n*~1~ ways or *n*~2~ ways, then the number of ways to do the task is *n*1 + *n*2 minus the number of ways to do the task that are common to the two different ways. The subtraction rule is also known as the **principle of inclusion--exclusion**, especially when it is used to count the number of elements in the union of two sets. Suppose that *A*1 and *A*2 are sets. Then, there are \|*A*1\| ways to select an element from *A*1 and \|*A*2\| ways to select an element from *A*2. The number of ways to select an element from *A*1 or from *A*2, that is, the number of ways to select an element from their union, is the sum of the number of ways to select an element from *A*1 and the number of ways to select an element from *A*2, minus the number of ways to select an element that is in both*A*1 and*A*2. Because there are \|*A*1 ∪ *A*2\|ways to select an element in either *A*1 or in *A*2, and \|*A*1 ∩ *A*2\| ways to select an element common to both sets, we have \|*A*1 ∪ *A*2\| = \|*A*1\| + \|*A*2\| − \|*A*1 ∩ *A*2\|*.* **EXAMPLE 8** How many bit strings of length eight either start with a 1 bit or end with the two bits 00? ***Solution*** We can construct a bit string of [length eight that either starts with a 1 bit or ends] [with the two bits 00, b]y constructing a bit string of length eight beginning with a 1 bit **[or]** by constructing a bit string of length eight that ends with the two bits 00. We can construct a bit string of length eight that begins with a 1 in 2^7^ = 128 ways. This follows by the product rule, because the first bit can be chosen in only one way and each of the other seven bits can be chosen in two ways. Similarly, we can construct a bit string of length eight ending with the two bits 00, in 2^6^ = 64 ways. This follows by the product rule, because each of the first six bits can be chosen in two ways and the last two bits can be chosen in only one way. [Some of the ways to construct a bit string of length eight starting with a 1 are the same as the ways to construct a bit string of length eight that ends with the two bits 00]. There are 2^5^ = 32 ways to construct such a string. This follows by the product rule, because the first bit can be chosen in only one way, each of the second through the sixth bits can be chosen in two ways, and the last two bits can be chosen in one way. Consequently, the number of bit strings of length eight that begin with a 1 or end with a 00, which equals the number of ways to construct a bit string of length eight that begins with a 1 or that ends with 00, equals 128 + 64 − 32 = 160. University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (4): **Permutations and Combinations** Instructor: Prof. Noureldien Abdelrahman **4.1 Introduction** **[Many counting problems can be solved]** by finding the number of ways to arrange a specified **[number of distinct elements]** of a set of a particular size, where **[the order of these elements matters].** **[Many other counting problems]** can be solved by finding the number of ways to **[select a particular number of elements]** from a set of a particular size, where the **[order of the elements selected does not matter].** **4.2 Permutations** We begin by solving the following example. **EXAMPLE 1** In how many ways can we select three students from a group of five students to stand in line for a picture? In how many ways can we arrange all five of these students in a line for a picture? ***Solution**:* First, note that the order in which we select the students matters. There are five ways to select the first student to stand at the start of the line. Once this student has been selected, there are four ways to select the second student in the line. After the first and second students have been selected, there are three ways to select the third student in the line. By the product rule, there are 5 · 4 · 3 = 60 ways to select three students from a group of five students to stand in line for a picture. To arrange all five students in a line for a picture, we select the first student in five ways, the second in four ways, the third in three ways, the fourth in two ways, and the fifth in one way. Consequently, there are 5 · 4 · 3 · 2 · 1 = 120 ways to arrange all five students in a line for a picture. **[Definition 1]** A **permutation** of a set of distinct objects is an ordered arrangement of these objects. We also are interested in ordered arrangements of some of the elements of a set. An ordered arrangement of *r* elements of a set is called an ***r*-permutation**. **EXAMPLE 2** Let *S* = {1*,* 2*,* 3}. The ordered arrangement 3, 1, 2 is a permutation of *S*. The ordered arrangement 3, 2 is a 2-permutation of *S*. **[Definition 2]** The number of *r*-permutations of a set with *n* elements is denoted by *P(n, r)*. We can find *P(n, r)* using the product rule. **EXAMPLE 3** Let *S* = {*a, b, c*}. The 2-permutations of *S* are the ordered arrangements *a, b*; *a, c*; *b, a*; *b, c*; *c, a*; and *c, b*. Consequently, there are six 2-permutations of this set with three elements. There are always six 2-permutations of a set with three elements. There are three ways to choose the first element of the arrangement. There are two ways to choose the second element of the arrangement, because it must be different from the first element. Hence, by the product rule, we see that *P(*3*,* 2*)* = 3 · 2 = 6. We now use the product rule to find a formula for *P(n, r)* whenever *n* and *r* are positive integers with 1 ≤ *r* ≤ *n*. **[THEOREM 1]** If *n* is a positive integer and *r* is an integer with 1 ≤ *r* ≤ *n*, then there are *P(n, r)* = *n(n* − 1*)(n* − 2*)* · · · *(n* − *r* + 1*)* *r*-permutations of a set with *n* distinct elements. **[COROLLARY 1]** If *n* and *r* are integers with 0 ≤ *r* ≤ *n*, then *P(n, r)* = *n*!/*(n* − *r)*! **EXAMPLE 4** How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered a contest? ***Solution:*** Because it matters which person wins which prize, the number of ways to pick the three prize winners is *[the number of ordered selections of three elements]* from a set of 100 elements, that is, the number of 3-permutations of a set of 100 elements. Consequently, the answer is *P(*100*,* 3*)* = 100 · 99 · 98 = 970*,*200*.* **EXAMPLE 5** How many permutations of the letters *ABCDEFGH* contain the string *ABC* ? ***Solution:*** Because the letters *ABC* must occur as a block, we can find the answer by finding the number of permutations of six objects, namely, the block *ABC* and the individual letters *D*, *E*, *F*, *G*, and *H*. Because these six objects can occur in any order, there are 6! = 720 permutations of the letters *ABCDEFGH* in which *ABC* occurs as a block. **4.3 Combinations** We now turn our attention to counting [unordered selections of objects]. We begin by solving example 6. **EXAMPLE 6** How many different committees of three students can be formed from a group of four students? ***Solution:*** To answer this question, we need only to find the number of subsets with three elements from the set containing the four students. We see that there *[are four such]* subsets, one for each of the four students, because choosing three students is the same as choosing one of the four students to leave out of the group. This means that [there are four ways to choose the three students for the committee], where the order in which these students are chosen does not matter. **Definition 3** An ***r*-combination** of elements of a [set is an unordered selection of] *r* elements from the set. Thus, an *r*-combination is simply a subset of the set with *r* elements. The number of *r*-combinations of a set with *n* distinct elements is denoted by *C (n, r)* or **THEOREM 2** The number of *r*-combinations of a set with *n* elements, where *n* is a nonnegative integer and *r* is an integer with 0 ≤ *r* ≤ *n*, equals *C(n, r)* = *n*!/ *r*! *(n* − *r)*! *.* **EXAMPLE 7** How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school? ***Solution**:* The answer is given by the number of 5-combinations of a set with 10 elements. By Theorem 2, the number of such combinations is *C(*10*,* 5*)* = 10!/5! 5! = 252*.* **EXAMPLE 8** How many bit strings of length *n* contain exactly *r* 1s? *Solution:* The positions of *r* 1s in a bit string of length *n [ ]*[form an *r*-combination of the set] [{1*,* 2*,* 3*,... , n*}]. Hence, there are *C(n, r)* bit strings of length *n* that contain exactly *r* 1s. **EXAMPLE 9** Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department? ***Solution:*** By the product rule, the answer is the [product of the number of 3-combinations] of a set with nine elements and the [number of 4-combinations of a set] with 11 elements. By Theorem 2, the number of ways to select the committee is *C(*9*,* 3*)* · *C(*11*,* 4*)* = 9!/3!6! · 11!/4!7! = 84 · 330 = 27*,*720*.* **4.4 The Binomial Theorem** The binomial theorem gives the coefficients of the expansion of powers of binomial expressions. A **binomial** expression is simply the sum of two terms, such as *x* + *y*. (The terms can be products of constants and variables, but that does not concern us here.) **EXAMPLE 10** What is the expansion of *(x* + *y)*^4^? *Solution:* From the binomial theorem it follows that **EXAMPLE 11** What is the coefficient of *x*^12^*y*^13^ in the expansion of *(x* + *y)*^25^? *Solution:* From the binomial theorem it follows that this coefficient is **EXAMPLE 12** What is the coefficient of *x*^12^*y*^13^ in the expansion of *(*2*x* − 3*y)*^25^? *Solution:* First, note that this expression equals *(*2*x* + *(*−3*y))*^25^. By the binomial theorem, we have Consequently, the coefficient of *x*^12^*y*^13^ in the expansion is obtained when *j* = 13, namely, University of Science and Technology Faculty of Computer Science and Information Technology **Computer Science Department** **Semester 6: Discrete Mathematics** Lecture (5): Relations Instructor: Prof. Noureldien Abdelrahman **5.1 Introduction** Relationships between elements of sets are represented using the structure called a **relation**, [which is just a subset of the Cartesian product of] the sets. Relations can be used to solve problems such as determining which pairs of cities are linked by airline flights in a network, finding a viable order for the different phases of a complicated project, or producing a useful way to store information in computer databases. **5.2 Relations and Their Properties** The most direct way to express a relationship between elements of two sets is to use [ordered pairs made up of two related] elements. For this reason, sets of ordered pairs are called binary relations. In this section we introduce the basic terminology used to describe binary relations. **DEFINITION 1** Let *A* and *B* be sets. A *binary relation from A to B* is a subset of *A* × *B*. In other words, a binary relation from *A* to *B* is a set *R* of ordered pairs where the first element of each ordered pair comes from *A* and the second element comes from *B*. We use the notation *a R b* to denote that *(a, b)* ∈ *R* and to denote that Moreover, when *(a, b)* belongs to *R*, *a* is said to be **related to** *b* by *R*. Binary relations represent relationships between the elements of two sets. **EXAMPLE 1** Let *A* = {0*,* 1*,* 2} and *B* = {*a, b*}. Then {*(*0*, a), (*0*, b), (*1*, a), (*2*, b)*} is a relation from *A* to *B*. This means, for instance, that 0*R a*, but that 1\_*R b*. Relations can be represented graphically, as shown in Figure 1, using arrows to represent ordered pairs. Another way to represent this relation is to use a table, which is also done in Figure 1. **5.3 Functions as Relations** Recall that a function *f* from a set *A* to a set *B* assigns exactly one element of *B* to each element of *A*. The graph of *f* is the set of ordered pairs *(a, b)* such that *b* = *f (a)*. Because the graph of *f* is a subset of *A* × *B*, it is a relation from *A* to *B*. A relation can be used to express [a one-to-many relationship] between the elements of the sets *A* and *B*, where an element of *A* may be related to more than one element of *B*.A function represents a relation where exactly one element of *B* is related to each element of *A*. **5.3.1 Relations on a Set** Relations from a set *A* to itself are of special interest. **DEFINITION 2** A *relation on a set A* is a relation from *A* to *A*. In other words, a relation on a set *A* is a subset of *A* × *A*. **EXAMPLE 2** Let *A* be the set {1*,* 2*,* 3*,* 4}. Which ordered pairs are in the relation *R* = {*(a, b)* \| *a* divides *b*}? ***Solution:*** Because *(a, b)* is in *R* if and only if *a* and *b* are positive integers not exceeding 4 such that *a* divides *b*, we see that *R* = {*(*1*,* 1*), (*1*,* 2*), (*1*,* 3*), (*1*,* 4*), (*2*,* 2*), (*2*,* 4*), (*3*,* 3*), (*4*,* 4*)*}*.* **5.4 Properties of Relations** There are several properties that are used to classify relations on a set. We will introduce the most important of these here. **DEFINITION 3** A relation *R* on a set *A* is called *reflexive* if *(a, a)* ∈ *R* for every element *a* ∈ *A*. **DEFINITION 4** A relation *R* on a set *A*i s called *symmetric* if *(b, a)* ∈ *R* whenever *(a, b)* ∈ *R*, for all *a, b* ∈ *A*. A relation *R* on a set *A* such that for all *a, b* ∈ *A*, if *(a, b)* ∈ *R* and *(b, a)* ∈ *R*, then *a* = *b* is called *antisymmetric*. EXAMPLE 3 Consider the following relations on {1*,* 2*,* 3*,* 4}: *R*1 = {*(*1*,* 1*), (*1*,* 2*), (*2*,* 1*), (*2*,* 2*), (*3*,* 4*), (*4*,* 1*), (*4*,* 4*)*}*,* *R*2 = {*(*1*,* 1*), (*1*,* 2*), (*2*,* 1*)*}*,* *R*3 = {*(*1*,* 1*), (*1*,* 2*), (*1*,* 4*), (*2*,* 1*), (*2*,* 2*), (*3*,* 3*), (*4*,* 1*), (*4*,* 4*)*}*,* *R*4 = {*(*2*,* 1*), (*3*,* 1*), (*3*,* 2*), (*4*,* 1*), (*4*,* 2*), (*4*,* 3*)*}*,* *R*5 = {*(*1*,* 1*), (*1*,* 2*), (*1*,* 3*), (*1*,* 4*), (*2*,* 2*), (*2*,* 3*), (*2*,* 4*), (*3*,* 3*), (*3*,* 4*), (*4*,* 4*)*}*,* *R*6 = {*(*3*,* 4*)*}*.* Which of these relations are reflexive? ***Solution:*** The relations *R*3 and *R*5 are reflexive because they both contain all pairs of the form *(a, a)*, namely, *(*1*,* 1*)*, *(*2*,* 2*)*, *(*3*,* 3*)*, and *(*4*,* 4*)*. The other relations are not reflexive because they do not contain all of these ordered pairs. In particular, *R*1, *R*2, *R*4, and *R*6 are not reflexive because *(*3*,* 3*)* is not in any of these relations. **EXAMPLE 4** Which of the relations from Example 3 are symmetric and which are antisymmetric? ***Solution:*** The relations *R*2 and *R*3 are symmetric, because in each case *(b, a)* belongs to the relation whenever *(a, b)* does. For *R*2*,* the only thing to check is that both *(*2*,* 1*)* and *(*1*,* 2*)* are in the relation. For *R*3, it is necessary to check that both *(*1*,* 2*)* and *(*2*,* 1*)* belong to the relation, and *(*1*,* 4*)* and *(*4*,* 1*)* belong to the relation. The reader should verify that none of the other relations is symmetric. This is done by finding a pair *(a, b)* such that it is in the relation but *(b, a)* is not. *R*4, *R*5, and *R*6 are all antisymmetric. For each of these relations there is no pair of elements *a* and *b* with *a* \_= *b* such that both *(a, b)* and *(b, a)* belong to the relation. The reader should verify that none of the other relations is antisymmetric. **DEFINITION 5** A relation *R* on a set *A* is called *transitive* if whenever *(a, b)* ∈ *R* and *(b, c)* ∈ *R*, then *(a, c)* ∈ *R*, for all *a, b, c* ∈ *A*. **EXAMPLE 5** Which of the relations in Example 3 are transitive? ***Solution:*** *R*4, *R*5, and *R*6 are transitive. For each of these relations, we can show that it is transitive by verifying that if *(a, b)* and *(b, c)* belong to this relation, then *(a, c)* also does. For instance, *R*4 is transitive, because *(*3*,* 2*)* and *(*2*,* 1*)*, *(*4*,* 2*)* and *(*2*,* 1*)*, *(*4*,* 3*)* and *(*3*,* 1*)*, and *(*4*,* 3*)* and *(*3*,* 2*)* are the only such sets of pairs, and *(*3*,* 1*)*, *(*4*,* 1*)*, and *(*4*,* 2*)* belong to *R*4. The reader should verify that *R*5 and *R*6 are transitive. *R*1 is not transitive because *(*3*,* 4*)* and *(*4*,* 1*)* belong to *R*1, but *(*3*,* 1*)* does not. *R*2 is not transitive because *(*2*,* 1*)* and *(*1*,* 2*)* belong to *R*2, but *(*2*,* 2*)* does not. *R*3 is not transitive because *(*4*,* 1*)* and *(*1*,* 2*)* belong to *R*3, but *(*4*,* 2*)* does not. **5.5 Combining Relations** Because relations from *A* to *B* are subsets of *A* × *B*, two relations from *A* to *B* can be combined in any way two sets can be combined. Consider Examples 17--19. **EXAMPLE 6** Let *A* = {1*,* 2*,* 3} and *B* = {1*,* 2*,* 3*,* 4}. The relations *R*1 = {*(*1*,* 1*)*, *(*2*,* 2*)*, *(*3*,* 3*)*} and *R*2 = {*(*1*,* 1*)*, *(*1*,* 2*)*, *(*1*,* 3*)*, *(*1*,* 4*)*} can be combined to obtain *R*1 ∪ *R*2 = {*(*1*,* 1*), (*1*,* 2*), (*1*,* 3*), (*1*,* 4*), (*2*,* 2*), (*3*,* 3*)*}*,* *R*1 ∩ *R*2 = {*(*1*,* 1*)*}*,* *R*1 − *R*2 = {*(*2*,* 2*), (*3*,* 3*)*}*,* *R*2 − *R*1 = {*(*1*,* 2*), (*1*,* 3*), (*1*,* 4*)*}*.* **DEFINITION 6** Let *R* be a relation from a set *A* to a set *B* and *S* a relation from *B* to a set *C*. **The *composite* of *R* and *S* is the** relation consisting of ordered pairs *(a, c)*, where *a* ∈ *A*, *c* ∈ *C*, and for which there exists an element *b* ∈ *B* such that *(a, b)* ∈ *R* and *(b, c)* ∈ *S*. We **[denote the composite of *R* and *S* by *S* ◦*R*]** **EXAMPLE 7** What is the composite of the relations *R* and *S*, where *R* is the relation from {1*,* 2*,* 3} to {1*,* 2*,* 3*,* 4} with *R* = {*(*1*,* 1*), (*1*,* 4*), (*2*,* 3*), (*3*,* 1*), (*3*,* 4*)*} and *S* is the relation from {1*,* 2*,* 3*,* 4} to {0*,* 1*,* 2} with *S* = {*(*1*,* 0*), (*2*,* 0*), (*3*,* 1*), (*3*,* 2*), (*4*,* 1*)*}? ***Solution:*** *S* ◦*R* is constructed using all ordered pairs in *R* and ordered pairs in *S*, where the second element of the ordered pair in *R* agrees with the first element of the ordered pair in *S*. For example, the ordered pairs *(*2*,* 3*)* in *R* and *(*3*,* 1*)* in *S* produce the ordered pair *(*2*,* 1*)* in *S* ◦*R*. Computing all the ordered pairs in the composite, we find *S* ◦*R* = {*(*1*,* 0*), (*1*,* 1*), (*2*,* 1*), (*2*,* 2*), (*3*,* 0*), (*3*,* 1*)*}*.*