Question? Leave a message!




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