59326111118641-Math-in-the-Modern-World.pptx

Topic Outline I. Nature of Mathematics II. Speaking Mathematically III. Problem-Solving IV. Statistics V. Logic VI. Mathematical Systems VII. Graphs Textbook: Aufmann , R., Lockwood, J., Nation, R., Clegg, D., Epp , S., Abad, E. Jr. Mathematics in the Modern World . (Rex Book Store, Inc., Manila, Philippines). 2018.

I. Nature of Mathematics

Fibonacci Sequence

Rabbit Problem

Questions: 1. What is the pattern of the birth of rabbits? 2. How many pairs of rabbits will be at 6 th month? Answers: 1. The number of pairs of rabbits for any month after the first 2 months can be determined by adding the number of pair of rabbits in each of the 2 previous months 2. In the 4 th month, there are 3 pairs of rabbits and in the 5 th month there are 5 pairs. Thus, there will be 8 pairs (5+3) at the 6 th month.

Fibonacci Sequence: 1,1,2,3,5,8,13,21,... Note: A recursive definition for a sequence is one in which each successive term of the sequence is defined by using some of the preceding terms. Recursive Definition for the Fibonacci Sequence: Example: Find the first ninth term of the Fibonacci sequence using the recursive definition .

Binet’s Formula The following formula known as Binet’s formula finds the n th Fibonacci number: n int is abbreviation for “nearest integer of”. Jacques Philippe Marie Binnet – French mathematician (1786-1856)

The Golden Ratio The ratios of successive Fibonacci numbers approach the number Φ (Phi), also known as the golden ratio. This is approximately 1.618 . Example : 1/1 = 1.000 13/8 = 1.625 2/1 = 2.000 21/13 ≈ 1.615 3/2 = 1.500 34/21 ≈ 1.619 5/3 ≈ 1.667 55/34 ≈ 1.618 8/5 = 1.600 89/55 ≈ 1.618

Fibonacci sequence has many interesting properties. Among these is that these pattern is very visible in nature. Some of nature’s most beautiful patterns, like the spiral arrangement of sunflower seeds, the number of petals in a flower, and the shape of a snail’s shell all contain Fibonacci numbers.

Shapes and figures that bear this proportion are generally considered to be aesthetically pleasing. As such, this ratio is visible in many works of art and architecture such as in the Mona Lisa, the Notre Dame Cathedral, and the Parthenon. In fact, the human DNA molecule also contains Fibonacci numbers, being 34 angstroms long by 21 angstroms wide for each full cycle of the double helix spiral. This approximates the Golden Ratio at a value of 1.619 (1 angstrom = 10 -10 meter or 0.1 nanometer ).

Partner Activity 1 2

3 4

5 6

7 8

9 10

Importance of Mathematical Language II. Speaking Mathematically

Characteristics of Mathematical Language

Some Difficulties in Mathematical Language

A variable in mathematics can be thought of as a placeholder when you want to talk about something, either: 1.) you imagine that it has one or more values but you do not know what they are; 2.) you want whatever you say about it to be equally true for all elements in a given set. Example: Is there a real number whose square is positive one? Example: Any prime number greater than two is odd.

Example: Express the following using variables. 1.) Are there numbers with the property that the sum of their squares equals the square of their sum? 2.) Given any real number, its square is nonnegative.

Mathematical Statements A universal statement says that a certain property is true for all elements in a set. Example: All positive real numbers are greater than zero. A conditional statement says that if one thing is true then some other thing also has to be true. Example: If 15 is divisible by 6 then 15 is divisible by 2. An existential statement says that there is at least one thing for which a certain property is true. Example: There is a prime number which is even.

Other Types of Statements A universal conditional statement is both universal and conditional. Example: For all animals x , if x is a dog then x is a mammal. Example: If x is a dog then x is a mammal. A universal existential statement is a statement whose first part says that a certain property is true for all objects of a given type, and its second part asserts the existence of something. Example: For every real number r , there is an additive inverse for r . An existential universal statement is a statement whose first part asserts that a certain object exists and its second part says that the object satisfies a certain property for all things of a certain kind. Example: There is a positive integer that is less than or equal to every positive integer.

Variable: (first use of a variable) Is there a real number x such that x 2 = -1? (second use of a variable) For any integer x , x 2 ≥ x . Universal Statement: For every whole number x , > 0. For any real numbers x and y , | xy |=| x |∙| y |. Existential Statement: There exist integers x, y, z such that x 2 + y 2 = z 2 . There exists a real number x such that x 2 = -1. Conditional: If 2 is even then 2 is not prime. If green is red then the moon is made of cheese.

Cantor and Russell (Set Theory and Foundational Mathematics Forerunners)

Sets The concept of set is fundamental in every mathematics. The theory of sets was made popular by Georg Cantor in 1879. Intuitively, we can think of a set as a well-defined collection of objects in which it is clear whether an object belongs or does not belong to the set. Sets are usually denoted by capital letters such as A, B, ... while elements of sets are written using small letters such as a, b, ... . If an object a belongs to a set A, we write . Otherwise , . A universal set U in a particular case is the set of all objects in a particular context. A set may be written using roster method , for example: A= { 2,4,6,8 } . A set can also be written using set-builder method , for example A= { x : x is an integer, 1 < x < 9 } .

By the Axiom of Extension : Let A and B be sets. If every element of A is in B and every element of B is in A , then A=B . Equality of Sets: Let A and B be sets. A= B if and only if every element of A is in B and every element of B is in A . Example: Let A= { 2,4,6,8 } B= { 6,4,8,2 } C= { 2,4,4,4,6,6,8 }. Is A=B ? Is A=C ? Example: Is { } =0 ? Example: Is 2 ϵ { 2, { 1 }} ? Is { 2 } ϵ { 2, { 1 }} ? Is 1 ϵ { 2, { 1 }} ? Exampe : Is { 2, { 1 }} = { 1, { 2 }} ? Example: Let n be a nonnegative integer. Define U n = { 2n-1, 2n+1, 2n+3 } . Find U , U 1 , U 2 .

Here is a list of frequently used sets in mathematics: Sometimes, we place superscripts such as +, -, ≥0 to indicate “only positive elements of...”, “only negative elements of...”, and “only nonnegative elements of...”, respectively. Example: R + = { xϵ R : x > 0 } ; R - = { xϵ R : x < 0 } ; R ≥0 = { xϵ R : x ≥ 0 } ; Z + =? Symbol Set R set of all real numbers Q set of all rational numbers Z set of all integers W set of all whole numbers N set of all natural numbers

More examples on using set-builder notation: Describe each set by listing the elements or by drawing if listing is impossible. 1.) { xϵ R : -2.5 ≤ x <5 } 2.) { xϵ Z : -2.5 ≤ x < 5 } 3.) { xϵ N : -2.5 ≤ x < 5 } Definition: Let A and B be sets. Then A is a subset of B (written as ) whenever xϵA implies xϵB . A is a proper subset of B provided that but A≠B and we write . Example: Which of the following is true?

Set Operations Let A and B be sets. We define the following: i.) A Ս B= { x : xϵA or xϵB } (Union of sets) ii.) A Ո B= { x : xϵA and xϵB } (Intersection of sets) iii.) A - B= { x : x ϵA and } (Relative Complement) Example: Let U ={ 1,2,3,4,5,6,7,8,9,10 }. Let A= { 2,4,6,8 } , B= { 6,7,8,9,10 } and C= { 3,6,9 } . Find the following:

Example: Two programs were broadcast on television at the same time; one was the Big Game and the other was Ice Stars. The Nelson Ratings Company uses boxes attached to television sets to determine what shows are actually being watched. In its survey of 1000 homes at the midpoint of the broadcasts, their equipment showed that 153 households were watching both shows, 736 were watching the Big Game and 55 households were not watching either. How many households were watching only Ice Stars? Venn Diagrams and Application

Example: In a recent survey people were asked if they took a vacation in April , May , or December in the past year. The results were the following: 73 took a vacation in April , 51 took a vacation in May , 27 took a vacation in December , and 2 had taken no vacation. Also, 10 had taken vacations at all three times, 33 had taken both a n April and a May vacation, 18 had taken only a May vacation, and 5 had taken both April and December but not a May vacation. (1 ) How many people had taken vacations at exactly two times of the year? ( 2 ) How many people had taken vacations in April only ? ( 3 ) How many had taken vacations during both April and May but not December ? (4) How many had taken vacations during both May and December but not April? (5) How many people had been surveyed?

There exists a set without elements and we call it the empty set (written as Ø or { } ). Example: { x : xϵ N , x<0 } Theorem: If A is any set, then . For any sets A and B , if then A and B are said to be disjoint . Example: If A ={2,4,6,8} and D ={3,5,7,9}, then and so A and D are disjoint. Given elements a and b , the ordered pair {{ a}, { a,b }} is denoted by ( a,b ) . Two ordered pairs ( a,b ) and ( c,d ) are equal if and only if a=c and b=d .

Cartesian Product : Given sets A and B , the Cartesian product of A and B is the set A X B = {( a,b ) : aϵA , bϵB } . Example: Let A= { 2,4,6,8 } and B= { 1,2,3 } . Find the following: 1.) A X B 2.) B X A 3.) B X B . One of the familiar types of Cartesian product is R X R which can be visualized geometrically as the Cartesian plane .

Relations Objects in mathematics can be related to each other in several ways. For example, a number x is related to a number y because x>y , or because x 2 +y 2 =1 , and so on. Let A= { 2,4,6,8 } and B= { 3,5,7,9 } . Say x in A is related to y in B if and only if x>y . We can denote this by: x R y if and only if x>y . Determine elements of A and B which are related by R . We can express this concept in terms of ordered pairs: Let A and B be sets. A relation R from A to B is a subset of A X B . The notation x R y is equivalent to ( x,y ) ϵ R . The set A is called the domain of R while B is its co-domain . From the relation above above: R =?

Example: Let Y= { 0,1,2 } and Z= { 1,2 } . Define relation R from Y to Z as follows: (for x ϵ Y, yϵZ) x R y if and only if 2 divides x+y . Determine the elements of R . Example: Consider R and define the relation S on R (from R to R ) by: x S y if and only if x 2 +y 2 =1 . 1.) Give some elements of S . 2.) Given x=1 , what are allowable values of y such that x S y ? 3.) What is the graph of this relation? Example: Consider Z and define the relation T on Z by: x T y if and only if x-y is divisible by 5 . 1.) Give some elements of T . 2.) Give some general observation about the connection of T and some subsets of Z .

Functions A function f from a set A to a set B is a relation with domain A and co-domain B which satisfies the following conditions: i.) For every xϵA , there exists yϵB such that ( x,y ) ϵ f . ii.) For all elements x ϵA , y and z in B , if ( x,y ) and ( x,z ) are elements of f , then y=z . Notation: We usually write the function above as f:A→B and f ( x ) =y if and only if ( x,y ) ϵ f . Here, we say, y is “ f of x ”. x is called a pre-image of y and y is the image of x under f .

Example: Let A={1,2,3} and B={3,4} . Which of the following relations are functions? 1.) (from A to B ) f 1 = {(1,3),(2,4),(3,3)} 2.) (from B to A ) f 2 = {(3,1),(4,2)} 3.) (from A to B ) f 3 = {(1,3),(2,4)} 4.) (from B to B ) f 4 = {(3,4),(4,3)} 5.) (from A to A ) f 5 = {(1,3),(2,4),(3,3),(1,4)} Example: Which of the following relations on R is a function? 1.) f 6 = {( x,y ) ϵ R X R : x-y 2 = 1 } 2.) f 7 = {( x,y ) ϵ R X R : x 2 -y = 1 } 3.) f 8 = {( x,y ) ϵ R X R : x 2 +y 2 = 1 } 4.) f 9 = {( x,y ) ϵ R X R : x-y = 1 }

Domain – the set of all first elements in the ordered pair. Range – the set of all second elements in the ordered pair. Co-domain – in a relation from A to B, the co-domain is the entire set B. Hence, the range (subset) of co-domain.

III. Problem-Solving A regular polygon with n ( n≥3 ) sides is a closed figure whose sides are of equal length such as the equilateral triangle, square, and so on. It is also called an n -gon. A diagonal of an n -gon is a line segment that connects two non-adjacent vertices. Observe the following pattern of the numbers of diagonals in several n -gons for small values of n and try to generalize.

Inductive Reasoning Inductive reasoning is the process of reaching a general conclusion by examining specific examples. Example:Use inductive reasoning to p redict the next number in each list. 1.) 5, 10, 15, 20, 25, ? 2.) 2, 5, 10, 17, 26, ? Example: Use inductive reasoning to make a conjecture. 1.) Consider the following procedure: Pick a number. Multiply the number by 9, add 15 to the product, divide the sum by 3, and subtract 5. 2.) Consider the following procedure: Pick a number. Multiply the number by 8, add 6 to the product, divide the sum by 3, and subtract 2.

Example: A tsunami is a sea wave produced by an underwater earthquake. The height of a tsunami as it approaches land depends on the velocity of the tsunami. Use the table below and inductive reasoning to answer each of the following questions. a.) What happens to the height of a tsunami when its velocity is doubled? b.) What should be the height of a tsunami if its velocity is 30 feet per second? Velocity of Tsunami (feet per second) Height of Tsunami (feet) 6 4 9 9 12 16 15 25 18 36 21 49 24 64

Counterexamples Example: For each circle, count the number of regions formed by the line segments that connect the dots on the circle. Using small numbers of dots, complete the list below. Make a guess on the number of regions when there are six dots. Number of Dots 1 2 3 4 5 6 Number of Regions 1 2 ? ? ? ?

Example: Verify that each of the following statements is false by finding a counterexample. 1.) For all real numbers x , |x|>0 . 2.) For all real numbers x , . 3.) For all real numbers x , . N.B. Using inductive reasoning would not guarantee that your conclusion is true.

Deductive Reasoning Deductive reasoning is the process of reaching a conclusion by applying general assumptions, procedures, or principles. Example: Use deductive reasoning to derive the general form of the expression. 1.) Consider the following procedure: Pick a number. Multiply the number by 9, add 15 to the product, divide the sum by 3, and subtract 5. 2.) Consider the following procedure: Pick a number. Multiply the number by 8, add 6 to the product, divide the sum by 3, and subtract 2. Example: Determine whether each of the following arguments is inductive or deductive. 1.) During the past 10 years, a tree has produced plums every other year. Last year the tree did not produce plums, so this year the tree will produce plums. 2.) All home improvements cost more than the estimate. The contractor estimated that my home improvement will cost $35,000. Thus my home improvement will cost more than $35,000.

Example (Logic Puzzle): Each of four neighbors , Sean, Maria, Sarah, and Brian, has a different occupation (editor, banker, chef, or dentist). From the following clues, determine the occupation of each neighbor . 1.) Maria gets home from work after the banker but before the dentist. 2.) Sarah, who is the last to get home from work, is not the editor. 3.) The dentist and Sarah leave for work at the same time. 4.) The banker lives next door to Brian. Example: Brianna, Ryan, Tyler, and Ashley were recently elected as the new class officers (president, vice president, secretary, treasurer) of the sophomore class at Summit College. From the following clues, determine which position each holds. 1.) Ashley is younger than the president but older than the treasurer. 2.) Brianna and the secretary are both of the same age, and they are the youngest members of the group. 3.) Tyler and the secretary are next-door neighbors .

Problem Solving with Patterns An ordered list of numbers a 1 , a 2 , ... a n , ... is called a sequence . The numbers separated by commas are the terms of the sequence. The n th term represents the general formula for each term. Example: Using “difference table”, determine the succeeding terms of each sequences. 1.) 2,5,8,11,14,... 2.) 5,14,27,44,65,... 3.) 2,7,24,59,118,207,... 4.) 1,14,51,124,245,426,... N.B. Here, we assume that the pattern obtained by the “difference table” continues.

Example: Assume the pattern shown by the square tiles in the following figures continue. a 1 a 2 a 3 a 4 a 5 1.) What is the nth-term formula for the number of tiles in the nth figure of the sequence? 2.) How many tiles are in the eighth figure of the sequence? 3.) Which figure will consist of exactly 320 tiles?

Example: Assume that the pattern shown by the square tiles in the following figure continues. a 1 a 2 a 3 a 4 a 5 1.) What is the nth-term formula for the number of tiles in the nth figure of the sequence? 2.) How many tiles are in the tenth figure of the sequence? 3.) Which figure will consist of exactly 419 tiles?

Problem-Solving Strategies Polya's Problem-Solving Strategy i.) Understand the problem. ii.) Devise a plan. iii.) Carry out the plan. iv.) Review the solution. Note: George Polya is a Hungarian mathematician who contributed to different areas of mathematics. One of his main contribution is a formula which is a consequence of the Burnside's Lemma which counts the number of orbits in a group action. Polya applied this to solve counting problems in combinatorics.

Example: Consider the map shown below. Allison wishes to walk along the streets from point A to point B. How many direct routes can Allison take? A B

Example: A baseball team won two out of their last four games. In how many different orders could they have two wins and two losses in four games? Example: In a basketball league consisting of 10 teams, each team plays each of the other teams exactly three times. How many league games will be played? Example: If six people greet each other at a meeting by shaking hands with one another, how many handshakes will take place? Example: Determine the digit 100 places to the right of the decimal point in the decimal representation . Example: Four people on one side of a river need to cross the river in a boat that can carry a maximum load of 180 pounds (including the driver of the boat). The weights of the people are 80, 100, 150, and 170 pounds. Find the minimum number of crossings that must be made by the boat to carry everyone to the opposite side. (Note: Assuming anyone can drive the boat).

IV. Statistics Statistics involves the collection, organization, summarization, presentation, and interpretation of data. The branch of statistics which involves the collection, organization, summarization, and presentation of data is called descriptive statistics . The branch that interprets and draws conclusions from the data is called inferential statistics . Suppose Elle is a senior at a university and in a few months she plans to graduate to start a career as a landscape architect. A survey of five landscape architects from last year's senior class shows that they received job offers with the following yearly salaries: $43,000 $39,500 $38,000 $41,250 $44,000. What amount would best represent the salaries above?

Measures of Central Tendency The mean of n numbers x 1 , x 2 , ... x n is the sum of the numbers divided by n . The entire group under consideration is known as the population . Any subset of the population is called a sample . A mean from the sample is denoted by , while the mean from the population is denoted by μ . Example: Six friends in a biology class of 20 students received test grades of 92, 84, 65, 76, 88, 90. Find the mean of these test scores.

The median of a ranked list of n numbers is the middle number if n is odd or the mean of the two middle numbers if n is even. Example: Find the median of the data in the following lists. 1.) 14, 27, 3, 82, 64, 34, 8, 51 2.) 21.3, 37.4, 11.6, 82.5, 17.2 The mode of a list of numbers is the number that occurs most frequently. Exampe: Find the mode of the data in the following lists. 1.) 18, 15, 21, 16, 15, 14, 15, 14, 21 2.) 3, 4, 7, 4, 3, 6, 8, 4, 7, 3, 6, 5, 5, 3, 4 3.) 14, 27, 3, 82, 64, 34, 8, 51 Note: The mean, median and mode are all averages and the three may not be equal for a certain set of data.

The weighted mean of n numbers x 1 , x 2 , ... , x n with the respective assigned weights w 1 , w 2 , ... , w n is Weighted Mean . Example: Suppose Maria's grades on the first semester in a certain university are as follows: Compute Maria's grade point average (GPA) as a weighted mean. Course Course Grade Course Unit Fundamentals of Mathematcis 1.1 3 General Physics 1.2 3 Physical Education II 1.5 2 NSTP II 2.0 1

Data that have not been organized or manipulated in any manner are called raw data . A frequency distribution is often used to organize raw data by tabulating observed cases with corresponding frequency. To compute for the mean, we can use the weighted mean formula by using the frequencies as weights. Example: Consider the following list of number of laptop computers owned by families in each 40 homes in a subdivision. Make a frequency table for the raw data above and compute the mean. 2 2 1 2 1 2 4 1 3 1 2 2 2 1 7 1 5 1 2 2 3 2 5 1 2 3 1 2 1 2 4 1 1 2 5

Measures of Dispersion The range of a set of data values is the difference between the greatest data value and the least data value. Example: Consider a soft-drink dispensing machine that should dispense 8 oz of your selection into a cup. The table shows data for two of these machines. Find the range of the numbers of ounces dispensed by Machine 1. Find the range of the numbers of ounces dispensed by Machine 2. Machine 1 Machine 2 9.52 8.01 6.41 7.99 10.07 7.95 5.85 8.03 8.15 8.02 mean = 8.0 mean = 8.0

If x 1 , x 2 , ... , x n is a population of n numbers with a mean of μ, then the standard deviation of the population is If x 1 , x 2 , ... , x n is a sample of n numbers with a mean of , then the standard deviation of the sample is

Company Hours of constant use per battery EverSoBright 6.2, 6.4, 7.1, 5.9, 8.3, 5.3, 7.5, 9.3 Dependable 6.8, 6.2, 7.2, 5.9, 7.0, 7.4, 7.3, 8.2 Beacon 6.1, 6.6, 7.3, 5.7, 7.1, 7.6, 7.1, 8.5 Example: A student has the following quiz scores: 5, 8, 16, 17, 18, 20. Find the standard deviation for this population of quiz scores. Example: A consumer group has tested a sample of 8 size-D batteries from each of 3 companies. The results of the tests are shown in the following table. According to these tests, which company produces batteries for which the values representing hours of constant use have the smallest standard deviation? A variance for a given set of data is the square of the standard deviation of the data. For population variance, we use . While is used for the sample variance. Example: A student has the following quiz scores: 5, 8, 16, 17, 18, 20. Find the variance for this population of quiz scores.

Measures of Relative Position The z -score for a given data value x is the number of standard deviations that x is above or below the mean of the data. The following formulas show how to calculate the z -score for a data value x in a population and in a sample. Note: A z-score of 3 for a data value x means that x is 3 standard deviations ABOVE the mean. A z-score of -1 for a data value x means that x is 1 standard deviation BELOW the mean.

Example: Cheryl has taken two quizzes in her history class. She scored 15 on the first quiz, for which the mean of all scores was 12 and the standard deviation was 2.4. Her score on the second quiz, for which the mean of all scores was 11 and the standard deviation was 2.0, was 14. In comparison to her classmates, did Cheryl do better on the first quiz or the second quiz? Example: A consumer group tested a sample of 100 light bulbs. It found that the mean life expectancy of the bulbs was 842 h, with a standard deviation of 90. One particular light bulb from the DuraBright Company had a z -score of 1.2. What was the life span of this light bulb? A value x is called the p th percentile of a data set provided p% of the data values are less than x . Example: The median annual salary for a police dispatcher in a large city was $44,528. If the 25th percentile for the annual salary of a police dispatcher was $32,761, find the percent of police dispatchers whose annual salaries were a.) less than $44,528. b.) more than $32,761. c.) between $32,761 and $44,528.

Percentile for a Given Data Value: Given a set of data and a data value x , Percentile of score x = [(number of data values less than x )/(total number of data values)] * 100 Example: On an examination given to 8600 students, Hal's score of 405 was higher than the scores of 3952 of the students who took the examination. What is the percentile for Hal's score? The three numbers Q 1 , Q 2 , and Q 3 that partition a ranked data set into four (approximately) equal groups are called the quartiles of the data. Q 1 is called the first quartile , Q 2 is the second quartile , and Q 3 is third quartile .

The Median Procedure for Finding Quartiles: 1.) Rank the data. 2.) Find the median of the data. This is Q 2 . 3.) Q 1 is the median of the data values less than Q 2 . Q 3 is the median of the data values greater than Q 2 . Example: The following table lists the weights, in ounces, of 15 avocados in a random sample. Find the quartiles for the data. 12.4 10.8 14.2 7.5 10.2 11.4 12.6 12.8 13.1 15.6 9.8 11.4 12.2 16.4 14.5 A box-whisker plot (sometimes called a box plot ) is used to make a visual summary of a set of data which shows the median, the first and third quartiles, and the minimum and maximum values of the data set.

Construction of a Box-and-Whisker Plot: 1.) Draw a horizontal scale that extends from the minimum data value to the maximum data value. 2.) Above the scale, draw a rectangle (box) with its left side at Q 1 and its right side at Q 3 . 3.) Draw a vertical line segment across the rectangle at the median. 4.) Draw a horizontal line segment, called whisker, that extends from Q 1 to the minimum and another whisker that extends from Q 3 to the maximum. Example: Construct a box-and-whisker plot for the data in the example above. Example: Construct a box-and-whisker plot for the following set of data which shows the number of rooms occupied in a resort during an 18-day period. 86 77 58 45 94 96 83 76 75 65 68 72 78 85 87 92 55 61

Frequency Distribution and the Normal Distribution Grouped Frequency Distibution Example: An internet service pro- vider has installed new computers. To estimate the new download times its subscribers will experience, it surveyed 1000 of its subscribers to determine the time required for each subscriber to download a particular file from an inter- net site. The results are summarized in the following table. Download time (in seconds) Number of Subscribers 0-5 6 5-10 17 10-15 43 15-20 92 20-25 151 25-30 192 30-35 190 35-40 149 40-45 90 45-50 45 50-55 15 55-60 10

Relative Frequency Distribution (In a relative frequency distribution there is a direct correspondence between the percent values of the relative frequency distribution and probabilities.) Example: Using the relative frequency on the right, determine the following: 1.) percent of subscribers who required less than 25 s to download the file. 2.) probability that a subscriber chosen at ran- dom will require at least 10 s but less than 30 s to download the file. Download time (in seconds) Percent of subscribers 0-5 0.6 5-10 1.7 10-15 4.3 15-20 9.2 20-25 15.1 25-30 19.2 30-35 19.0 35-40 14.9 40-45 9.0 45-50 4.5 50-55 1.5 55-60 1.0

Histogram Relative Frequency Histogram

Normal Distribution A normal distribution forms a bell-shaped curve that is symmetric about a vertical line through the mean of the data. Some Properties of a Normal Distribution a.) The graph of a normal distribution is symmetric about a vertical line through the mean of the distribution. b.) The mean, median, and mode are equal. c.) Areas under the curve that are symmetric about the mean are equal. d.) The total area under the curve is 1. There are several types of data that approximate a normal distribution.

Empirical Rule for a Normal Distribution

Example: A survey of 1000 U.S. gas stations found that the price charged for a gallon of regular gas could be closely approximated by a normal distribution with a mean of $3.10 and a standard deviation of $0.18. How many of the stations charge a.) between $2.74 and $3.46 for a gallon of regular gas? b.) less than $3.28 for a gallon of regular gas? c.) more than $3.46 for a gallon of regular gas? Example: A vegetable distributor knows that during the month of August, the weights of its tomatoes are normally distributed with a mean of 0.61 lb and a standard deviation of 0.15 lb. a.) What percent of the tomatoes weigh less than 0.76 lb? b.) In a shipment of 6000 tomatoes, how many tomatoes can be expected to weigh more than 0.31 lb? c.) In a shipment of 4500 tomatoes, how many tomatoes can be expected to weigh from 0.31 lb to 0.91 lb?

Standard Normal Distribution If the original distribution of x values is a normal distribution, then the corresponding distribution of z -scores will also be a normal distribution and this is called a standard normal distribution .

Example: Find the area of the standard normal distribution between z=-1.44 and z=0 . Example: Find the area of the standard normal distribution between z=-0.67 and z=0 . Example: Find the area of the standard normal distribution to the right of z=0.82 . Example: Find the area of the standard normal distribution to the right of z=-1.47 . The Standard Normal Distribution, Areas, Percentages, and Probabilities: In the standard normal distribution, the area of the distribution from z=a to z=b represents i.) the percentage of z -values that lie in the interval from a to b . ii.) the probability that z lies in the interval from a to b .

Example: A soda machine dispenses soda into 12-ounce cups. Tests show that the actual amount of soda dpensed is normally distributed, with a mean of 11.5 oz and a standard deviation of 0.2 oz. a.) What percent of cups will receive less than 11.25 oz of soda? b.) What percent of cups will receive between 11.2 oz and 11.55 oz of soda? c.) If a cup is filled at random, what is the probability that the machine will overflow the cup? Example: A study shows that the lengths of the careers of professional football players are nearly normally distributed, with a mean of 6.1 years and a standard deviation of 1.8 years. a.) What percent of professional football players have a career of more than 9 years? b.) If a professional football player is chosen at random, what is the probability that the player will have a career of between 3 and 4 years?

Linear Regression and Correlation Researchers often wish to know the relationship or whether a relationship exists between two variables. If two variables are determined to be related, the next thing of interest is to model the relationship by a mathematical equation. The two variables involved in the investigation are called bivariate data . A scatter diagram is then drawn to give a picture of the relationship. One of the interesting case is studying if there is a linear relationship. The least-squares regression line or line of best fit for a set of bivariate data is the line that minimizes the sum of the squares of the vertical deviations from each data point to the line.

Hours of sunshine (x) 2 3 5 7 9 Ice creams sold (y) 4 5 7 10 15 The equation of the least-squares line for the n ordered pairs (x 1 ,y 1 ), (x 2 ,y 2 ),...,( x n ,y n ) is , where Example: Sam observed and found some data on how many hours of sunshine and how many ice creams were sold at the shop from Monday to Friday. Draw the scatter diagram and find the equation for the line of best fit for the data.

Example: The stride length for an animal is defined as the distance x from a particular point on a footprint to that same point on the next footprint of the same foot. A scientist is trying to experiment on the stride of an animal vs its speed. He obtained the following data. a.) Adult men b.) Dogs Draw the scatter diagram for each of the above and find the equation of the line of best fit. Stride length (m) 2.5 3.0 3.3 3.5 3.8 4.0 4.2 4.5 Speed (m/s) 3.4 4.9 5.5 6.6 7.0 7.7 8.3 8.7 Stride length (m) 1.5 1.7 2.0 2.4 2.7 3.0 3.2 3.5 Speed (m/s) 3.7 4.4 4.8 7.1 7.7 9.1 8.8 9.9

Linear Correlation Coefficient Linear correlation coefficient is used to determine the strength of linear relationship between two variables. For the n ordered pairs (x 1 ,y 1 ), (x 2 ,y 2 ),...,(x n ,y n ) , the linear correlation coefficient r is given by

A positive r indicates a positive correlation , that is, if one variable increases then the other also increases. A negative r indicates a negative correlation , that is, if one variable increases then the other tends to decrease. Different Types of Linear Correlation

Example: Find the linear coefficient for the stride length versus speed of an adult man as given in the above example. Example: Find the linear coefficient for the stride length versus speed of a dog as given in the above example. Example: In the table below, the hours per week that a student spent playing pool and the student's weekly algebra test scores for those same weeks are listed. Compute for the linear coefficient and conclude on the type of linear relationship between the two variables. N.B. The linear correlation coefficient indicates the strength of a linear relationship between two variables but it does show the presence of a cause-and-effect relationship . Hours per week spent playong pool 4 5 7 8 10 Weekly algebra test score 52 60 72 79 83

V. Logic

A National Scientist Fr. Nebres has conducted studies in the first-order logic, as mathematicians, philosophers, and theoretical computer scientists mostly do and in infinitary logics. In a series of papers published in very prestigious international journals (Notices of the American Mathematical Society, Journal of Symbolic Logic, Journal of the Mathematical Society of Japan) Fr. Nebres studied the characterization of infinitary sentences preserved under unions of models. His supervisor was the distinguished logician Solomon Feferman , who was a student of Alfred Tarski, founder of model theory and considered one of the greatest logicians of all time . (Courtesy of the National Academy of Science and Technology - Philippines)

Logic Statements and Quantifiers A statement is a declarative sentence that is either true or false, but not both true and false. Example: Which of the following is a statement? 1.) Is the moon made of cheese? 2.) x>3 . 3.) 3+5 is even. 4.) 3+5=7. 5.) This is a false sentence. A simple statement is a statement that conveys a single idea. A compound statement is a statement that conveys two or more ideas. Combining simple statements to form a compound statement uses the following binary connectives : and , or (inclusive or), if-then , if and only if . We can also use the unary connective not to form a new simple statement out of a given one.

Let p and q be simple statements. The following are compound statements formed by logic connectives and usual notations: The truth value of a simple statement is either true (T) or false (F). The truth value of a compound statement depends on the truth values of its simple statements and its connectives. A truth table shows the truth value of a compound statement for all possible truth values of its simple statements. Statement Connective Symbolic Form Type of Statement not p not ~ p negation p and q and p Λ q conjunction p or q or p V q disjunction If p then q If...then p → q conditional p if and only if q if and only if p ↔ q biconditional

Truth Table for ~ p Example: Write the negation of each statement and determine the truth value. 1.) Red is blue. 2.) 1 is not equal to -1. Example: Consider the following simple statements. p : Today is Friday. q : It is raining. r : I am going to a movie. s : I am not going to the basketball game. p ~ p T F F T

Write th following compound statements in symbolic form. 1.) Today is not Friday and I am going to a movie. 2.) I am going to the basketball game or I am not going to a movie. 3.) I am going to a movie if and only if it is not raining. 4.) If today is Friday then I am not going to the basketball game. Example: Consider the following statements. p : The game will be played in Atlanta. q : The game will be shown on CBS. r : The game will not be shown on ESPN. s : The Mets are favored to win. Write each of the following symbolic statements in words. 1.) p Λ q 2.) q V ~r 3.) ~ p → s

If a compound statement is written in symbolic form then parentheses are used to indicate which simple statements are grouped together. However, if a compound statement is written as an English statement then a comma is used to indicate which simple statements are grouped together. Do ~( p Λ q ) and ~ p Λ q differ in meaning? Example: Let p, q, and r represent the following. p : You get a promotion. q : You complete the training. r : You will receive a bonus. 1.) Write ( p Λ q )→ r as an English sentence. 2.) Write “If you do not complete the training, then you will not get a promotion and you will not receive a bonus.”

Truth Table of a Conjunction Truth Table of a Disjunction p q p Λ q T T T T F F F T F F F F p q p V q T T T T F T F T T F F F

Example: Determine the truth value of each statement. 1.) 2 is a prime number and red is blue. 2.) 2 is a prime number or red is blue. 3.) -2 ≤ 5 4.) There are infinitely many primes but only one prime is even.

Quantifiers and Negation Recall: The words all, every, any are called universal quantifiers . While some, there exists, at least one are called existential quantifiers . How do we negate quantified statements? Example: Give the negation of the following statements. 1.) All dogs in the house are black. 2.) No doctors write in a legible manner. 3.) Some vegetables are not green. 4.) There are examinees who failed the first part of the examination. Quantified Statements and Their Negations Statement Negation All X are Y. Some X are not Y. No X are Y. Some X are Y. Some X are Y. No X are Y. Some X are not Y. All X are Y.

Equivalent Statements and Tautologies Standard Truth Table Form Example: Construct the truth table of ( p Λ~ q )V(~ p V q ). p q Statement T T T F F T F F Example: Construct the truth table of p Λ( q V r ). p q r Statement T T T T T F T F T T F F F T T F T F F F T F F F

Equivalent Statements Two statements are equivalent if they both have same truth value for all possible truth values of their simple statements. If statements p and q are equivalent, we write p ≡ q. Example: Show that ~( p Λ q ) ≡ ~ p V ~ q . Example: Which of the following statements are equivalent? 1.) p V ( q Λ r ) 2.) ( p V q ) Λ ( p V r ) 3.) ( p Λ q ) V ( p Λ r ). Example: Restate the following sentence in an equivalent form. “It is not true that, I ordered ice cream and I got a change.”

Tautologies and Self-Contradictions A tautology is a statement that is always true. A contradiction is a statement that is always false. Example: Determine if each is a tautology, a contradiction, or neither. 1.) My shirt is red. 2.) My shirt is red and my shirt is not red. 3.) My shirt is red or my shirt is not red. Example: Using truth table, determine if each is a tautology, a contradiction, or neither. 1.) p Λ (~ p Λ q ) 2.) (( p V q ) Λ ~ q ) V p 3.) ( p Λ q ) V (~ p V ~ q ).

Conditional Consider the following advertising slogan: “If you can use a word processor, then you can create a webpage.” When can we say that the ad is telling the truth ? Telling a lie? Conditional: If p then q . Antecedent: p Consequent: q Notation: p → q Other way of expressing p → q : p implies q; p is stronger than q; q is a necessary condition for p. Truth Table for a Conditional: p q p → q T T T T F F F T T F F T

In row 1, you can use a word processor and you can create a webpage. In this case the truth value of the ad is true . In row 2, you can use a word processor but you cannot create a webpage . In this case the truth value of the ad is false . In row 3, you cannot use a word processor but you can create a webpage. Because the ad does not make any statement about what you might or might not be able to do if you cannot use a word processor, we cannot say that the ad is false. Hence its truth value is true . In row 4, you cannot use a word processor and you cannot create a webpage. Because the ad does not make any statement about what you might or might not be able to do if you cannot use a word processor, we cannot say that the ad is false. Hence its truth value is true .

Example: Determine the truth value of each of the following. 1.) If 9>4 then 8>3. 2.) If 4>9 then 3>8. 3.) If 1=-1 then 8>3. 4.) If green is red then the moon is made of cheese. Example: Construct a truth table for each of the following. 1.) ( p Λ ( q → p )) → q. 2.) (( p V q ) Λ ~ q ) → p. 3.) (( p → q ) Λ ( q → r )) → ( p → q ).

An Equivalent Form of a Conditional: p → q ≡ ~ p v q . Example: Write each of the following in its equivalent disjunctive form. 1.) If I do not move to Georgia then I will live in Houston. 2.) If the number is divisible by 2 then the number is even. Negation of a Conditional: ~( p → q ) ≡ p Λ ~ q . Example: Write the negation of each conditional statement. 1.) If I finish the report then I will go to the concert. 2.) If the square of n is 25 then n is 5 or -5.

Biconditional Biconditional: p ↔ q p ↔ q is true whenever p and q have the same truth value. Truth Table for a Biconditional: Ways of expressing p ↔ q : p if and only if q; p is equivalent to q. Equivalent Form of a Biconditional: p ↔ q ≡ ( p → q ) Λ ( q → p ). p q p ↔ q T T T T F F F T F F F T

Example: Let p , q , and r represent the following. p : I will go on vacation. q : I cannot take the train. r : I cannot get a loan. Write the following symbolic statements in words: 1.) p ↔ ~ r . 2.) ~ q ↔ ~ r . Example: State whether each biconditional is true or false. 1.) 9>4 if and only if 8>3. 2.) 4>9 is equivalent to 3>8. 3.) 1=-1 is equivalent to 8>3. 4.) Green is red if and only if the moon is made of cheese.

Conditional and Related Statements The converse of p → q is q → p . The inverse of p → q is ~ p →~ q . The contrapositive of p → q is ~ q →~ p . Example: Write the converse, inverse and contrapositive of the following implication. If I study then I will pass the examination. Example: Find the truth tables for the converse, inverse and contrapositive of p → q and compare it with that of p → q. p q p → q q → p ~ p →~ q ~ q →~ p T T T T F F F T T F F T

Example: Determine which of the given statements are equivalent. 1.) If I do not live in Cebu City then I do not live in Tisa. If I do not live in Tisa then I do not live in Cebu City. If I live in Cebu City the I live in Tisa. If I live in Tisa then I live in Cebu City. 2.) Let a, b and c be real numbers. If a=b then ac=bc . If ac=bc then a=b . If a ≠b then ac≠ bc . If ac ≠ bc then a ≠ b .

A theorem in mathematics always comes in an implication form or biconditional which can be broken into two implications. Sometimes, it is easier to prove the equivalent contrapositive form than the given theorem. Mathematicians called the related proof method as the contrapositive proof. Example: Prove the following theorem by proving its contrapositive form. 1.) Let n be an integer. If n 2 is even then n is even. 2.) Let n be an integer.If 3+ n is an odd integer then n is even. 3.) Let a and b be real numbers. If abϵR+ then ( a,b ) ϵ R + X R + or ( a,b ) ϵ R - X R - .

Symbolic Arguments An argument consists of a set of statements called premises and another statement called the conclusion . An argument is valid if the conclusion is true whenever all the premises are assumed to be true. An argument is invalid if it is not a valid argument. In symbol, suppose p 1 , p 2 , ... , p n are the premises and q is the conclusion. Thus, the argument is ( p 1 Λ p 2 Λ ... Λ p n ) → q . Another way of writing an argument is: p 1 p 2 . . . p n ________ q

Example: 1.) p1: If Aristotle was human, then Aristotle was mortal. p2: Aristotle was human. q : Therefore, Aristotle was mortal. 2.) p1: The fish is fresh or I will not order the fish. p2: The fish is fresh. q : Therefore, I will order the fish. 3.) p1: If she does not get on the plane then she will regret it. p2: She does not regret it. q : Therefore, she gets on the plane. Example: Write the arguments above in symbolic forms using its simple statements. 1.) Let p: Aristotle was human; q: Aristotle was mortal. Then p→q p__ that is, (( p → q ) Λ p ) → q. q

How to determine the validity of an argument? Using Truth Table to Determine the Validityof an Argument i.) Transform the argument in symbolic form. ii.) Construct a truth table that shows the truth value of each premise and the truth value of the conclusion for all combinations of truth values of the simple statements. iii.) If the conclusion is true in every row of the truth table in which all the premises are true, the argument is valid. If the conclusion is false in some row in which all the premises are true, the argument is invalid. Example: Determine if each of the arguments above is valid or invalid using truth tables. 1.) p q (( p → q ) Λ p ) → q T T T F F T F F

When the number of simple statements grow large, truth table procedure becomes inefficient. Thus, we make use of a list of verified tautologies in writing a sequence of statements which starts from the premises and ends up with the conclusion. We do this via a two-column table. Example: Determine whether the following argument is valid. If I read a literature book I start to fall asleep . If I start to fall asleep then I drink soda. If I drink soda then I must eat a candy bar. If I read a literature book then I eat a candy bar. Example: Determine whether the following argument is valid. I will not go to Japan or I will go to Hong Kong. If I visit my uncle then I will go to Singapore. If I go to Hong Kong then I will not go to Singapore. If I go to Japan then I will not visit my uncle.

Example: Determine whether each of the arguments is valid or not. If valid, give a two-column proof. 1.) ~m V t 2.) ~m V t t → ~d t → ~d e V g e V g e → d e → d g → m m → g Example: Use the premises to determine a valid conclusion and verify. 1.) ~( p Λ ~ q ) 2.) ~ s → q p ~ t → ~ q ~ t_____

Arguments and Euler Diagrams Euler Diagrams on Relationships Between Two Sets

Example: (1-5) Use an Euler diagram to determine whether the following arguments are valid or invalid. 1. All lawyers drive BMWs. 2. Some positive numbers are integers. Susan is a lawyer. is a positive number. Susan drives a BMW. is an integer. 3. No prime numbers are negative. 4. No mathematics professors are good-looking. The number 7 is not negative. All good-looking people are models. The number 7 is a prime number. No mathematics professor is a model. 5. All squares are rhombi. 6. Determine a valid conclusion. All rhombi are are parallelograms. All rabbits are white. All parallelograms are quadrilaterals . No white animals like tomatoes. All squares are quadrilaterals. ?

VI. Mathematical Systems Consider a 12-hour clock. To know what is 7 hours after 6 am, we just start by pointing the hour hand at 6 then move it 7 units “clockwise”. We then end up with 1 which means that 7 hours after 6 am is 1 pm. Likewise, if we want to determine what day is 5 days after W ednesday then we start counting from T hursday , with one day counted as one, we end up with M onday . Thus, 5 days after W ednesday is M onday . Example : Evaluate each of the following, where and indicate addition and subtraction respectively on a 12-hour clock. 1.) 3.) 2.) 4 .) Instances like these just repeat in cycles and are represented mathematically using the concept of modulo congruence and modulo arithmetic.

Modulo Congruence Let x be any integer and b any positive integer. Then b divides x (written as ) if there exists an integer y such that . Example: Which of the following is true? 1.) 2|6 3 .) 1|5 5 .) 3|0 2.) 4|6 4 .) 5|1 Let x and y be integers and n be a positive integer. We say x is congruent to y modulo n (written as ) if and only if 1.) Example : Which of the following congruences are true? 1.) 3 .) 2.) 4 .) 2.) July 4, 2017, was a Tuesday. What day of the week is July 4, 2022?

Arithmetic Operations Modulo n Theorem (Division Algorithm): Let be any integer and be any positive integer. Then there exist unique integers and such that where Addition Modulo n : Let x and y be any integers and n be a positive integer. Then is obtained by adding x and y under the usual addition then using the Division algortihm . That is, we write whenever where q, r are integers such that We define: subtraction modulo n : multiplication modulo n : in the same manner.

Example: Evaluate each of the following: 1. 2. 3. 4. 5. Disregard A.M. or P.M., If it is 5 o’clock now, what time was it 57 hours ago?

Solving Congruence Equations Let a and b be integers and n is a positive integer. Then is called a linear congruence equation . To solve a congruence equation means finding all whole number values of the variable for which the congruence is true. Example: Solve Example: Solve Example: Solve

Applications of Modular Arithmetic Every book that is cataloged in the Library of Congress has an ISBN ( International Standard Book Number ) which is a 13-digit number. The first three digits of an ISBN are 978 (or 979), followed by nine digits which are divided into three groups and indicate the country or region, publisher, and the title of the book. The last digit (the 13th digit) is called the check digit which is computed as follows: For integer i such that 1 ≤ i ≤ 12, denote the i th digit of an ISBN by d i . Then If d 13 = 10 then the check digit is 0.

Example : 1.) The first twelve digits of the ISBN of a book are 978-0-7432-5820-___? Determine the check digit. 2.) A purchase order for the book The Mathematical Tourist by Ivars Peterson includes the ISBN 978-0-395-28517-4. Is this a valid ISBN?

Another coding scheme is the UPC ( Universal Product Code ) which is used in grocery stores. The UPC is a 12-digit number such that the last digit is also called the check digit and is computed using modular arithmetic. The formula for the check digit of a UPC is given by If d 12 = 10 then the check digit is 0.

Example : 1.) Find the check digit for the UPC of the Century Tuna can with the first eleven digits 0-25192-21221-___? 2.) Is 0-14285-00278-9 a valid UPC?

Luhn algorithm is a coding method used in credit cards, automated teller machine card, etc. which uses modular arithmetic. Credit card numbers are normally 13 to 16 digits long. The first one to six digits are used to identify the card issuer. The table below shows some of the identification prefixes used by four popular card issuers. Card Number Prefix Number of digits MasterCard 51 to 55 16 Visa 4 13 or 16 American Express 34 or 37 15 Discover 6011 16

To determine whether a card number is valid or not under this algorithm, the following calculations are performed: Begin with the next-to-past digit and reading from right to left, double every digit. If a digit becomes a two-digit number after being doubled, treat the as two individual digits. Find the sum of the new list of digits. The final sum must be congruent to 0 mod 10. Example: 1.) Is 5234-8213-3410-1298 is a valid credit card number? 2.) Example : Is 280 01 009263 1 a valid ATM card? 3.) Example : U sing Luhn algorithm, c heck your own atm card number if it is valid.

(From the book Elementary Number theory: Primes, Congruences, and Secrets by William Stein) - W. Stein Diffie Hellman

Cryptology Cryptology is the study of making and breaking secret codes. Coding Scheme

Numerical Equivalents for the Letters of the Alphabet To encode a message with shifting, every letter p in the plaintext will be encoded using the formula where m is the chosen number of shifts of the letters. To decode a ciphertext , the following formula is used where A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Example: Use the cyclical alphabetic encrypting code that shifts each letter 11 positions to 1 .) encode CATHERINE THE GREAT 2 .) decode TGLY ESP EPCCTMWP

A more sophisticated coding scheme is based on the congruence where gcd ( a ,26) = 1. Example: 1.) Use the congruence c ≡ (5 p + 2) mod 26 to encode the message LASER PRINTER.

Decoding a message that was encrypted using the congruence requires solving the congruence for p. The method relies on multiplicative inverses. Here we solve the congruence used in the previous example for p.

Example: 1.) Decode the message ACXUT CXRT, which was encrypted using the congruence

VII. Graph Theory (Courtesy google.com) Seven Bridges of K ӧ nigsberg , Euler and Graph Theory

(Courtesy of google.com)

Introduction to Graphs A graph is a pair ( V,E ) where V is a set of elements called vertices and E is a set of edges { v,w }. Example: Consider the graph G =( V,E ) where V={1,2,3,4,5} and E={{1,2},{1,3},{3,4},{2,4},{4,5}}. Draw a diagram representing the graph G . Example: Consider the graph G =( V,E ) where V={a,,b,c,d} and E={{a,b},{b,c},{b,d},{b,e}}. Draw a diagram representing the graph G . Example: The table below lists five mobile phone companies and indicates whether they have agreements to roam onto each other's networks. Draw a graph that represents this information, where each vertex represents a phone company and an edge connects two vertices if the corresponding companies have a roaming agreement. Then use the graph to answer the questions: Which phone company has roaming agreements with the most carriers? Which company can roam with only one other network? MobilePlus TalkMore SuperCell Airwave Lightning MobilePlus - No Yes No Yes TalkMore No - Yes No No SuperCell Yes Yes - Yes No Airwave No No Yes - Yes Lightning Yes No No Yes -

Example: An “X” in the table below indicates a direct train route between the corresponding cities. Draw a graph that represents this information, in which each vertex represents a city and an edge connects two two vertices if there is a train route between the corresponding cities. Give a minimal set of routes so that a commuter can travel from Watertown to Newhope. Springfield Riverside Greenfield Watertown Midland Newhope Springfield - X X Riverside - X X X Greenfield X - X X X Watertown X X - Midland X X X - X Newhope X X X -

In general, a graph can include vertices that are not joined to any edges, but all edges must begin and end at vertices. If two or more edges connect the same vertices, they are called multiple edges . If an edge begins and ends at the same vertex, it is called a loop . A graph is called connected if any vertex can be reached from any other vertex by tracing along edges. A connected graph in which every possible edge is drawn between vertices and without any multiple edges is called a complete graph . Two graphs G =( V,E ) and G' =( V',E' ) are isomorphic if there exists a one-to-one and onto function β:V→V' such that for any x,y ϵ V : { x,y } ϵ E if and only if { β(x), β(y) } ϵ E' .

Example: Determine whether the following graphs are equivalent. B C A B C D A D Example: Determine whether the following graphs are equivalent. A D B B A C E C D E

Euler Circuits A path is a graph G=(V,E) such that V={ x 1 , x 2 , x 3 , ... , x n-2 , x n-1 , x n } and E={{ x 1 ,x 2 }, { x 2 ,x 3 }, ... , { x n-2 ,x n-1 }, { x n-1 ,x n }}. If a path ends at the same vertex at which it started, it is called a closed path or a circuit . Note: a path or a circuit is sometimes useful when considered a part of a “bigger” graph. In a graph, a circuit that uses every edge but never uses the same edge twice is called an Euler circuit . Example: Find an Euler circuit in the following graph. A B C D E F G H

Example: Find an Euler circuit in the following graph. A B C D The number of edges that meet at a vertex is called the degree of a vertex. If v is a vertex of a graph G , we write deg( v ) the degree of vertex v . Example: Determine the degree of each vertex in the following graph. A B C D E

A graph with an Euler circuit s called an Eulerian graph. Eulerian Graph Theorem: A connected graph is Eulerian if and only if every vertex of the graph is of even degree. Example: Use the Eulerian Graph Theorem to verify our two examples above on the existence of Eulerian circuits. Example: Recalling the problem of 7 bridges of K ӧ nigsberg, was it possible for the people to take a stroll that would lead them across each bridge and return them to the starting point without traversing the same bridge twice? In a graph, a path that uses every edge once and only once is called an Euler path . Example: Determine if there exists an Euler path of the following graph. A B C D

A Version of Euler Path Theorem: Let G be a connected graph with two distinct vertices x and y of odd degrees . G has an Euler path from vertex x to vertex y if and only if x and y are the only vertices of odd degrees. Example: Verify our last example on the existence of an Euler path using this theorem. Example: Recalling the problem of 7 bridges of K ӧ nigsberg, was it possible for the people to take a stroll such that they start in one of the starting point and end up with a different point with the condition that they cross each bridge without traversing the same bridge twice?

Example: A bicyclist wants to mountain bike through all the trails of a national park. A map of the park is shown on the right. Because the bicyclist will be dropped off in the morning by friends and picked up in the evening, she does not have a preference for where she begins and ends her ride. Is it possible for the cyclist to traverse all of the trails without repeating any portions of her trip?

Example: The floor plan of a warehouse is illustrated on the right. Use a graph to represent the floor plan, and answer the following questions: Is it possible to walk through the warehouse so that you pass through every doorway once but not twice? Does it matter whether you return to the starting point?

Hamiltonian Circuits A Hamiltonian circuit ina a given graph is a path that begins and ends at the same vertex and passes through each vertex of a graph exactly once. A graph that contains a Hamiltonian circuit is called a Hamiltonian graph . Example: Which of the following graphs is a Hamiltonian graph? A B E F J K I C D G H L M N Dirac's Theorem : Consider a connected graph with at least three vertices and no multiple edges. Let n be the number of vertices in the graph. If every vertex has degree of at least n /2 then the graph is Hamiltonian.

Example: The following table shows the availbale flights of a small airline. An “X” means that the airline has direct flights between the two corresponding cities. Draw a corresponding graph for the table. Is there a sequence of flights that visits each city and returns to the starting city without visiting any city twice? Portland Boise Buttle Sacramento Reno Salt Lake City Portland - X X X Boise X - X X X Buttle X - X X Sacramento X - X X Reno X X X X - X Salt Lake City X X X X -

Example: A large law firm has offices in seven major cities. The firm has overnight document deliviries scheduled every day between cetain offices. In the table below, the “X” indicates that there is delivery service between the corresponding offices. Using the law firm's existing delivery service, is it possible to route a document to all the offices and return the document to its originating office without sending it through the same office twice? San Francisco New York Los Angeles Dallas Boston Phoenix Atlanta San Francisco - X X X X New York - X X X Los Angeles X X - X Dallas X - X X Boston X X - X Phoenix X X X - Atlanta X X X -

Weighted Graphs A weighted graph is a graph in which each edge is associated with a value called weight . Example: 1 2 6 3 5 4 Is it possible to find a Hamiltonian circuit with the least sum of weights?

Example: The table below lists the distances in miles between six popular cities that a particluar airline flies to. Suppose a traveler would like to start in Chicago, visit the other five cities this airline flies to, and return to Chicago. Find routes that the traveler could follow, and find the total distance flown for each route. Chicago New York Washington, D.C. Philadelpia Atlanta Dallas Chicago - 713 597 665 585 803 New York 713 - No flights No flights 748 1374 Washington, D.C. 597 No flights - No flights 544 1185 Philadelpia 665 No flights No flights - 670 1299 Atlanta 585 748 544 670 - No flights Dallas 803 1374 1185 1299 No flights -

Example: A tourist visiting San Francisco is staying at a hotel near the Moscone Center. The tourist would like to visit five locations by bus tomorrow and then return to the hotel. The number of minutes spent traveling by bus between locations is given below. (N/A in the table indicates that no convenient bus route is avalable.) Find routes for the tourist to follow and compare the total travel times. Moscone Center Civic Center Union Square Embarcadero Plaza Fisherman's Wharf Coit Tower Moscone Center - 18 6 22 N/A N/A Civic Center 18 - 14 N/A 33 N/A Union Square 6 14 - 24 28 36 Embarcadero Plaza 22 N/A 24 - N/A 18 Fisherman's Wharf N/A 33 28 N/A - 14 Coit Tower N/A N/A 36 18 14 -

Algorithms in Complete graphs From the previous examples, is there a way of finding the best route? There is no known shortcut for finding the optimal Hamiltonian circuit in weighted graph. But there are algorithms in finding a pretty good solution in a comlete graph. The Greedy Algorithm i.) Choose a vertex to start at, then travel along the connected edge that has the smallest weight. (If two or more edges have the same weight, pick any one. ii.) After arriving at the next vertex, travel along the edge of the smallest weight that connects to a vertex not yet visited. Continue this process until you have visited all vertices. iii.) Return to the starting vertex.

Example: Find good routes from the previous examples using the greedy algorithm. The Edge-Picking Algorithm i.) Mark the edge of smallest weight in the graph. (If two or more edges have the same weight, pick any one.) ii.) Mark the edge of the next smallest weight in the graph, as long as it does not complete a circuit and does not add a third marked edge to a single vertex. iii.) Continue this process until you can no longer mark any edges. Then mark the final edge that completes the Hamiltonian circuit. Example: Find good routes from the previous examples using the edge-picking algorithm.

Example: Brian needs to visit the pet store, the shopping mall, the local farmers market, and the pharmacy. His estimated driving times (in minutes) between the locations are given in the following table. Use the greedy algorithm and edge-picking algorithm to find two possible routes, starting and ending at home, that will help Brian minimize his total travel time. Home Pet Store Shopping Mall Farmers Market Pharmacy Home - 18 27 15 8 Pet Store 18 - 24 22 10 Shopping Mall 27 24 - 20 32 Farmers Market 15 22 20 - 22 Pharmacy 8 10 32 22 -

Planarity of Graphs Problem: Three utility companies each need to run pipes to three houses. Can they do so without crossing over each other's pipes at any point? This is a question of planarity!

A planar graph is a graph that can be drawn so that no edges intersect each other (except at vertices). Example: Which of the following are planar graphs?

Does the utility problem above has a positive solution? Subgraph Theorem: If a graph G has a subgraph which is not planar, then G is also not planar. Example: Is the following graph planar?

Euler's Formula In a planar drawing of a graph, the edges divide the graph into different regions called faces . The region surrounding the graph, or the exterior, is considered the infinite face . Example: How many faces are there in each of the following graph?

Euler's Formula In a connected planar graph drawn with no intersecting edges, let v be the number of vertices, e the number of edges, and f the number of faces. Then v + f = e + 2. Example: Verify the graphs from the previous example using the Euler's formula. Example: Determine the number of faces of the following graph and verify using the Euler's formula.

Graph Coloring Francis Guthrie, a South African mathematician and botanist, tried to color a map of the countries of England. He wanted that countries sharing a common border to have different colors. He then noticed that four colors are needed to color the map and so he postulated that four colors are sufficient to color any map. This is now known as the four-color problem . Example: 4-Coloring of the US map.

Example: Suppose the following is a map of a province with different cities. Color the map such that two cities sharing a common boundary have different colors. We can draw a corresponding graph for a map by representing a country by a vertex in a graph and connect two vertices if the corresponding countries share the same boundary. The coloring of map as above corresponds to coloring of vertices such that two vertices which are neighbors have different colors.

Example: Draw the corresponding graph of the map from the previous example and color the graph such that no two neighbor vertices have the same color. Four-Color Theorem Every planar graph is 4-colorable. Example: Consider the map of Central Cebu Protected Landscape (CCPL) on the following page. Construct a graph such that each city/municipality included in CCPL is represented by a vertex and two vertices are connected if the corresponding cities/municipalities share the same boundary. Color the graph and decide whether it is 2-colorable, 3-colorable or 4-colorable.

The minimum number of colors needed to color a graph so that no edge connects vertices of the same color is called the chromatic number of the graph. 2-Colorable Graph Theorem A graph is 2-colorable if and only if it has no circuits that consist of an odd number of vertices. Example: Determine if each of the following graphs is 2-colorable or not.

Applications of Graph Coloring Example: Eight different school clubs want to schedule meetings on the last day of the semester. Some club members, however, belong to more than one of these clubs, so clubs that share the same members cannot meet at the same time. How many different time slots are required so that all members can attend all meetings? Clubs that have a member in common are indicated with an “X” in the table below. Ski Club Student Government Debate Club Honor Society Student Newspaper Community Outreach Campus Democrats Campus Republicans Ski Club - X X X X Student Government X - X X X Debate Club X - X X X Honor Society X X X - X X Student Newspaper X X - X X Community Outreach X X X - X X Campus Democrats X X X - Campus Republcans X X X -

Example: Six film students have collaborated on the creation of five films. Film A was produced by Brian, Chris, and Damon. Film B was produced by Allison and Fernando. Film C was produced by Damon, Erin, and Fernando. Film D was produced by Brian and Erin. Film E was produced by Brian, Chris,and Erin. The college is scheduling a one-day film festival where each film will be shown once and the producers of each film will attend and participate in a discussion afterward. The college has several screening rooms available and two hours will be allotted for each film. If the showings begin at noon, create a screening schedule that allows the festival to end as early as possible while assuming that all the producers of each film can attend that film's screening.

Example: Five classes at an elementary school have arranged a tour at a zoo where the students get to feed the animals. Class 1 wants to feed the elephants, giraffes, and hippos. Class 2 wants to feed the monkeys, rhinos, and elephants. Class 3 wants to feed the monkeys, deer, and sea lions. Class 4 wants to feed the parrots, giraffes, and polar bears. Class 5 wants to feed the sea lions, hippos, and polar bears. If the zoo allows animals to be fed only once a day by one class of students, can the tour be accomplished in two days? (Assume that each class will visit the zoo only on one day.) If not, how many days will be required?

59326111118641-Math-in-the-Modern-World.pptx

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

59326111118641-Math-in-the-Modern-World.pptx

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77