DS102 Discrete Structure Module PDF

MODULE 1 DS102: Discrete Structure LEARNING OUTCOMES After this module, students shall be able to: 1.​ Understand and construct mathematical arguments 2.​ Prove simple arguments 3.​ Develop recursive algorithms based on mathematical induction 4.​ Know...

MODULE 1 DS102: Discrete Structure LEARNING OUTCOMES After this module, students shall be able to: 1.​ Understand and construct mathematical arguments 2.​ Prove simple arguments 3.​ Develop recursive algorithms based on mathematical induction 4.​ Know basic properties of relations 5.​ Know essential concepts in graph theory and related algorithms 6.​ Understand basic concepts in formal languages and computability 7.​ Apply knowledge about discrete mathematics in problem solving ​ ​ LESSONS: LESSON 1: Propositional Logic LESSON 2: Sets and Functions LESSON 3: Application of Number Theory LESSON 6: Computational Complexity of Algorithms LESSON 7: Graphs and its Applications LESSON 8: Mathematical reasoning and induction LESSON 9: Probability, Statistics and Application LESSON 1: Propositional Logic What is Logic? Logic is the basis of all mathematical reasoning, and of all automated reasoning. The rules of logic specify the meaning of mathematical statements. Importance of Mathematical Logic The rules of logic give precise meaning to mathematical statements. These rules are used to distinguish between valid and invalid mathematical arguments. Apart from its importance in understanding mathematical reasoning, logic has numerous applications in Computer Science, varying from design of digital circuits, to the construction of computer programs and verification of correctness of programs. Propositional Logic What is a proposition? A proposition is the basic building block of logic. It is defined as a declarative sentence that is either True or False, but not both. The Truth Value of a proposition is True(denoted as T) if it is a true statement, and False(denoted as F) if it is a false statement. For Example,1. The sun rises in the East and sets in the West. 2. 1 + 1 = 2 3. 'b' is a vowel. All of the above sentences are propositions, where the first two are Valid(True) and the third one is Invalid(False). Some sentences that do not have a truth value or may have more than one truth value are not propositions. For Example, 1. What time is it? 2. Go out and play. 3. x + 1 = 2. The above sentences are not propositions as the first two do not have a truth value, and the third one may be true or false. To represent propositions, propositional variables are used. By Convention, these variables are represented by small alphabets such as p,q,r,s. The area of logic which deals with propositions is called propositional calculus or propositional logic. It also includes producing new propositions using existing ones. Propositions constructed using one or more propositions are called compound propositions. The propositions are combined together using Logical Connectives or Logical Operators. Truth Table Since we need to know the truth value of a proposition in all possible scenarios, we consider all the possible combinations of the propositions which are joined together by Logical Connectives to form the given compound proposition. This compilation of all possible scenarios in a tabular format is called a truth table. Most Common Logical Connectives-  LESSON 2: Sets and Functions SETS Set Theory A Set is defined as a group of objects, known as elements. These objects could be anything conceivable, including numbers, letters, colors, even set themselves. However, none of the objects of the set can be the set itself. Set Notation We write sets using braces and denote them with capital letters. The most natural way to describe sets is by listing all its members. For example, A = {1,2,3,…,10} is the set of the first 10 counting numbers, or naturals, B = {Red, Blue, Green} is the set of primary colors, N = {1,2,3,…} is the set of all naturals, and Z = {...,−3,−2,−1,0,1,2,3,…} is the set of all integers. Well defined Set Well-defined means, it must be absolutely clear that which object belongs to the set and which does not. Some common examples of well defined sets: ​ The collection of vowels in English alphabets. This set contains five elements, namely, a, e, i, o, u ​ N = {1,2,3,…} is the set of counting numbers, or naturals. ​ N = {1,2,3,…} is the set of counting numbers, or naturals. ​ Z = {…,−3,−2,−1,0,1,2,3,…} is the set of integers. Set Equality Two sets A and B are said to be equal if and only if both the sets have same and exact number of elements. Here, if and only if means that both parts of the statement ("A = B" and "both sets have the exact same elements") are interchangeable. For example, {2,4,6,8} = {4,8,6,2} and {2,4,6,8} = {2,4,2,6,8,2,6,4,4}. Another example comes from the set of even naturals, which can be described as E = {2,4,6,8,…} = {2x | x ∊ N}. Null Set A very important set is the empty set, or the null set, which has no elements. We denote the empty set by ∅, or {}. Note that we could also write, for example, ∅= {x | x ∊N and x < 0} or ∅ = {x | x ∊Q and x ∉Q}. Intersection of Sets The intersection of sets A and B, denoted as A ∩ B, is the set of elements common to both A AND B. For example: A = {1,2,3,4,5} B = {2,4,6,8,10} The intersection of A and B (i.e. A∩B) is simply {2, 4} Union of Sets The union of sets A and B, written as A∪B, is the set of elements that appear in either A OR B. For example: A = {1,2,3,4,5} B = {2,4,6,8,10} The union of A and B (i.e. A∪B) is {1, 2, 3, 4, 5, 6, 8, 10} Difference of Sets The difference of sets A and B, written as A-B, is the set of elements belonging to set A and NOT to set B. For example: A = {1,2,3,4,5} B = {2,3,5} The difference of A and B (i.e. A-B) is {1,4} NOTE: A-B ≠ B-A Cartesian Product of Sets The Cartesian product of sets A and B, written A x B, is expressed as: A x B = {(a,b)│a is every element in A, b is every element in B} For example: A = {1,2} B = {4,5,6} The Cartesian product of A and B (i.e. A x B) is {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6)} Now, lets us try doing some questions based on Set Theory. Solved Questions: Question 1: If ∪ = {1, 3, 5, 7, 9, 11, 13}, then which of the following are subsets of U. B = {2, 4} A = {0} C = {1, 9, 5, 13} D = {5, 11, 1} E = {13, 7, 9, 11, 5, 3, 1} F = {2, 3, 4, 5} Answer: Here, we can see that C, D and E have the terms which are there in ∪. Therefore, C, D and E are the subsets of ∪. Question 2: Let A and B be two finite sets such that n(A) = 20, n(B) = 28 and n(A ∪ B) = 36, find n(A ∩ B). Solution: Using the formula n(A ∪ B) = n(A) + n(B) - n(A ∩ B). then n(A ∩B) = n(A) + n(B) - n(A ∪B) = 20 + 28 - 36 = 48 - 36 = 12 Difference of Rule, Roster Method, Statement form Rule Method. - giving a descriptive phrase that will clearly identify the elements of the set. Example: A = { first four counting numbers} B= { even numbers} In this form of representation of a set, the element of the set is described by using a symbol ‘x’ or any other variable followed by a colon The symbol ‘:‘ or ‘|‘ is used to denote such that and then we write the property possessed by the elements of the set and enclose the whole description in braces. In this, the colon stands for ‘such that’ and braces stand for ‘set of all’. For example: (i) Let P is a set of counting numbers greater than 12; the set P in set-builder form is written as : ​ P = {x : x is a counting number and greater than 12} P={13,14,15,16….} or P = {x | x is a counting number and greater than 12} This will be read as, 'P is the set of elements x such that x is a counting number and is greater than 12'. Note: The symbol ':' or '|' placed between 2 x's stands for such that. Roster method - defined as a way to show the elements of a set by listing the elements inside of brackets. An example of the roster method is to write the set of numbers from 1 to 10 as {1,2,3,4,5,6,7,8,9 and 10}. Example: to write the seasons as {summer, fall, winter and spring}. i) Let N denote the set of first five natural numbers= Rule method Therefore, N = {1, 2, 3, 4, 5} → Roster Form II) Let F={set of flowers} F={ROSE, GUMAMELA,..} iii) Let N={vowels in the alphabet} N={ a,e,i,o,u} Statement form- well-defined description of the elements of the set is given and the same are enclosed in curly brackets. For example: (i) The set of odd numbers less than 7 is written as: {odd numbers less than 7}. (ii) A set of football players with ages between 22 years to 30 years. (iii) A set of numbers greater than 30 and smaller than 55. (iv) A set of students in class VII whose weights are more than your weight. Roster method is listing the elements inside a pair of braces { } while Rule Method is a notation for describing a set by indicating the properties that it's members must satisfy and Statement form is a well-defined description of the elements of the set is given ex. A={School days in a week} A={M, T, W, TH, F} ​ {m,t,w,th,f} 1. M__A ​ 2. T____A ​ 3. SU____A ​ 4. SA___A 5. B={Counting numbers less than 5} SOLUTION: B={1,2,3,4}= rule method=B={Counting numbers less than 5} 6. A={EVEN NUMBER} B={ODD #} C={COUNTING NUMBER} FILL IN THE BLANKS WITH ∈ OR ∈ 1. 2___A ​ 2. 7___C ​ 3. -2___C​ 4. 8____B 5. 3___B 6. 5___A ∈ Belongs to ∉ Does not belongs to : or | Such that ∅ Null set or empty set n(A) Cardinal number of the set A ∪ Union of two sets ∩ Intersection of two sets N Set of natural numbers = {1, 2, 3, ……} W Set of whole numbers = {0, 1, 2, 3, ………} I or Z Set of integers = {………, -2, -1, 0, 1, 2, ………} Z+ Set of all positive integers Q Set of all rational numbers Q+ Set of all positive rational numbers R Set of all real numbers R+ Set of all positive real numbers C Set of all complex numbers **These are the different notations in sets generally required while solving various types of problems on sets Symbol Symbol Name Meaning Example {} set a collection of A = {1, 7, 9, 13, 15, elements 23}, B = {7, 13, 15, 21} A∪B union Elements that A ∪ B = {1, 7, 9, 13, belong to set A or 15, 21, 23} set B A∩B intersection Elements that A ∩ B = {7, 13, 15 } belong to both the sets, A and B A⊆B subset subset has few or all {7, 15} ⊆ {7, 13, elements equal to 15, 21} the set A⊄B not subset left set is not a {1, 23} ⊄ B subset of right set A⊂B proper subset / subset has fewer {7, 13, 15} ⊂ {1, 7, strict subset elements than the 9, 13, 15, 23} set A⊃B proper superset / set A has more {1, 7, 9, 13, 15, 23} strict superset elements than set B ⊃ {7, 13, 15, } A⊇B superset set A has more {1, 7, 9, 13, 15, 23} elements or equal to ⊃ {7, 13, 15, 21} the set B Ø empty set Ø={} C = {Ø} P (C) power set all subsets of C C = {4,7}, P(C) = {{}, {4}, {7}, {4,7}} s Given by 2 , s is number of elements in set C A⊅B not superset set X is not a {1, 2, 5} ⊅{1, 6} superset of set Y A=B equality both sets have the {7, 13,15} = {7, 13, same members 15} A \ B or A-B relative complement objects that belong {1, 9, 23} to A and not to B c complement all the objects that We know, U = {1, 2, A do not belong to set 7, 9, 13, 15, 21, 23, A 28, 30} c A = {2, 21, 28, 30} A∆B symmetric objects that belong A ∆ B = {1, 9, 21, difference to A or B but not to 23} their intersection a∈B element of set membership B = {7, 13, 15, 21}, 13 ∈ B (a,b) ordered pair collection of 2 (1, 2) elements x∉A not element of no set membership A = {1, 7, 8, 13, 15, 23}, 5 ∉ A VENN DIAGRAMS What are Venn Diagrams? ​ Pictorial representations of sets represented by closed figures are called set diagrams or Venn diagrams. Venn diagrams are used : ​ to illustrate various operations like union, intersection and difference. We can express the relationship among sets through this in a more significant way. In this, A rectangle is used to represent a universal set. Circles or ovals are used to represent other subsets of the universal set. Union of Sets using Venn Diagram Intersection of Sets using Venn Diagram Disjoint of Sets using Venn Diagram Difference of Sets using Venn Diagram Functions Key Points ​ Functions are a relation between a set of inputs and a set of outputs with the property that each input maps to exactly one output. ​ Typically functions are named with a single letter such as f. ​ Functions can be thought of as a machine in a box that is open on two ends. You put something into one end of the box, it somehow gets changed inside of the box, and then the result pops out the other end. ​ All functions are relations, but not all relations are functions. Key Terms ​ output: The output is the result or answer from a function. ​ relation: A relation is a connection between numbers in one set and numbers in another. ​ function: A function is a relation in which each element of the input is associated with exactly one element of the output.  LESSON 3: Application of Number Theory Number Theory is the study of natural numbers, particularly their divisibility properties. Number theory is a branch of pure mathematics devoted to the study of natural numbers and integers. It is the study of the set of positive whole numbers which are usually called the set of natural numbers. As it holds the foundational place in the discipline, Number theory is also called "The Queen of Mathematics". Divisibility is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Divisibility Theorems For integers a, b, and c it is true that  if a | b and a | c, then a | (b + c) a= 3,b= 6,c=9 ​ Example: ​ 3 | 6 and 3 | 9, so 3 | 15. if a | b, then a | bc for all integers c ​ Example: ​ 5 | 10, so 5 | 20, 5 | 30, 5 | 40 … if a | b and b | c, then a | c ​ Example: ​ 4 | 8 and 8 | 24, so 4 | 24. Prime A number greater than 1 whose only factors are 1 and itself is called prime. Non-primes that are greater than 1 are called composite. The remaining natural numbers 0 and 1 are by convention neither prime nor composite; this allows us to avoid writing “except 0 or 1” in a lot of places later. Division Algorithm In simple terms, ​ Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 £ r < d, such that a = dq + r. In the above equation, d is called the divisor, a is called the dividend, q is called the quotient, and  r is called the remainder. When we divide a number by another number, the division algorithm is, the sum of the product of quotient & divisor and the remainder is equal to the dividend. More clearly, Dividend = Quotient x Divisor + Remainder When we divide a number by another number, we will have the terms dividend, divisor, quotient, and remainder. ​ The number which we divide is called the dividend. ​ The number by which we divide is called the divisor. ​ The result obtained is called the quotient. ​ The number left over is called the remainder. More clearly, Division Algorithm : Division Algorithm Solving Problems using Division Algorithm Problem 1 : What is the dividend, when the divisor is 17, the quotient is 9 and the remainder is 5? (A) 153 (B) 156 (C) 158 (D) None of these Solution : Using division algorithm Dividend = Divisor x quotient + Remainder Dividend = 17 x 9 + 5 Dividend = 153 + 5 Dividend = 158 Hence the required dividend is 158. Problem 2 : When the integer n is divided by 8, the remainder is 3. What is the remainder if 6n is divided by 8? A) 0 ​ B) 1 ​ C) 2 ​ D) 3 ​ E) 4 Solution : Using division algorithm Dividend = Divisor x quotient + Remainder From the given information, we have n = 8q + 3 To find the remainder, when 6n is divided by 8, we multiply 6 on both sides. 6n = 48q + 18 6n = 48q + 16 + 2 Factoring out 8 from 48 and 16, we get 6n = 8(6q + 2) + 2 8(6q + 2) is the multiple of 8 and remainder is 2. Hence we get 2 as remainder, while dividing 6n by 8. Problem 3 : On dividing 12401 by a certain number, we get 76 as the quotient and 13 as the remainder. What is the divisor? Solution : Let x be the divisor. Dividend = 12401, divisor = x, quotient = 76 and remainder = 13. 12401 = 76x + 13 12401 - 13 = 76x Solving for x, we get the divisor. 76x = 12388 x = 12388/76 x = 163 Hence the divisor is 163. Important rules for division: Rule 1: Whenever a number is divided by zero, the resultant (quotient) is always zero. Examples: (i) 0 ÷ 4 = 0 (ii) 0 ÷ 12 = 0 (iii) 0 ÷ 25 = 0 (iv) 0 ÷ 314 = 0 (v) 0 ÷ 225 = 0 (vi) 0 ÷ 7135 = 0 Rule 2: Whenever a number is divided by one, the resultant (quotient) is always the number itself. Examples: (i) 28 ÷ 1 = 28 (ii) 4558 ÷ 1 = 4558 (iii) 335 ÷ 1 = 335 (iv) 9387 ÷ 1 = 9387 (v) 6789754 ÷ 1 = 6789754 Rule 3: Whenever a number is divided by itself, the resultant (quotient) is always 1. Examples: (i) 45 ÷ 45 = 1 (ii) 98 ÷ 98 = 1 (iii) 1371 ÷ 1371 = 1 (iv) 5138 ÷ 5138 = 1 (v) 6758 ÷ 6758 = 1 Greatest Common Divisors It is the largest positive integer that divides each of the integers. Let k be the largest number for which k | m and k | n. Then k is called the greatest common divisor or gcd of m and n, written gcd(m,n) or sometimes just (m,n). A similar concept is the least common multiple (lcm), written lcm(m,n), which is the smallest k such that m | k and n | k. Using prime factorization: 24 = 2 × 2 × 2 × 3 60 = 2 × 2 × 3 × 5 2 × 2 × 3 = 12. Division by primes Greatest Common Divisors Example 1: ​ What is gcd(48, 72) ? The positive common divisors of 48 and 72 are 1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24 How to find Greatest Common Divisor (GCD) There are a few ways to find the greatest common divisor. Below are some of them. ​ Prime Factorization ​ Division by primes ​ Euclidean Algorithm (Euclid's Algorithm) For example, let's try to find the HCM of 24 and 60. Prime Factorization method Using this method, first find the prime factorization of each number. Check the prime factors page to learn how to find prime factors of an integer. 24 = 2 × 2 × 2 × 3 60 = 2 × 2 × 3 × 5 Then we find the common prime factors of these two numbers. 24 = 2 × 2 × 2 × 3 60 = 2 × 2 × 3 × 5 The common prime factors are 2, 2, and 3. The greatest common divisor of 24 and 60 is the product of these common prime factors, i.e. 2 × 2 × 3 = 12. Division by primes First, divide all the numbers by the smallest prime that can divide all of them. The smallest prime that divides 24 or 60 is 2. 2 24 60 12 30 Continue the steps until we can't find any prime number that can divide all the numbers on the right side. 2 24 60 2 12 30 3 6 15 2 5 The GCD is 2 × 2 × 3 = 12. Euclidean Algorithm This algorithm finds GCD by performing repeated division starting from the two numbers we want to find the GCD of until we get a remainder of 0. For our examples, 24 and 60, below are the steps to find GCD using Euclid's algorithm. ​ Divide the larger number by the small one. In this case, we divide 60 by 24 to get a quotient of 2 and a remainder of 12. ​ Next, we divide the smaller number (i.e. 24) by the remainder from the last division (i.e. 12). So 24 divided by 12, we get a quotient of 2 and a remainder of 0. ​ Since we already get a remainder of zero, the last number that we used to divide is the GCD, i.e 12. Let's look at another example, find GCD of 40 and 64. ​ 64 ÷ 40 = 1 with a remainder of 24 ​ 40 ÷ 24 = 1 with a remainder of 16 ​ 24 ÷ 16 = 1 with a remainder of 8 ​ 16 ÷ 8 = 2 with a remainder of 0.​ We stop here since we've already got a remainder of 0. The last number we used to divide is 8 so the GCD of 40 and 64 is 8 Least Common Multiples Is also referred to as the Lowest Common Multiples (LCM) and Least Common Divisor. The smallest positive integer is evenly divisible by both a and b. Examples: Lcm (3,7) =21 Lcm (4,6) = 12 Lcm (5,10) = 10 How to Find Least Common Multiple (LCM) Some methods to find the least common multiple are  ​ Prime Factorization ​ Division by primes ​ Formula For example, let's try to find the LCM of 24 and 60. Prime Factorization method Using this method, first find the prime factorization of each number and write it in index form. Check the prime factors page to learn how to find the prime factors of an integer. 24 = 23 × 3 60 = 22 × 3 × 5 The least common multiple is the product of each prime factor with the greatest power. So for the above example, the LCM is 23 × 3 × 5 = 120. Division by primes First, divide all the numbers by the smallest prime that can divide any of them. The smallest prime that divides 24 or 60 is 2. 2 24 60 12 30 Continue the steps until we have all prime numbers on the left side and at the bottom. 2 24 60 2 12 30 3 6 15 2 5 The LCM is 2 × 2 × 3 × 2 × 5 = 120. Formula If we know the greatest common divisor (GCD) of integers a and b, we can calculate the LCM using the following formula. LCM Using back the same example above, we can find the LCM of 24 and 60 as follows. LCM(24,60)=24×6012=120 Of course, you can use this formula to find the GCD of two integers if you already know the LCM. LESSON 6: Computational Complexity of Algorithms Algorithm An algorithm is a finite set of instructions, if followed, accomplishes a particular task. It is not language-specific, we can use any language and symbols to represent instructions. Problem Solving: Main Steps 1.​ Problem definition  2.​ Algorithm design / Algorithm specification 3.​ Algorithm analysis 4.​ Implementation 5.​ Testing 6.​ [Maintenance] Problem Definition What is the task to be accomplished? Calculate the average of the grades for a given student Understand the talks given out by politicians and translate them into Chinese What are the time/space/speed/performance requirements? The criteria of an algorithm 1.​ Input: Zero or more inputs are externally supplied to the algorithm. 2.​ Output: At least one output is produced by an algorithm. 3.​ Definiteness: Each instruction is clear and unambiguous. 4.​ Finiteness: In an algorithm, it will be terminated after a finite number of steps for all different cases. 5.​ Effectiveness: Each instruction must be very basic, so the purpose of those instructions must be very clear to us. Analysis of algorithms Algorithm analysis is an important part of computational complexities. The complexity theory provides the theoretical estimates for the resources needed by an algorithm to solve any computational task. Analysis of the algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of the analysis of the algorithm is the required time or performance. Complexities of an Algorithm The complexity of an algorithm computes the amount of time and spaces required by an algorithm for an input of size (n). The complexity of an algorithm can be divided into two types. The time complexity and the space complexity. Time Complexity of an Algorithm The time complexity is defined as the process of determining a formula for the total time required for the execution of that algorithm. This calculation is totally independent of the implementation and programming language. Space Complexity of an Algorithm Space complexity is defined as the process of defining a formula for the prediction of how much memory space is required for the successful execution of the algorithm. The memory space is generally considered the primary memory. The term "analysis of algorithms" was coined by Donald Knuth. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity. The Need for Analysis Analysis of the algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of the analysis of algorithms is the required time or performance. Generally, we perform the following types of analysis − · Worst-case − The maximum number of steps taken on any instance of size a. · Best-case − The minimum number of steps taken on any instance of size a. · Average case − An average number of steps taken on any instance of size a. Amortized − A sequence of operations applied to the input of size averaged over time A complete analysis of the running time of an algorithm involves the following steps: · Implement the algorithm completely. · Determine the time required for each basic operation. · Identify unknown quantities that can be used to describe the frequency of execution of the basic operations. · Develop a realistic model for the input to the program. · Analyze the unknown quantities, assuming the modeled input. · Calculate the total running time by multiplying the time by the frequency for each operation, then adding all the products. Classical algorithm analysis on early computers could result in exact predictions of running times. Modern systems and algorithms are much more complex, but modern analyses are informed by the idea that exact analyses of this sort could be performed in principle.  LESSON 7: Graphs and its Applications graph theory, is a branch of mathematics concerned with networks of points connected by lines. The subject of graph theory had its beginnings in recreational math problems (see number game), but it has grown into a significant area of mathematical research, with applications in chemistry, operations research, social sciences, and computer science The history of graph theory may be specifically traced to 1735 when the Swiss mathematician Leonhard Euler solved the Königsberg bridge problem. The Königsberg bridge problem was an old puzzle concerning the possibility of finding a path over every one of seven bridges that span a forked river flowing past an island—but without crossing any bridge twice. Euler argued that no such path exists. His proof involved only references to the physical arrangement of the bridges, but essentially he proved the first theorem in graph theory. As used in graph theory, the term graph does not refer to data charts, such as line graphs or bar graphs. Instead, it refers to a set of vertices (that is, points or nodes) and edges (or lines) that connect the vertices. When any two vertices are joined by more than one edge, the graph is called a multigraph. A graph without loops and with at most one edge between any two vertices is called a simple graph. Unless stated otherwise, the graph is assumed to refer to a simple graph. When each vertex is connected by an edge to every other vertex, the graph is called a complete graph. When appropriate, a direction may be assigned to each edge to produce what is known as a directed graph, or digraph. Eulerian circuit A graph is a collection of vertices, or nodes, and edges between some or all of the vertices. When there exists a path that traverses each edge exactly once such that the path begins and ends at the same vertex, the path is known as an Eulerian circuit and the graph is known as an Eulerian graph. Eulerian refers to the Swiss mathematician Leonhard Euler, who invented graph theory in the 18th century. An important number associated with each vertex is its degree, which is defined as the number of edges that enter or exit from it. Thus, a loop contributes 2 to the degree of its vertex. For instance, the vertices of the simple graph shown in the diagram all have a degree of 2, whereas the vertices of the complete graph shown are all of degree 3. Knowing the number of vertices in a complete graph characterizes its essential nature. For this reason, complete graphs are commonly designated Kn, where n refers to the number of vertices, and all vertices of Kn have degree n − 1. (Translated into the terminology of modern graph theory, Euler’s theorem about the Königsberg bridge problem could be restated as follows: If there is a path along edges of a multigraph that traverses each edge once and only once, then there exist at most two vertices of odd degree; furthermore, if the path begins and ends at the same vertex, then no vertices will have odd degree.) Another problem of topological graph theory is the map-coloring problem. This problem is an outgrowth of the well-known four-colour map problem, which asks whether the countries on every map can be coloured by using just four colours in such a way that countries sharing an edge have different colours. Asked originally in the 1850s by Francis Guthrie, then a student at University College London, this problem has a rich history filled with incorrect attempts at its solution. In an equivalent graph-theoretic form, one may translate this problem to ask whether the vertices of a planar graph can always be coloured by using just four colours in such a way that vertices joined by an edge have different colours. The result was finally proved in 1976 by using computerized checking of nearly 2,000 special configurations. Interestingly, the corresponding colouring problem concerning the number of colours required to colour maps on surfaces of higher genus was completely solved a few years earlier; for example, maps on a torus may require as many as seven colours. This work confirmed that a formula of the English mathematician Percy Heawood from 1890 correctly gives these colouring numbers for all surfaces except the one-sided surface known as the Klein bottle, for which the correct colouring number had been determined in 1934. Among the current interests in graph theory are problems concerning efficient algorithms for finding optimal paths (depending on different criteria) in graphs. Two well-known examples are the Chinese postman problem (the shortest path that visits each edge at least once), which was solved in the 1960s, and the traveling salesman problem (the shortest path that begins and ends at the same vertex and visits each edge exactly once), which continues to attract the attention of many researchers because of its applications in routing data, products, and people. Work on such problems is related to the field of linear programming, which was founded in the mid-20th century by the American mathematician George Dantzig. Hamiltonian circuit A directed graph in which the path begins and ends on the same vertex (a closed loop) such that each vertex is visited exactly once is known as a Hamiltonian circuit. The 19th-century Irish mathematician William Rowan Hamilton began the systematic mathematical study of such graphs. K5 is not a planar graph, because there does not exist any way to connect every vertex to every other vertex with edges in the plane such that no edges intersect. planar graph and nonplanar graph compared With fewer than five vertices in a two-dimensional plane, a collection of paths between vertices can be drawn in the plane such that no paths intersect. With five or more vertices in a two-dimensional plane, a collection of nonintersecting paths between vertices cannot be drawn without the use of a third dimension. K3,2 A bipartite map, such as K3,2, consists of two sets of points in the two-dimensional plane such that every vertex in one set (the set of red vertices) can be connected to every vertex in the other set (the set of blue vertices) without any of the paths intersecting. Dudeney puzzle The English recreational problemist Henry Dudeney claimed to have a solution to a problem that he posed in 1913 that required each of three houses to be connected to three separate utilities such that no utility service pipes intersected. Dudeney's solution involved running a pipe through one of the houses, which would not be considered a valid solution in graph theory. In a two-dimensional plane, a collection of six vertices (shown here as the vertices in the homes and utilities) that can be split into two completely separate sets of three vertices (that is, the vertices in the three homes and the vertices in the three utilities) is designated a K3,3 bipartite graph. The two parts of such graphs cannot be interconnected within the two-dimensional plane without intersecting some paths. Encyclopædia Britannica, Inc. Graph A graph is a pictorial and mathematical representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices or nodes and the links that connect the vertices are called edges or arcs or lines. In other words, a graph is an ordered pair G = (V, E) where, G specifies the graph. V is the vertex-set whose elements are called the vertices, or nodes of the graph. This set is often denoted by V(G) or just V. E is the edge-set whose elements are called the edges, or connections between vertices of the graph. This set is often denoted by E(G) or just E. Graph Theory Graph theory is the sub-field of mathematics and computer science which deals with graphs, diagrams that contain points and lines and which often pictorially represent mathematical truths. In short, graph theory is the study of the relationship between edges and vertices. Fundamental Concepts Some of the basic fundamental concepts of graph theory are: 1. Point A point is a particular position that is located in space. Space can be one-dimensional, two-dimensional, or three-dimensional space. A dot is used to represent a point in a graph and it is labeled by alphabet, numbers, or alphanumeric values. Example Fundamental Concepts Here, the dot is a point labeled by 'p'. 2. Line Two points are connected to each other through a line. A line is a connection between two points. It is represented by a solid line. Example Fundamental Concepts Here, 'A' and 'B' are the points, and links between two points are called a line. 3. Vertex A vertex is a synonym of a point in a graph i.e. one of the points on which the graph is defined and which may be connected by lines/edges is called a vertex. Vertex is also called "node", "point" or "junction". A vertex is denoted by alphabets, numbers, or alphanumeric values. Example Fundamental Concepts Here, the point is the vertex labeled with an alphabet 'v'. 4. Edge Edge is the connection between two vertices. Each edge connects one vertex to another vertex in the graph. Without a vertex, an edge cannot be formed. It is also called line, branch, link, or arc. Edge can either be directed or undirected. A directed edge is an edge that points from one vertex to another, and an undirected edge has no direction. If there is a directed edge from vertex A to B, and a directed edge from B to A, this would essentially be equivalent to an undirected edge connecting A and B. Example Fundamental Concepts Here, 'A' and 'B' are the vertices and the link 'AB' between them is called an edge. Graph Graph specifies a "function graph" or "graph of a function" i.e. a plot. In mathematics terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. A graph G is defined as G = {V, E} where V is a set of all vertices or points and E is the set of all edges in the graph. Example 1 Fundamental Concepts In the above example, A, B, C, D, and E are the vertices of the graph, and AB, BC, CA and AD are the edges of the graph. Example 2 Fundamental Concepts In the above example, G1, G2, and G3 are graphs. Types of Graphs Though there are a lot of different types of graphs depending upon the number of vertices, a number of edges, interconnectivity and their overall structure, some of such common types of graphs are as follows: 1. Null Graph A null graph is a graph in which there are no edges between its vertices. A null graph is also called an empty graph. Example 2. Trivial Graph A trivial graph is a graph that has only one vertex. Example In the above graph, there is only one vertex 'v' without any edge. Therefore, it is a trivial graph. 3. Simple Graph A simple graph is an undirected graph with no parallel edges and no loops. In a simple graph that has n vertices, the degree of every vertex is at most n -1. Example In the above example, the First graph is not a simple graph because it has two edges between the vertices A and B and it also has a loop. The second graph is a simple graph because it does not contain any loop and parallel edges. 4. Undirected Graph An undirected graph is a graph whose edges are not directed. Example In the above graph since there are no directed edges, therefore it is an undirected graph. 5. Directed Graph A directed graph is a graph in which the edges are directed by arrows. The directed graph is also known as digraphs. Example In the above graph, each edge is directed by the arrow. A directed edge has an arrow from A to B, which means A is related to B, but B is not related to A. 6. Complete Graph A graph in which every pair of vertices is joined by exactly one edge is called a complete graph. It contains all possible edges. A complete graph with n vertices contains exactly nC2 edges and is represented by Kn. Example In the above example, since each vertex in the graph is connected with all the remaining vertices through exactly one edge, therefore, both graphs are complete graphs. 7. Connected Graph A connected graph is a graph in which we can visit from any one vertex to any other vertex. In a connected graph, at least one edge or path exists between every pair of vertices. Example In the above example, we can traverse from any one vertex to any other vertex. It means there exists at least one path between every pair of vertices therefore, it is a connected graph. 8. Disconnected Graph A disconnected graph is a graph in which any path does not exist between every pair of vertices. Example The above graph consists of two independent components which are disconnected. Since it is not possible to visit from the vertices of one component to the vertices of other components, therefore, it is a disconnected graph. 9. Regular Graph A regular graph is a graph in which the degree of all the vertices is the same. If the degree of all the vertices is k, then it is called a k-regular graph. Example In the above example, all the vertices have degree 2. Therefore they are called 2- Regular graphs. 10. Cyclic Graph A graph with 'n' vertices (where, n>=3) and 'n' edges forming a cycle of 'n' with all its edges are known as a cycle graph. A graph containing at least one cycle in it is known as a cyclic graph. In the cycle graph, the degree of each vertex is 2. The cycle graph which has n vertices is denoted by Cn. Example 1 In the above example, all the vertices have degree 2. Therefore they all are cyclic graphs. Example 2 Since the above graph contains two cycles in it, therefore, it is a cyclic graph. 11. Acyclic Graph A graph that does not contain any cycle in it is called an acyclic graph. Example Since the above graph does not contain any cycle in it therefore, it is an acyclic graph. 12. Bipartite Graph A bipartite graph is a graph in which the vertex set can be partitioned into two sets such that edges only go between sets, not within them. A graph G (V, E) is called a bipartite graph if its vertex-set V(G) can be decomposed into two non-empty disjoint subsets V1(G) and V2(G) in such a way that each edge e ∈ E(G) has its one last joint in V1(G) and other last points in V2(G). The partition V = V1 ∪ V2 is known as the bipartition of G. Example 1 Example 2 13. Complete Bipartite Graph A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge. A complete bipartite graph is a bipartite graph that is complete. Complete Bipartite graph = Bipartite graph + Complete graph Example The above graph is known as K4,3. 14. Star Graph A star graph is a complete bipartite graph in which n-1 vertices have degree 1 and a single vertex have a degree (n -1). This exactly looks like a star where (n - 1) vertices are connected to a single central vertex. A star graph with n vertices is denoted by Sn. Example In the above example, out of n vertices, all the (n-1) vertices are connected to a single vertex. Hence, it is a star graph. 15 Weighted Graph A weighted graph is a graph whose edges have been labeled with some weights or numbers. The length of a path in a weighted graph is the sum of the weights of all the edges in the path. Example 16. Multi-graph A graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself (loop) is called a multi-graph. Example In the above graph, vertex-set B and C are connected with two edges. Similarly, vertex sets E and F are connected with 3 edges. Therefore, it is a multi-graph. 17. Planar Graph A planar graph is a graph that we can draw in a plane in such a way that no two edges of it cross each other except at a vertex to which they are incident. Example The above graph may not seem to be planar because it has edges crossing each other. But we can redraw the above graph. The three-plane drawings of the above graph are: The above three graphs do not consist of two edges crossing each other and therefore, all the above graphs are planar. 18. Non - Planar Graph A graph that is not a planar graph is called a non-planar graph. In other words, a graph that cannot be drawn without at least one pair of its crossing edges is known as a non-planar graph. Example The above graph is a non - planar graph. Applications of Graph Theory Graph Theory is used in a vast area of science and technologies. Some of them are given below: 1. Computer Science In computer science, graph theory is used for the study of algorithms like: ​ Dijkstra's Algorithm ​ Prims's Algorithm ​ Kruskal's Algorithm ​ Graphs are used to define the flow of computation. ​ Graphs are used to represent networks of communication. ​ Graphs are used to represent data organization. ​ Graph transformation systems work on rule-based in-memory manipulation of graphs. Graph databases ensure transaction-safe, persistent storing and querying of graph-structured data. ​ Graph theory is used to find the shortest path in a road or a network.  ​ In Google Maps, various locations are represented as vertices or nodes, and the roads are represented as edges, and graph theory is used to find the shortest path between two nodes. 2. Electrical Engineering In Electrical Engineering, graph theory is used in designing circuit connections. These circuit connections are named topologies. Some topologies are series, bridge, star, and parallel topologies. 3. Linguistics ​ In linguistics, graphs are mostly used for parsing a language tree and grammar of a language tree. ​ Semantics networks are used within lexical semantics, especially as applied to computers, modeling word meaning is easier when a given word is understood in terms of related words. ​ Methods in phonology (e.g. theory of optimality, which uses lattice graphs) and morphology (e.g. morphology of finite-state, using finite-state transducers) are common in the analysis of language as a graph. 4. Physics and Chemistry ​ In physics and chemistry, graph theory is used to study molecules. ​ The 3D structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms.  ​ Statistical physics also uses graphs. In this field, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. ​ Graphs are also used to express the micro-scale channels of porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores. ​ The graph is also helpful in constructing the molecular structure as well as a lattice of the molecule. It also helps us to show the bond relation between atoms and molecules, also helps in comparing the structure of one molecule to another. 5. Computer Network ​ In a computer network, the relationships among interconnected computers within the network, follow the principles of graph theory. ​ Graph theory is also used in network security. ​ We can use the vertex coloring algorithm to find a proper coloring of the map with four colors. ​ Vertex coloring algorithm may be used for assigning at most four different frequencies for any GSM (Grouped Special Mobile) mobile phone networks. 6. Social Sciences ​ Graph theory is also used in sociology. For example, to explore rumor spreading, or to measure actors' prestige notably through the use of social network analysis software.  ​ Acquaintanceship and friendship graphs describe whether people know each other or not. ​ In the influence graphs model, certain people can influence the behavior of others. ​ In collaboration graphs model to check whether two people work together in a particular way, such as acting in a movie together. 7. Biology ​ Nodes in biological networks represent bimolecular such as genes, proteins or metabolites, and edges connecting these nodes indicate functional, physical or chemical interactions between the corresponding bimolecular. ​ Graph theory is used in transcriptional regulation networks. ​ It is also used in Metabolic networks. ​ In PPI (Protein-Protein interaction) networks graph theory is also useful. ​ Characterizing drug - drug-target relationships. 8. Mathematics In mathematics, operational research is an important field. Graph theory provides many useful applications in operational research LESSON 8: Mathematical reasoning and induction Terminologies  Axiom - is a basic assumption about mathematical structures that needs no proof. Proof – use to demonstrate that a particular statement is true. It consists of a sequence of statements that form an argument. Theorem – is a statement that can be shown to be true. Rules of Inference – steps that connect statements in such a sequence. Terminologies Lemma – a simple theorem used as an intermediate result in proof of another theorem Corollary - is a proposition that follows directly from a theorem that has been proven. Conjecture – is a statement whose truth value is unknown. Once it’s proven, it becomes a theorem Rule of Inference In order to define the notion of proof rigorously, we would have to define a formal language in which to express statements very precisely and we would have to set up a proof system in terms of axioms and proof rules (also called inference rules). Rule of Inference The general form of a rule of inference is: Rule of Inference Arguments consists of one or more hypotheses and a conclusion. we say that an argument is valid if whenever all its hypotheses are true, its conclusion is also true.  Arguments Example 1: If 101 is divisible by 3, then 1012 is divisible by 9. 101 is divisible by 3. Consequently, 1012 is divisible by 9.” Although the argument is valid, its conclusion is incorrect, because one of the hypotheses is false (“101 is divisible by 3.”). If in the above argument we replace 101 with 102, we could correctly conclude that 1022 is divisible by 9. Proving Theorems 1.​ Direct Proof - an implication p®q can be proven by showing that if p is true, then q is also true. Example: Give a direct proof of the theorem “If n is odd, then n2 is odd.” Proving Theorems B. Indirect Proof - an implication p®q is equivalent to its contra-positive Øq ® Øp. Therefore, we can prove p®q by showing that whenever q is false, then p is also false. Example: Give an indirect proof of the theorem “If 3n + 2 is odd, then n is odd.” Induction The principle of mathematical induction is a useful tool for proving that a certain predicate is true for all natural numbers. It cannot be used to discover theorems, but only to prove them Induction If we have a propositional function P(n), and we want to prove that P(n) is true for any natural number n, we do the following:  Show that P(0) is true. ​ (basis step) Show that if P(n) then P(n + 1) for any nÎN. ​ (inductive step) Then P(n) must be true for any nÎN. ​ (conclusion) LESSON 9: Probability, Statistics, and Application DATA MANAGEMENT: the development, execution, and supervision of plans, policies, programs, and practices that control, protect, deliver and enhance the value of data and information assets. Statistics is a branch of mathematics dealing with the collection, organization, presentation, analysis, and interpretation of data. Objective: Use a variety of statistical tools to process and manage numerical data. 1.​ Data Gathering Different methods are used in gathering or collecting data. These are: 1.1. Direct or interview method- a person-to-person encounter between the source of information, the interviewee, and the one who gathers information. 1.2. Indirect or questionnaire method- the technique in which a questionnaire is used to elicit the information or data needed. 1.3. Registration method- obtains data from the records of government agencies authorized by law to keep such data or information and made it available to researchers 1.4. Observation Method - the technique in which data particularly pertaining to the behaviors of individuals or group of individuals during the given situation are best obtained through observation 1.5. Experimental Method - a system is used to gather data from the result of performed series on some controlled and experimental variables. This is commonly used in scientific inquiries. 2. Data Organization - data collected can be classified according to the scale of measurement used. Four levels of Measurement:( from lowest to higher scale)  2.1. Nominal scale - assigns names or labels to observation in purely arbitrary sequence. The labels are used to classify the respondents or objects without ordering. 2.2 Ordinal scale - assigns numbers or labels to observation with implied ordering. 2.3 Interval scale - assigns a real number to observation to reflect the distance between the rank position of the respondents or objects in equal units. ​ ​ ​ 2.4. Ratio scale - assigns a number to observations to reflect the existence of true absolute zero point as its origin. Note: the data set obtained using the interval and ratio scales is called MEASURED DATA. WAYS OR FORMS TO PRESENT DATA: 1.​ TEXTUAL PRESENTATION OF DATA. In the textual presentation, data are described within the text. Case 1: In a bandh call given on 08 September 2005 protesting the hike in prices of petrol and diesel, 5 petrol pumps were found open and 17 were closed whereas 2 schools were closed and the remaining 9 schools were found open in a town of Bihar. 2.​ TABULAR PRESENTATION OF DATA. The most simple way of conceptualizing a table is to present the data in rows and columns along with some explanatory notes. Tabulation can be done using one-way, two-way, or three-way classification depending upon the number of characteristics involved. A good table should essentially have the following: (i) Table Number. Table number is assigned to a table for identification purposes. If more than one table is presented, it is the table number that distinguishes one table from another. It is given at the top or at the beginning of the title of the table. Generally, table numbers are whole numbers in ascending order if there are many tables in a book. Subscripted numbers, like 1.2, 3.1, etc., are also used for identifying the table according to its location. For example, Table 4.5 should be read as the fifth table of the fourth chapter, and so on (See Table 4.5). (ii) Title. The title of a table narrates the contents of the table. It has to be clear, brief, and carefully worded so that the interpretations made from the table are clear and free from ambiguity. It finds a place at the head of the table succeeding the table number or just below it (See Table 4.5). (iii) Captions or Column Headings At the top of each column in a table a column designation is given to explain the figures of the column. This is called caption or column heading (See Table 4.5). (iv) Stubs or Row Headings Like a caption or column heading, each row of the table has to be given a heading. The designations of the rows are also called stubs or stub items, and the complete left column is known as the stub column. A brief description of the row headings may also be given at the left-hand top in the table. (See Table 4.5). (v) Body of the Table Body of a table is the main part and it contains the actual data. The location of any figure/data in the table is fixed and determined by the row and column of the table. (vi) Unit of Measurement The unit of measurement of the figures in the table (actual data) should always be stated along with the title. If different units are there for rows or columns of the table, these units must be stated along with ‘stubs’ or ‘captions’. If figures are large, they should be rounded up and the method of rounding should be indicated (See Table 4.5).  (vii) Source It is a brief statement or phrase indicating the source of data presented in the table. If more than one source is there, all the sources are to be written in the source. The source is generally written at the bottom of the table. (See Table 4.5). (viii)Note Note is the last part of the table. 3.​ DIAGRAMMATIC PRESENTATION OF DATA This is the third method of presenting data. This method provides the quickest understanding of the actual situation to be explained by data in comparison to tabular or textual presentations. Diagrams may be less accurate but are much more effective than tables in presenting the data. There are various kinds of diagrams in common use. Amongst them, the important ones are the following: (i) Geometric diagram (ii) Frequency diagram (iii) Arithmetic line graph Geometric Diagram. Bar diagrams and pie diagrams come in the category of geometric diagrams. The bar diagrams are of three types — simple, multiple, and component bar diagrams. Bar Diagram. Simple Bar Diagram. Bar diagram comprises a group of equispaced and equi width rectangular bars for each class or category of data. The height or length of the bar reads the magnitude of the data. The lower end of the bar touches the baseline such that the height of a bar starts from zero units. Bars of a bar diagram can be visually compared by their relative height and accordingly data are comprehended quickly. Data for this can be of frequency or non-frequency type. In non-frequency type data a particular characteristic, say production, yield, population, etc. at various points of time or of different states are noted and corresponding bars are made of the respective heights according to the values of the characteristic to construct the diagram. 3. DATA ANALYSIS AND INTERPRETATION - the process of making sense of numerical data that has been collected, analyzed, and presented. A common method of describing the characteristics of individual objects or groups of individuals under the study is known as DESCRIPTIVE STATISTICS while analyzing and interpreting data is known as INFERENTIAL STATISTICS. 3 methods of describing a set of values: The Measures of Central Tendency, Measures of Dispersion, and measure of Skewness and Kurtosis 1.​ The measures of central tendency : A measure of central tendency (also referred to as measures of center or central location) is a summary measure that attempts to describe a whole set of data with a single value that represents the middle or center of its distribution. There are three main measures of central tendency: the mode, the median, and the mean. Each of these measures describes a different indication of the typical or central value in the distribution. ​ Mean- Sum of all observations divided by the total number of observations. ​ Median- The middle or central value in an ordered set. ​ Mode- The most frequently occurring value in a data set. FOR GROUPED DATA: A frequency distribution is an overview of all distinct values in some variable and the number of times they occur. That is, a frequency distribution tells how frequencies are distributed overvalues. Frequency distributions are mostly used for summarizing categorical variables. * TO GET THE (lb): Score - 0.5 TO GET THE CLASS MARK: ADD THE SCORES / 2 Mode Consider this dataset showing the retirement age of 11 people, in whole years: 54, 54, 54, 55, 56, 57, 57, 58, 58, 60, 60  In some cases, particularly where the data are continuous, the distribution may have no mode at all (i.e. if all values are different). In cases such as these, it may be better to consider using the median or mean, or group the data into appropriate intervals, and find the modal class. If two or more values appear with the same frequency, each is a mode. The downside to using the mode as a measure of central tendency is that a set of data may have no mode, or it may have more than one mode. However, the same set of data will have only one mean and only one median. ​ The word modal is often used when referring to the mode of a data set. ​ If a data set has only one value that occurs most often, the set is called unimodal. ​ A data set that has two values that occur with the same greatest frequency is referred to as bimodal. ​ When a set of data has more than two values that occur with the same greatest frequency, the set is called multimodal. When determining the mode of a data set, calculations are not required, but keen observation is a must. The mode is a measure of central tendency that is simple to locate, but it is not used much in practical applications. Problem Find the mode of the following data: 76, 81, 79, 80, 78, 83, 77, 79, 82, 75  There is no need to organize the data unless you think that it would be easier to locate the mode if the numbers were arranged from least to greatest. In the above data set, the number 79 appears twice, but all the other numbers appear only once. Since 79 appears with the greatest frequency, it is the mode of the data values. Remember that the mode can be determined for qualitative data as well as quantitative data, but the mean and the median can only be determined for quantitative data. Example  Problem You begin to observe the color of clothing your employees wear. Your goal is to find out what color is worn most frequently so that you can offer company shirts to your employees. Monday: Red, Blue, Black, Pink, Green, and Blue Tuesday: Green, Blue, Pink, White, Blue, and Blue Wednesday: Orange, White, White, Blue, Blue, and Red Thursday: Brown, Black, Brown, Blue, White, and Blue Friday: Blue, Black, Blue, Red, Red, and Pink What is the mode of the colors above? The color blue was worn 11 times during the week. All other colors were worn with much less frequency in comparison to the color blue. MEAN The mean (or arithmetic mean) often called the average is most likely one of the measures of central tendency that you are most familiar with. It is also known as average. Mean is simply the sum of all the components in a group or collection, divided by the number of components. We generally denote the mean of a given data-set by x̄, pronounced “x bar”. The formula to calculate the mean for ungrouped data to represent it as the measure is given as, For a set of observations: Mean = Sum of the terms/Number of terms For a set of grouped data: Mean, x̄ = Σfx/Σf where,  ​ x̄ = the mean value of the set of given data. ​ f = frequency of each class ​ x = mid-interval value of each class Example1: The weights of 8 boys in kilograms: 45, 39, 53, 45, 43, 48, 50, 45. Find the mean weight for the given set of data. Therefore, the mean weight of the group: Mean = Sum of the weights/Number of boys = (45 + 39 + 53 + 45 + 43 + 48 + 50 + 45)/8 = 368/8 = 46 Thus, the mean weight of the group is 46 kilograms. Example2 Mark operates Technology Titans, a Step 1: Add the numbers to determine the total Web site service that employs 8 people. age of the workers. Find the mean age of his workers if the ages of the employees are as follows: 55 + 63 + 34 + 59 + 29 + 46 + 51 + 41 = 378 55, 63, 34, 59, 29, 46, 51, 41 Step 2: Divide the total by the number of months. MEDIAN The median is the number that falls in the middle position once the data has been organized. Organized data means the numbers are arranged from smallest to largest or from largest to smallest. The median for an odd number of data values is the value that divides the data into two halves. If n represents the number of data values and n is an odd number, then the median will be found in the position. Example Problem Find the median of the following data: 12, 2, 16, 8, 14, 10, 6 Step 1: Organize the data, or arrange the numbers from smallest to largest. 2, 6, 8, 10, 12, 14, 16 Step 2: Since the number of data values is odd, the median will be found in the position. Step 3: In this case, the median is the value that is found in the fourth position of the organized data. 2, 6, 8, 10, 12, 14, 16 Example Proble Find the median of the following data: m 7, 9, 3, 4, 11, 1, 8, 6, 1, 4 Step 1: Organize the data, or arrange the numbers from smallest to largest. 1, 1, 3, 4, 4, 6, 7, 8, 9, 11 Step 2: Since the number of data values is even, the median will be the mean value of the numbers found before and after the position. Step 3: The number found before the 5.5 position is 4 and the number found after the 5.5 positions is 6. Now, you need to find the mean value. 1, 1, 3, 4, 4, 6, 7, 8, 9, 11  Types of Measures of Dispersion There are two main types of dispersion methods in statistics which are:  ​ Absolute Measure of Dispersion ​ Relative Measure of Dispersion Absolute Measure of Dispersion An absolute measure of dispersion contains the same unit as the original data set. Absolute dispersion method expresses the variations in terms of the average of deviations of observations like standard or mean deviations. It includes range, standard deviation, quartile deviation, etc. The types of absolute measures of dispersion are: 1.​ Range: It is simply the difference between the maximum value and the minimum value given in a data set. Example: 1, 3,5, 6, 7 => Range = 7 -1= 6 2.​ Variance: Deduct the mean from each data in the set then squaring each of them and adding each square and finally dividing them by the total no of values in the data set is the variance. Variance (σ2)=∑(X−μ)2/N 3.​ Standard Deviation: The square root of the variance is known as the standard deviation i.e. S.D. = √σ. 4.​ Quartiles and Quartile Deviation: The quartiles are values that divide a list of numbers into quarters. The quartile deviation is half of the distance between the third and the first quartile. 5.​ Mean and Mean Deviation: The average of numbers is known as the mean and the arithmetic mean of the absolute deviations of the observations from a measure of central tendency is known as the mean deviation (also called mean absolute deviation). Relative Measure of Dispersion The relative measures of dispersion are used to compare the distribution of two or more data sets. This measure compares values without units. Common relative dispersion methods include: 1.​ Coefficient of Range 2.​ Coefficient of Variation 3.​ Coefficient of Standard Deviation 4.​ Coefficient of Quartile Deviation 5.​ Coefficient of Mean Deviation Coefficient of Dispersion The coefficients of dispersion are calculated (along with the measure of dispersion) when two series are compared, that differ widely in their averages. The dispersion coefficient is also used when two series with different measurement units are compared. It is denoted as C.D.  The common coefficients of dispersion are: C.D. In Terms of Coefficient of dispersion Range C.D. = (Xmax – Xmin) ⁄ (Xmax + Xmin) Quartile Deviation C.D. = (Q3 – Q1) ⁄ (Q3 + Q1) Standard Deviation (S.D.) C.D. = S.D. ⁄ Mean Mean Deviation C.D. = Mean deviation/Average https://www.youtube.com/watch?v=BiLIcCtXmm0 SUGGESTED READING/S: Guide to Discrete Mathematics by Gerard O’ Regan; Discrete Mathematics by Marcel B. Finan; Discrete Mathematical structures by Ragesh Jaiswal, CSE,IIT Delhi; Kenneth H. Rosen; Discrete Mathematics and Its Applications, 7th Edition, McGraw Hill, 2012; courses.lumenlearning.com/boundless-algebra/chapter/introduction-to-functions/;https://www.javatpoi nt.com/graph-theory-applications;https://sciencerack.com/scheduling-algorithm/ TEST AND APPLY YOUR KNOWLEDGE: Pls visit Google classroom: https://classroom.google.com/c/Mzc3OTk0NzM4NDA4?cjc=yhfwwyv