Posts

Showing posts with the label algorithm

Prove that (f+g)(x) is an odd function, if f and g are odd functions (Stewart, Calculus)

-
Suppose f(x) and g(x) are odd functions. Prove that (f+g)(x) is also an odd function.  Answer:  1. Strategy By definition, f is an odd function if and only if f(-x) = - f(x) To show (f+g) is an odd function, we need to show (f+g)(-x) = - (f+g)(x) 2. Explanation Since $f(x)$ and $g(x)$ are odd functions $\Rightarrow f(-x) =-f(x)$ and $g(-x) =-g(x)$ By definition of sum of functions. $(f+g)(-x) =f(-x)+g(-x)$ $=-f(x)-g(x)$ $=-(f(x)+g(x))$ $=-(f+g)(x)$ (by definition of sum of functions) $\Rightarrow(f+g)(-x) =-(f+g)(x)$ $\Rightarrow f+g$ is an odd function. Q.E.D. 
Post a Comment
Read more

[Java] Excercise: compare two given arrays and determine their equality

-
Motivation: In Java, c heck if Two Arrays are Equal or not Equal. a={1,2,3,4,5,6} b={2,3,1,4,5,4,4} Time complexity: $O(n^2)$ (because of the bubble sort algorithm) - Version 1: 1 process. double-nested loop statement. - Version 2: 2 processes. 1) bubble sort algorithm: $O(n^2)$, 2) single-nested loop statement O(n) - Version 3: 1 process. 1) Arrays . equals ( a , b ): $O(n^2)$ (still $n^2$) - Version 4: 2 processes. 1) check lengths of arrays, 2) sort arrays, 3) compare elements of arrays. Still $O(n^2)$ because of sorting arrays. Java codes import java.util.Arrays ; public static void main ( String [] args ) { int a [] = { 1 , 2 , 3 , 4 , 5 , 6 }; int b [] = { 2 , 3 , 1 , 4 , 5 , 4 , 4 }; boolean result = true ; // version 1 // determine whether two arrays are equal, by comparing elements one-by-one: version 1 // this is theta(n^2) algorithm for ( int i = 0 ; i < a . length ; i ++) { for ( int j = 0 ; j < b . len...
Post a Comment
Read more

[Math] Taking a square root of a number: finding an upper limit for factors of a non-prime number (Eratosthenes)

-
Eratosthenes has discovered that "a non-prime number has its factor (other than 1) that is less than the square root of the number."  1) Task: finding an upper limit for factors of a non-prime number.    2) Motivation: suppose number = 100 square root (100) = 10 factors of 100 = {1, 2, 4,5, 10, 20, 25, 50, 100}  Note that factors of 100 exist  before the square root of 100 (= 10). Namely, 1, 2, 4, 5 are those. With exception of 1, we have found prime factors of 10 that are less than 2,4, and 5. That's good enough information to determine that 100 is not a prime number.   3) An idea for mathematical proof would be: 1. suppose a number is a non-prime number. That is, this number = M * N where M>N > 0  2. multiplying N to both sides of the inequality  M>N results M*N > N^2  3. by design, this number = M*N > N^2 4. taking the square root, we have (M*N)^(1/2) > N  conclusion: a factor of a non-prime number is l...
Post a Comment
Read more