# Mathematics and engineering

###### Mathematics and engineering
ECE 250 Algorithms and Data Structures Mathematical background Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Mathematical background 2 Outline This topic reviews the basic mathematics required in this course: – A justification for a mathematical framework – The ceiling and floor functions – L’Hôpital’s rule – Logarithms – Arithmetic and other polynomial series • Mathematical induction – Geometric series – Recurrence relations – Weighted averages – CombinationsMathematical background 3 Mathematics and engineering For engineers, mathematics is a tool: – Of course, that doesn’t mean it always works... http://xkcd.com/55/Mathematical background 4 Justification However, as engineers, you will not be paid to say: Method A is better than Method B or Algorithm A is faster than Algorithm B Such comparisons are said to be qualitative: qualitative, a. Relating to, connected or concerned with, quality or qualities. Now usually in implied or expressed opposition to quantitative. OEDMathematical background 5 Justification Qualitative statements cannot guide engineering design decisions: – Algorithm A could be better than Algorithm B, but Algorithm A would require three person weeks to implement, test, and integrate while Algorithm B has already been implemented and has been used for the past year – There are circumstances where it may beneficial to use Algorithm A, but not based on the word betterMathematical background 6 Justification Thus, we will look at a quantitative means of describing data structures and algorithms: quantitative, a. Relating to, concerned with, quantity or its measurement; ascertaining or expressing quantity. OED This will be based on mathematics, and therefore we will look at a number of properties which will be used again and again throughout this courseMathematical background 7 Floor and ceiling functions The floor function maps any real number x onto the greatest integer less than or equal to x: 3.2 3 3   5.266   – Consider it rounding towards negative infinity The ceiling function maps x onto the least integer greater than or equal to x: 3.2 4 4   Necessary because double 1024 have a range just under 2 5.255   – Consider it rounding towards positive infinity long can only represent – The cmath library implements these as 63 numbers as large as 2 – 1 double floor( double ); double ceil( double );Mathematical background 8 L’Hôpital’s rule If you are attempting to determine fn  lim n  gn  lim f n lim g n but both , it follows  nn 1  f n f n  lim lim 1  nn gn  gn  Repeat as necessary… k  th fn Note: the k derivative will always be shown as Mathematical background 9 Logarithms We will begin with a review of logarithms: m If n = e , we define m = ln( n ) ln(n) n It is always true that e = n; however, ln(e ) = n requires that n is realMathematical background 10 Logarithms Exponentials grow faster than any nonconstant polynomial n e lim  d n  n for any d 0 Thus, their inverses—logarithms—grow slower than any polynomial ln(n) lim 0 d n  nMathematical background 11 Logarithms 1/2 Example: is strictly greater than ln(n) f() n n n n ln(n)Mathematical background 12 Logarithms 1/3 3 grows slower but only up to n = 93 f() n n n (93.354, 4.536) ln(n) 3 nMathematical background 13 Logarithms You can view this with any polynomial ln(n) 4 n (5503.66, 8.61)Mathematical background 14 Logarithms We have compared logarithms and polynomials – How about log (n) versus ln(n) versus log (n) 2 10 You have seen the formula Constant ln(n) log (n) b ln(b) All logarithms are scalar multiples of each othersMathematical background 15 Logarithms A plot of log (n) = lg(n), ln(n), and log (n) 2 10 lg(n) ln(n) log (n) 10Mathematical background 16 Logarithms Note: the base2 logarithm log (n) is written as lg(n) 2 It is an industry standard to implement the natural logarithm ln(n) as double log( double ); The common logarithm log (n) is implemented as 10 double log10( double );Mathematical background 17 Logarithms A more interesting observation we will repeatedly use: log (m) log (n) b b n = m , log n b nb a consequence of : log (m) log (n) log (m) b b b n = (b ) log (n) log (m) b b = b log (m) log (n) b b = (b ) log (n) b = mMathematical background 18 Logarithms You should also, as electrical or computer engineers be aware of the relationship: 10 lg(2 ) = lg(1024) = 10 20 lg(2 ) = lg(1 048 576) = 20 and consequently: 3 lg(10 ) = lg(1000) ≈ 10 kilo 6 lg(10 ) = lg(1 000 000) ≈ 20 mega 9 lg(10 ) ≈ 30 giga 12 lg(10 ) ≈ 40 teraMathematical background 19 Arithmetic series Next we will look various series Each term in an arithmetic series is increased by a constant value (usually 1) : n nn1  01 2 3nk  2 k0Mathematical background 20 Arithmetic series Proof 1: write out the series twice and add each column . . . 1 + 2 + 3 + + n – 2 + n – 1 + n . . . + n + n – 1 + n – 2 + + 3 + 2 + 1 . . . (n + 1) + (n + 1) + (n + 1) + + (n + 1) + (n + 1) + (n + 1) = n (n + 1) Since we added the series twice, we must divide the result by 2Mathematical background 21 Arithmetic series Proof 2 (by induction): The statement is true for n = 0: 0 0 01  01 k 0  22 i0 Assume that the statement is true for an arbitrary n: n nn1  k  2 k0Mathematical background 22 Arithmetic series Using the assumption that n nn1  i  2 i0 for n, we must show that n1 nn  12  k  2 k0Mathematical background 23 Arithmetic series Then, for n + 1, we have: nn1 k n1 k   ki  00 By assumption, the second sum is known: nn1   n1  2 n1 2 n1 n   2 nn  12   2Mathematical background 24 Arithmetic series The statement is true for n = 0 and the truth of the statement for n implies the truth of the statement for n + 1. Therefore, by the process of mathematical induction, the statement is true for all values of n ≥ 0. Reference: Mr. OprendickMathematical background 25 Other polynomial series We could repeat this process, after all: 2 2 n n n n 1 2n 1  nn1  2 3 k k   6 4 k0 k0 however, it is easier to see the pattern: 3 2 n n n n 1 2n 1 nn1 n  n 2 k k   63 22 k0 k0 2 2 4 n nn1  n 3 k  44 k0Mathematical background 26 Other polynomial series We can generalize this formula d1 n n d k  d1 k0 Demonstrating with d = 3 and d = 4:Mathematical background 27 Other polynomial series The justification for the approximation is that we are approximating the sum with an integral: n n dd  11 n xn dd k x dx 0   dd  11 k0 0 x0 However, there is an accumulating error: 2 nMathematical background 28 Other polynomial series How large is the error – Assuming d 1, shifting the errors, we see that they would be dd1 n nn d d d1  k n n  21 d k0 2 n = 100 2 n = 10Mathematical background 29 Other polynomial series The ratio between the error and the actual value goes to zero: – In the limit, as n → ∞, the ratio between the sum and the approximation goes to 1 d1 n d1 lim1 n n  d k  k0 – The relative error of the approximation goes to 0Mathematical background 30 Geometric series The next series we will look at is the geometric series with common ratio r: n1 n 1 r k r  1 r k0 and if r 1 then it is also true that  1 k r  1 r k0Mathematical background 31 Geometric series 1 r Elegant proof: multiply by 1 1 r Telescoping series: n k n 1rr   all but the first and last terms cancel k k0 r  1 r k0 nn kk r r r  kk  00  1 r 2 n 2 n n1 (1 r r r ) (r r r r )  1 r n1 1 r  1 r Ref: Bret D. Whissel, A Derivation of AmortizationMathematical background 32 Geometric series Proof by induction: 01 0 1 r k 0 rr1 The formula is correct for n = 0:  1 r k0 n1 n 1 r i Assume the formula r  is true for an arbitrary n; then  1 r i0 n1 n1 n1 nn1 1 r (1 r)r1 r k n 11 k n r r r r  11 rr kk  00 n1 n2 n1 n2 (n1)1 r r1 r 1 r 1 r  1 r 1 r 1 r and therefore, by the process of mathematical induction, the statement is true for all n ≥ 0.Mathematical background 33 Geometric series Note that we can use a changeofindex with summations like we do with integration: n n n i i1 i1 r rr r r  i1 i1 i1 Letting j = i – 1: n1 n 1 r j  r r r  1 r j0Mathematical background 34 Geometric series A common geometric series will involve the ratios r = ½ and r = 2: n1 i n 1 i  1 1  1 n 2  2 2   2   1 2 1  2  2 i0 i0 n1 n 12 kn1 2 21  12 k0Mathematical background 35 Recurrence relations Finally, we will review recurrence relations: – Sequences may be defined explicitly: x = 1/n n 1 1 1 1, / , / , / , ... 2 3 4 – A recurrence relationship is a means of defining a sequence based on previous values in the sequence – Such definitions of sequences are said to be recursiveMathematical background 36 Recurrence relations Define an initial value: e.g., x = 1 1 Defining x in terms of previous values: n – For example, x = x + 2 n n – 1 x = 2x + n n n – 1 x = x + x n n – 1 n – 2Mathematical background 37 Recurrence relations Given the two recurrence relations x = x + 2 x = 2x + n n n – 1 n n – 1 and the initial condition x = 1 we would like to find explicit formulae 1 for the sequences In this case, we have n + 1 x = 2n – 1 x = 2 – n – 2 n n respectivelyMathematical background 38 Recurrence relations We will use a functional form of recurrence relations: Calculus ECE 250 x = 1............. f(1) = 1................... 1 x = x + 2.. f(n) = f(n – 1) + 2... n n – 1 x = 2x + n f(n) = 2 f(n – 1) + n n n – 1Mathematical background 39 Recurrence relations The previous examples using the functional notation are: f(n) = f(n – 1) + 2 g(n) = 2 g(n – 1) + n With the initial conditions f(1) = g(1) = 1, the solutions are: n + 1 f(n) = 2n – 1 g(n) = 2 – n – 2Mathematical background 40 Recurrence relations In some cases, given the recurrence relation, we can find the explicit formula: – Consider the Fibonacci sequence: f(n) = f(n – 1) + f(n – 2) f(0) = f(1) = 1 that has the solution 23  ff nn f(n)ff 55 where f is the golden ratio: 51 f1.6180 2Mathematical background 41 Weighted averages Given n objects x , x , x , ..., x , the average is 1 2 3 n x x x x 1 2 3 n n Given a sequence of coefficients c , c , c , … , c where 1 2 3 n c c c c1 1 2 3 n then we refer to c x c x c x c x 1 1 2 2 3 3 nn as a weighted average 1 c c c c For an average, 1 2 3 n nMathematical background 42 Weighted averages Examples: – Simpson’s method approximates an integral by sampling the function at three points: f(a), f(b), f(c) – The average value of the function is approximated by 1 2 1 f a f b f c  6 3 6 – It can be shown that that 1 2 1 f a f b f c c a   6 3 6 is a significant better approximation than f a f b f c  ca  3Mathematical background 43 Weighted averages Examples: 2 cos(x)dx sin(2) 0.9093  0 1 2 1 1 – Using the weighted average: 6 3 6 1 2 1 cos 0 cos 1 cos 22 0.9150   6 3 6 – Using a simple average: cos 0 cos 1 cos 2  111  2 0.74941 333 3Mathematical background 44 Combinations Given n distinct items, in how many ways can you choose k of these – I.e., ―In how many ways can you combine k items from n‖ – For example, given the set 1, 2, 3, 4, 5, I can choose three of these in any of the following ways: 1, 2, 3, 1, 2, 4, 1, 2, 5, 1, 3, 4, 1, 3, 5, 1, 4, 5, 2, 3, 4, 2, 3, 5, 2, 4, 5, 3, 4, 5, The number of ways such items can be chosen is written n  n   k k n k   n  where is read as ―n choose k‖s  k  n n 11 n   There is a recursive definition:  k k k1 Mathematical background 45 Combinations The most common question we will ask in this vein: – Given n items, in how many ways can we choose two of them – In this case, the formula simplifies to: n nn1  n   2 2 n 2 2  For example, given 0, 1, 2, 3, 4, 5, 6, we have the following 21 pairs:  0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 3, 2, 4, 2, 5, 2, 6, 3, 4, 3, 5, 3, 6, 4, 5, 4, 6, 5, 6Mathematical background 46 Combinations You have also seen this in expanding polynomials: n n  n k nk x y x y    k k0  For example, 4 4  4 kk 4 x y x y    k k0  4 4 4 4 4  4 3 2 2 3 4  y xy x y x y x  0 1 2 3 4  4 3 2 2 3 4  y 4xy 6x y 4x y xMathematical background 47 Combinations These are also the coefficients of Pascal’s triangle: 0   0  11  1  01  11 2 2 2  1 2 1  0 1 2  1 3 3 1 3 3 3 3  1 4 6 4 1  0 1 2 3  4 4 4 4 4   0 1 2 3 4 Mathematical background 48 Summary In this topic, we have discussed: – A review of the necessity of quantitative analysis in engineering We reviewed the following mathematical concepts: – The floor and ceiling functions – L’Hôpital’s rule – Logarithms – Arithmetic and other polynomial series • Mathematical induction – Geometric series – Recurrence relations – Weighted average – Combinations
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom