Math 240 Archives - Page 6 of 9 - Shawn Zhong

3.2 The Growth of Functions

$The Growth of Functions • In both computer science and in mathematics, there are many times when we care about how fast a function grows. • In computer science, we want to understand how quickly an algorithm can solve a problem as the size of the input grows. ○ We can compare the efficiency of two different algorithms for solving the same problem. ○ We can also determine whether it is practical to use a particular algorithm as the input grows. ○ We’ll study these questions in Section 3.3. • Two of the areas of mathematics where questions about the growth of functions are studied are: ○ number theory (covered in Chapter 4) ○ combinatorics (covered in Chapters 6 and 8) Big-O Notation • Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. • We say that f(x) is O(g(x)) if there are constants C and k such that ○ |f(x)|≤C|g(x)| whenever xk. • This is read as “f(x) is big-O of g(x)” or “g asymptotically dominates f.” • The constants C and k are called witnesses to the relationship f(x) is O(g(x)). • Only one pair of witnesses is needed. Some Important Points about Big-O Notation • If one pair of witnesses is found, then there are infinitely many pairs. • We can always make the k or the C larger and still maintain the inequality |f(x)|≤C|g(x)| . • If f(x) is O(g(x)) and g(x) is O(hx)) then f(x) is O(hx)) • You may see “ f(x)=O(g(x))” instead of “ f(x) is O(g(x)).” • But this is an abuse of the equals sign since the meaning is that there is an inequality relating the values of f and g, for sufficiently large values of x. • It is ok to write f(x)∈O(g(x)), because O(g(x)) represents the set of functions that are O(g(x)). • Usually, we will drop the absolute value sign since we will always deal with functions that take on positive values. Using the Definition of Big-O Notation • Example: Show that f(x)=x^2+2x+1 is O(x^2 ). ○ Since when x1, xx^2 and 1x^2 ○ 0≤x^2+2x+1≤x^2+2x^2+x^2−4x^2 ○ Can take C = 4 and k = 1 as witnesses to show that f(x) is O(x^2 ) ○ Alternatively, when x2, we have 2x≤x^2 and 1x^2. ○ Hence, 0≤x^2+2x+1≤x^2+x^2+x^2=3x^2 when x2. ○ Can take C = 3 and k = 2 as witnesses instead. • Example: Show that 7x^2 is O(x^3) ○ When x7, 7x^2x^3. ○ Take C =1 and k = 7 as witnesses to establish that 7x^2 is O(x^3). ○ (Would C = 7 and k = 1 work?) Yes • Example: Show that n^2 is not O(n) ○ Suppose there are constants C and k for which n^2≤Cn, whenever nk. ○ Then n≤ C must hold for all nk. A contradiction! Big-O Estimates for Polynomials • Let f(x)=a_n x^n+a_(n−1) x^(n−1)+…+a_1 x+a_0 where a_0,a_1,…a_n are real numbers with a_n≠0 • Then f(x) is O(x_n). • |f(x)| = |a_n x^n + a_(n−1) x^(n−1)+…+a_1 x+a_0 | • ≤ |an|xn + |an−1| xn−1 + ∙∙∙ + |a1|x1 + |a0| • = x_n (|a_n |+|a_(n−1) |/x +…+|a1|/x_(n−1) +|a_0 |/x_n ) • ≤ x_n (|a_n |+ |a_(n−1) |+…+ |a_1 |+ |a_0 |) • Take C=|a_n |+|a_(n−1) |+…+ |a_0 | and k=1. • Then f(x) is O(x^n). • The leading term a_n x^n of a polynomial dominates its growth. Big-O Estimates for Some Important Functions • Example: Use big-O notation to estimate the sum of the first n positive integers. ○ 1+2+…+n≤n+n+…+n=n^2 ○ 1+2+…+n is O(n^2 ) taking C=1 and k=1 • Example: Use big-O notation to estimate the factorial function f(n)=n!=1×2×…×n ○ n!=1×2×…×n≤n×n×…×n^n ○ n! is O(n^n ) taking C=1 and k=1 • Example: Use big-O notation to estimate log⁡n! ○ Given that n!n^n ○ then log⁡n!≤n⋅log⁡n . ○ Hence, log⁡n! is O(n log⁡n ) taking C = 1 and k = 1. Display of Growth of Functions Combinations of Functions • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1+f_2)(x) is O(max⁡{|g_1 (x)|,|g_2 (x)|} ). • If f_1 (x) and f_2 (x) are both O(g(x)) then ○ (f_1+f_2)(x) is O(g(x)). • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1 f_2)(x) is O(g_1 (x) g_2 (x)). Big-Omega Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • We say that f(x) is Ω(g(x)) if there are constants C and k such that |f(x)|≥C|g(x)| when xk • We say that “f(x) is big-Omega of g(x).” • Big-O gives an upper bound on the growth of a function, while Big-Omega gives a lower bound. • Big-Omega tells us that a function grows at least as fast as another. • f(x) is Ω(g(x)) if and only if g(x) is O(f(x)). • This follows from the definitions. • Example: Show f(x)=8x^3+5x^2+7 is Ω(g(x)) where g(x)=x^3 ○ f(x)=8x^3+5x^2+7≥8x^3 for all positive real numbers x ○ Is it also the case that g(x)=x^3 is O(8x^3+5x^2+7)? Yes Big-Theta Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • The function f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)) • We say that ○ “f is big-Theta of g(x)” ○ “f(x) is of order g(x)” ○ “f(x) and g(x) are of the same order.” • f(x) is Θ(g(x)) if and only if there exists constants C_1, C_2 and k such that C_1 g(x)f(x)C_2 g(x) if xk. • This follows from the definitions of big-O and big-Omega. • When f(x) is Θ(g(x)) it must also be the case that g(x) is Θ(f(x)) • Note that f(x) is Θ(g(x)) if and only if it is the case that f(x) is O(g(x)) and g(x) is O(f(x)). • Sometimes writers are careless and write as if big-O notation has the same meaning as big-Theta. Examples of Big-Theta Notation • Example 1: Show that the sum of the first n positive integers is Θ(n^2 ) ○ Let f(n) = 1 + 2 + ∙∙∙ + n. ○ We have already shown that f(n) is O(n^2). ○ To show that f(n) is Ω(n^2), we need a positive constant C such that f(n) Cn^2 for sufficiently large n. ○ Summing only the terms greater than n/2 we obtain the inequality 1 + 2 + ∙∙∙ + n ≥ ⌈n/2⌉+(⌈n/2⌉+1)+…+n ≥ ⌈n/2⌉+⌈n/2⌉+…+⌈n/2⌉ = (n−⌈n/2⌉+1)⌈n/2⌉ ≥ (n/2)(n/2) = n^2/4 ○ Taking C = 1/4, f(n) Cn^2 for all positive integers n. ○ Hence, f(n) is Ω(n^2), and we can conclude that f(n) is Θ(n^2). • Example 2: Show that f(x)=3x^2+8x log⁡x is Θ(x^2) ○ f(x)=3x^2+8x log⁡x≤11x^2 for x 1, ○ since 0 ≤8x log⁡x≤ 8x^2. ○ Hence, 3x^2+8x log⁡x is O(x^2). ○ x^2 is clearly O(3x^2+8x log⁡x) ○ Hence, 3x^2+8x log⁡x is Θ(x^2)$

3.1 Algorithms

Algorithms • Definition ○ An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. • Example: Describe an algorithm for finding the maximum value in a finite sequence of integers. ○ Perform the following steps: ○ Set the temporary maximum equal to the first integer in the sequence. ○ Compare the next integer in the sequence to the temporary maximum. § If it is larger than the temporary maximum, § set the temporary maximum equal to this integer. ○ Repeat the previous step if there are more integers. If not, stop. ○ When the algorithm terminates, the temporary maximum is the largest integer in the sequence. Specifying Algorithms • Algorithms can be specified in different ways. • Their steps can be described in English or in pseudocode. • Pseudocode is an intermediate step between an English language description of the steps and a coding of these steps using a programming language. • The form of pseudocode we use is specified in Appendix 3. • It uses some of the structures found in popular languages such as C++ and Java. • Programmers can use the description of an algorithm in pseudocode to construct a program in a particular language. • Pseudocode helps us analyze the time required to solve a problem using an algorithm, independent of the actual programming language used to implement algorithm. Properties of Algorithms • Input ○ An algorithm has input values from a specified set. • Output ○ From the input values, the algorithm produces the output values from a specified set. ○ The output values are the solution. • Correctness ○ An algorithm should produce the correct output values for each set of input values. • Finiteness ○ An algorithm should produce the output after a finite number of steps for any input. • Effectiveness ○ It must be possible to perform each step of the algorithm correctly and in a finite amount of time. • Generality ○ The algorithm should work for all problems of the desired form. Finding the Maximum Element in a Finite Sequence • The algorithm in pseudocode: • Does this algorithm have all the properties listed on the previous slide? Some Example Algorithm Problems • Three classes of problems will be studied in this section. • Searching Problems ○ finding the position of a particular element in a list. • Sorting problems ○ putting the elements of a list into increasing order. • Optimization Problems ○ determining the optimal value of a particular quantity over all possible inputs. Searching Problems • The general searching problem is to locate an element x in the list of distinct elements a_1,a_2,…,a_n, or determine that it is not in the list. • The solution to a searching problem is the location of the term in the list that equals x (that is, i is the solution if x=a_i) or 0 if x is not in the list. • For example, a library might want to check to see if a patron is on a list of those with overdue books before allowing him/her to checkout another book. • We will study two different searching algorithms; linear search and binary search. Linear Search Algorithm • The linear search algorithm locates an item in a list by examining elements in the sequence one at a time, starting at the beginning. • First compare x with a1. If they are equal, return the position 1. • If not, try a_2. If x=a_2, return the position 2. • Keep going, and if no match is found when the entire list is scanned, return 0. Binary Search • Assume the input is a list of items in increasing order. • The algorithm begins by comparing the element to be found with the middle element. ○ If the middle element is lower, the search proceeds with the upper half of the list. ○ If it is not lower, the search proceeds with the lower half of the list ○ Repeat this process until we have a list of size 1. ○ If the element we are looking for is equal to the element in the list, the position is returned. ○ Otherwise, 0 is returned to indicate that the element was not found. • In Section 3.3, we show that the binary search algorithm is much more efficient than linear search. • Here is a description of the binary search algorithm in pseudocode. Sorting • To sort the elements of a list is to put them in increasing order (numerical order, alphabetic, and so on). • Sorting is an important problem because: ○ A nontrivial percentage of all computing resources are devoted to sorting different kinds of lists, especially applications involving large databases of information that need to be presented in a particular order (e.g., by customer, part number etc.). ○ An amazing number of fundamentally different algorithms have been invented for sorting. Their relative advantages and disadvantages have been studied extensively. ○ Sorting algorithms are useful to illustrate the basic notions of computer science. • A variety of sorting algorithms are studied in this book; binary, insertion, bubble, selection, merge, quick, and tournament. • In Section 3.3, we’ll study the amount of time required to sort a list using the sorting algorithms covered in this section. Bubble Sort • Bubble sort makes multiple passes through a list. • Every pair of elements that are found to be out of order are interchanged. Insertion Sort • Insertion sort begins with the 2nd element. • It compares the 2nd element with the 1st and puts it before the first if it is not larger. • Next the 3rd element is put into the correct position among the first 3 elements. • In each subsequent pass, the (n+1)\-th element is put into its correct position among the first n+1 elements. • Linear search is used to find the correct position. Greedy Algorithms • Optimization problems minimize or maximize some parameter over all possible inputs. • Among the many optimization problems we will study are: ○ Finding a route between two cities with the smallest total mileage. ○ Determining how to encode messages using the fewest possible bits. ○ Finding the fiber links between network nodes using the least amount of fiber. • Optimization problems can often be solved using a greedy algorithm, which makes the “best” choice at each step. • Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem, but in many instances, it does. • After specifying what the “best choice” at each step is, we try to prove that this approach always produces an optimal solution, or find a counterexample to show that it does not. • The greedy approach to solving problems is an example of an algorithmic paradigm, which is a general approach for designing an algorithm. • We return to algorithmic paradigms in Section 3.3. Greedy Algorithms: Making Change • Example ○ Design a greedy algorithm for making change (in U.S. money) of n cents with the following coins § quarters (25 cents) § dimes (10 cents) § nickels (5 cents) § pennies (1 cent) ○ using the least total number of coins. • Idea ○ At each step choose the coin with the largest possible value that does not exceed the amount of change left. ○ If n = 67 cents, first choose a quarter leaving 67−25 = 42 cents. Then choose another quarter leaving 42 −25 = 17 cents ○ Then choose 1 dime, leaving 17 − 10 = 7 cents. ○ Choose 1 nickel, leaving 7 – 5 = 2 cents. ○ Choose a penny, leaving one cent. Choose another penny leaving 0 cents. • Solution ○ G reedy change-making algorithm for n cents. ○ The algorithm works with any coin denominations c_1, c_2, …,c_r. ○ For the example of U.S. currency, we may have quarters, dimes, nickels and pennies, with c_1=25, c_2=10, c_3=5, c_4=1. • Proving Optimality ○ Lemma 1 § If n is a positive integer, then n cents in change using quarters, dimes, nickels, and pennies, using the fewest coins possible has at most 2 dimes, 1 nickel, 4 pennies, and cannot have 2 dimes and a nickel. § The total amount of change in dimes, nickels, and pennies must not exceed 24 cents. ○ Proof § If we had 3 dimes, we could replace them with a quarter and a nickel. § If we had 2 nickels, we could replace them with 1 dime. § If we had 5 pennies, we could replace them with a nickel. § If we had 2 dimes and 1 nickel, we could replace them with a quarter. § The allowable combinations, have a maximum value of 24 cents; 2 dimes and 4 pennies. ○ Theorem § The greedy change-making algorithm for U.S. coins produces change using the fewest coins possible. ○ Proof § Assume there is a positive integer n such that change can be made for n cents using quarters, dimes, nickels, and pennies, with a fewer total number of coins than given by the algorithm. § Then, q̍q where q̍ is the number of quarters used in this optimal way and q is the number of quarters in the greedy algorithm’s solution. § But this is not possible by Lemma 1, since the value of the coins other than quarters cannot be greater than 24 cents. § Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, and quarters. Halting Problem • Can we develop a procedure that takes as input a computer program along with its input and determines whether the program will eventually halt with that input. • Solution: Proof by contradiction. • Assume that there is such a procedure and call it H(P,I). • The procedure H(P,I) takes as input a program P and the input I to P. ○ H outputs “halt” if it is the case that P will stop when run with input I. ○ Otherwise, H outputs “loops forever.” • Since a program is a string of characters, we can call H(P,P). • Construct a procedure K(P), which works as follows. ○ If H(P,P) outputs “loops forever” then K(P) halts. ○ If H(P,P) outputs “halt” then K(P) goes into an infinite loop printing “ha” on each iteration. • Now we call K with K as input, i.e. K(K). ○ If the output of H(K,K) is “loops forever” then K(K) halts. A Contradiction. ○ If the output of H(K,K) is “halts” then K(K) loops forever. A Contradiction. • Therefore, there cannot be a procedure that can decide whether or not an arbitrary program halts. • The halting problem is unsolvable.

2.6 Matrices

$Matrices • Matrices are useful discrete structures that can be used in many ways. • For example, they are used to: ○ describe certain types of functions known as linear transformations. ○ Express which vertices of a graph are connected by edges (see Chapter 10). • Here we cover the aspect of matrix arithmetic that will be needed later. • Definition ○ A matrix is a rectangular array of numbers. ○ A matrix with m rows and n columns is called an m×n matrix. ○ The plural of matrix is matrices. ○ A matrix with the same number of rows as columns is called square. ○ Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal. • Example: 3×2 matrix ○ [■8(1&1@0&2@1&3)] • Notation ○ Let m and n be positive integers and let § A=[■8(a_11&a_12&…&a_1n@a_21&a_22&…&a_2n@⋮&⋮&⋱&⋮@a_m1&a_m2&…&a_mn )] ○ The ith row of A is the 1×n matrix § [a_i1, a_i2,…,a_in]. ○ The jth column of A is the m×1 matrix: § [█(a_1j@a_2j@⋮@a_mj )] ○ The (i,j)th element or entry of A is the element a_ij ○ We can use A = [a_ij] to denote the matrix with its (i,j)th element equal to a_ij Matrix Arithmetic: Addition • Let A = [a_ij] and B = [b_ij] be m×n matrices. • The sum of A and B, denoted by A + B, is the m×n matrix that has a_ij + b_ij as its (i,j)th element. • In other words, A + B = [a_ij + bij]. • Example ○ [■8(1&0&−1@2&2&−3@3&4&0)]+[■8(3&4&−1@1&−3&0@−1&1&2)]=[■8(4&4&−2@3&−1&−3@2&5&2)] • Note that matrices of different sizes cannot be added. Matrix Multiplication • Let A be an m×k matrix and B be a k×n matrix. • The product of A and B, denoted by AB, is the m×n matrix that has its (i,j)th element equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. • In other words, if AB = [c_ij] then c_ij=a_i1 b_1j+a_i2 b_2j+⋯+a_kj b_kj. • Example ○ [■8(1&0&4@2&1&1@3&1&0@0&2&2)][■8(2&4@1&1@3&0)]=[■8(14&4@8&9@7&13@8&2)] Matrix Multiplication is not Commutative • Let A=[■8(1&1@2&1)],B=[■8(2&1@1&1)], then • AB=[■8(3&2@5&3)],BA=[■8(4&3@3&2)] • Thus AB≠BA Identity Matrix and Powers of Matrices • The identity matrix of order n is the m×n matrix I_n=[δ_ij ], where ○ δ_ij = 1 if i = j ○ δ_ij = 0 if i≠j • I_n=[■(1&&@&⋱&@&&1)] • AI_n=I_m A=A when A is an m×n matrix • Powers of square matrices can be defined. When A is an n×n matrix, we have: ○ A^0=I_n ○ A^r=⏟(AA⋯A)┬(r times) Transposes of Matrices • Let A = [a_ij] be an m×n matrix. • The transpose of A, denoted by A^t ,is • the n×n matrix obtained by interchanging the rows and columns of A. • If A^t = [b_ij], then b_ij=a_ji for i =1,2,…,n and j = 1,2, …,m • The transpose of the matrix [■8(1&2&3@4&5&6)] is the matrix [■8(1&4@2&5@3&6)] Symmetric Matrices • A square matrix A is called symmetric if A=A^t. • Thus A = [a_ij] is symmetric if a_ij=a_ji for i and j with 1≤i≤n and 1≤j≤n. • The matrix [■8(1&1&0@1&0&0@0&1&0)] is square • Symmetric matrices do not change when their rows and columns are interchanged Zero-One Matrices • A matrix all of whose entries are either 0 or 1 is called a zero-one matrix. • Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the following Boolean operations: ○ b_1∧b_2={■8(1&if b_1=b_2=1@0&otherwise)┤ ○ b_1∨b_2={■8(1&if b_1=1 or b_2=1@0&otherwise)┤ Joint and Meet of Zero-One Matrices • Definition: Let A = [a_ij] and B = [b_ij] be an m×n zero-one matrices. • The join of A and B is the zero-one matrix with (i,j)th entry a_ij∨b_ij. • The join of A and B is denoted by A ∨ B. • The meet of of A and B is the zero-one matrix with (i,j)th entry a_ij∧b_ij. • The meet of A and B is denoted by A ∧ B. • Example ○ Find the join and meet of the zero-one matrices § A=[■8(1&0&1@0&1&0)] § B=[■8(0&1&0@1&1&0)] ○ The joint of A and B is § A∨B=[■8(1&1&1@1&1&0)] ○ The meet of A and B is § A∧B=[■8(0&0&0@0&1&0)] Boolean Product of Zero-One Matrices • Definition: ○ Let A = [a_ij] be an m×k zero-one matrix and B = [b_ij] be a k×n zero-one matrix. ○ The Boolean product of A and B, denoted by A⨀B, is the m×n zero-one matrix with (i,j)th entry c_ij=(a_i1∧b_1j )∨(a_i2∧b_2j )∨⋯∨(a_ik∧b_kj ). • Example: Find the Boolean product of A and B, where ○ A=[■8(1&0@0&1@1&0)],B=[■8(1&1&0@0&1&1)] ○ A⨀B=[■8(1&1&0@0&1&1@1&1&0)] Boolean Powers of Zero-One Matrices • Let A be a square zero-one matrix and let r be a positive integer. • The rth Boolean power of A is the Boolean product of r factors of A, denoted by A^[r] . • Hence, A^[r] =⏟(A⨀A⨀⋯⨀A)┬(r times) • We define A^[0] =I_n • The Boolean product is well defined because the Boolean product of matrices is associative • Example ○ Let A=[■8(0&0&1@1&0&0@1&1&0)] ○ Find A^[n] for all positive integers n ○ A^[2] =[■8(1&1&0@0&0&1@1&0&1)] ○ A^[3] =[■8(1&0&1@1&1&0@1&1&1)] ○ A^[4] =[■8(1&1&1@1&0&1@1&1&1)] ○ A^[5] =[■8(1&1&1@1&1&1@1&1&1)]$

2.5 Cardinality of Sets

$Cardinality • The cardinality of a set A is equal to the cardinality of a set B, denoted |A|=|B|, • if and only if there is a one-to-one correspondence (i.e., a bijection) from A to B • If there is a one-to-one function (i.e., an injection) from A to B, then • the cardinality of A is less than or equal to the cardinality of B and we write |A|≤|B| • When |A|≤|B| and A and B have different cardinality, • we say that the cardinality of A is less than the cardinality of B and write |A||B| Countable and Uncountable • A set that is either finite or has the same cardinality as Z+ is called countable. • A set that is not countable is uncountable. • The set of real numbers R is an uncountable set. • When an infinite set is countable (countably infinite) its cardinality is ℵ_0 • (where ℵ is aleph, the 1st letter of the Hebrew alphabet). • We write |S|=ℵ_0 and say that S has cardinality “aleph null.” Showing that a Set is Countable • An infinite set is countable iff it is possible to list the elements of the set in a sequence. • A 1-1 correspondence f from the set of positive integers to a set S can be expressed • in terms of a sequence a_1,a_2,…,a_n where a_1=f(1), a_2=f(2),…,a_n=f(n) • Example 1: The set of positive even integers E is countable set. ○ Let f(x)=2x ○ ■8(1&2&3&4&…@↕&↕&↕&↕&↕@2&4&6&8&…) ○ Then f is a bijection from N to E since f is both one-to-one and onto. ○ To show that it is one-to-one, suppose that f(n)=f(m). ○ Then 2n=2m, and so n=m. ○ To see that it is onto, suppose that t is an even positive integer. ○ Then t=2k for some positive integer k and f(k)=t. • Example 2: The set of integers Z is countable. ○ Can list in a sequence: 0, 1, − 1, 2, − 2, 3, − 3,… ○ Or can define a bijection from N to Z: § f(2n)=−n § f(2n+1)=n+1 • Example 3: The positive rational numbers are countable. § A rational number can be expressed as p/1 where p,q∈Z and q≠0. ○ Note: § p and q such that q≠0. ○ The positive rational numbers are countable since they can be arranged in a sequence • Example 4: Union of countable sets is countable ○ A={a_1,a_2,…,a_n,…} ○ B={b_1,b_2,…,b_n,…} ○ A∪B={a_1,b_1,a_2,b_2,…,a_n,b_n,…} • Example 5: The set of all rationals is countable ○ Q={0}∪Q+∪Q− ○ f(−p/q)=p/q is a bijiection from Q− to Q+ • Example 6: The set of finite string S over a finite alphabet A is counitable infinite ○ A={a,b} ○ List all strings with length § 0: λ § 1: a, b § 2: aa,ab,ba,bb § 3: aaa,aab,aba,abb,baa,bab,bba,bbb § ⋯ • Example 7: Show that the set of all Java program is countable ○ Just list all the strings Hilbert’s Grand Hotel • The Grand Hotel has countably infinite number of rooms, each occupied by a guest. • We can always accommodate a new guest at this hotel. • How is this possible? • Because the rooms of Grand Hotel are countable • We can list them as Room 1, Room 2, Room 3, and so on. • When a new guest arrives, we move the guest in Room n to Room n+1 • This frees up Room 1, which we assign to the new guest, and all the current guests still have rooms. • The hotel can also accommodate a countable number of new guests, all the guests on a countable number of buses where each bus contains a countable number of guests The Real Numbers are Uncountable • The method is called the Cantor diagnalization argument • Suppose R is countable. Then the real numbers between 0 and 1 are also countable • The real numbers between 0 and 1 can be listed in order r1 , r2 , r3 ,… . • Let the decimal representation of this listing be ○ r_1=0.d_11 d_12 d_13… ○ r_2=0.d_21 d_22 d_23… ○ r_3=0.d_31 d_32 d_33… • Form a new real number with the decimal expansion r=0.s_1 s_2 s_3… where ○ s_n={■8(4&d_nn=4@3&d_nn≠3)┤ • r is not equal to any of the r_1,r_2,r_3,… • Because it differs from r_i in its i-th position after the decimal point. • Therefore there is a real number between 0 and 1 that is not on the list • since every real number has a unique decimal expansion. • Hence, all the real numbers between 0 and 1 cannot be listed • so the set of real numbers between 0 and 1 is uncountable. • Since a set with an uncountable subset is uncountable • the set of real numbers is uncountable. Computability • We say that a function is computable if there is a computer program in some programming language that finds the values of this function. • If a function is not computable we say it is uncomputable. • There are uncomputable functions. • We have shown that the set of Java programs is countable. • We can show that the set of functions f:N→N is uncountable • Therefore there must be uncomputable functions$

2.4 Sequences and Summations

$Introduction • Sequences are ordered lists of elements. ○ 1,2,3,5,8 ○ 1,3,9,27,81,… • Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music. • We will introduce the terminology to represent sequences and sums of the terms in the sequences. Sequences • Definition ○ A sequence is a function from a subset of the integers to a set S. ○ The notation a_n is used to denote the image of the integer n. ○ We can think of a_n as the equivalent of f(n) ○ where f is a function from {0,1,2,…..} to S. ○ We call a_n a term of the sequence. • Example ○ Consider the sequence {a_n } where ○ a_n=1/n, {a_n }={a_1,a_2,a_3,…} ○ 1, 1/2,1/3,… Strings • A string is a finite sequence of characters from a finite set (an alphabet). • Sequences of characters or bits are important in computer science. • The empty string is represented by λ. • The string abcde has length 5. Geometric Progression • Definition ○ A geometric progression is a sequence of the form: a,ar,ar^2,…,ar^n,… ○ where the initial term a and the common ratio r are real numbers • Example 1 ○ Let a = 1 and r = −1. Then: ○ {b_n }={b_0,b_1,b_2,b_3,b_4,…}={1,−1,1,−1,1,…} • Example 2 ○ Let a = 2 and r = 5. Then: ○ {c_n }={c_0,c_1,c_2,c_3,c_4,…}={2,10,50,250,1250,…} • Example 3 ○ Let a = 6 and r=1/3. Then: ○ {d_n }={d_0,d_1,d_2,d_3,d_4,…}={6,2, 2/3,2/9,2/27,…} Arithmetic Progression • Definition ○ A arithmetic progression is a sequence of the form ○ a,a+d,a+2d,…,a+nd,… ○ where the initial term a and the common difference d are real numbers • Example 1 ○ Let a = −1 and d = 4: ○ {s_n }={s_0,s_1,s_2,s_3,s_4…}={−1,3,7,11,15…} • Example 2 ○ Let a = 7 and d = −3: ○ {t_n }={t_0,t_1,t_2,t_3,t_4…}={7,4,1,−2,−5…} • Example 3 ○ Let a = 1 and d = 2: ○ {u_n }={u_0,u_1,u_2,u_3,u_4…}={1,3,5,7,9…} Recurrence Relations • A recurrence relation for the sequence {a_n} is an equation that ○ expresses a_n in terms of a_0, a_1, …, a_(n−1) ○ for all integers n with n≥n_0, where n_0 is a nonnegative integer. • A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. • The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. • Example ○ Let {a_n} be a sequence that satisfies § the recurrence relation a_n=a_(n−1)+3 for n=1,2,3,4 § and suppose that a_0=2. ○ What are a_1, a_2 and a_3? ○ a_1=a_0+3=2+3=5 ○ a_2=5+3=8 ○ a_3=8+3=11 Fibonacci Sequence • Define the Fibonacci sequence, f0 ,f1 ,f2,…, by: ○ Initial Conditions: f_0=0, f_1=1 ○ Recurrence Relation: f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5,f_6 ○ f_2=f_1+f_0=1+0=1 ○ f_3=f_2+f_1=1+1=2 ○ f_4=f_3+f_2=2+1=3 ○ f_5=f_4+f_3=3+2=5 ○ f_6=f_5+f_4=5+3=8 Solving Recurrence Relations • Finding a formula for the n-th term of the sequence generated by a recurrence relation is called solving the recurrence relation. • Such a formula is called a closed formula. • Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth. • Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5). • Method 1: Working upward, forward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_2=2+3 ○ a_3=(2+3)+3=2+3∙2 ○ a_4=(2+2∙3)+3=2+3∙3 ○ ⋮ ○ a_n=a_(n−1)+3=(2+3∙(n–2))+3=2+3(n–1) • Method 2: Working downward, backward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_n=a_(n−1)+3 ○ =(a_(n−2)+3)+3=a_(n−2)+3∙2 ○ =(a_(n−3)+3)+3∙2=a_(n−3)+3∙3 ○ =… ○ =a_2+3(n–2)=(a_1+3)+3(n–2)=2+3(n–1) Summations • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m+a_(m+1)+…+a_n ○ ∑_(j=m)^n▒a_j • The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n. • More generally for a set S ○ ∑_(j∈S)▒a_j • Examples: ○ r^0+r^1+r^2+r^3+…+r^n=∑_(j=0)^n▒r^j ○ 1+1/2+1/3+1/4+…=∑_(i=1)^∞▒1/i ○ If S={2,5,7,10} then ∑_(j∈S)▒a_j =a_2+a_5+a_7+a_10 Geometric Series • Sums of terms of geometric progressions • Product Notation • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m×a_(m+1)×…×a_n ○ ∏_(j=m)^n▒a_j$

Math 240

3.2 The Growth of Functions

3.1 Algorithms

2.6 Matrices

2.5 Cardinality of Sets

2.4 Sequences and Summations

Search

WeChat Account