online advertising

Sunday, November 29, 2015

Integral (1)

Let's do some integrals! The good thing about integral is

(a) It requires some tricks to get it done, an interesting intellectual challenge.
(b) It is easy to check if I have got the right answer, even without the model answer, just differentiate it.

Problem:

$ \int{\frac{dx}{\sqrt{x} + \sqrt{x + 1}}} $

Solution:

 The trick is rationalizing:

$ \begin{eqnarray*} & & \int{\frac{dx}{\sqrt{x} + \sqrt{x + 1}}} \\ &=& \int{\frac{dx}{\sqrt{x} + \sqrt{x + 1}}\frac{\sqrt{x + 1} - \sqrt{x}}{\sqrt{x + 1} - \sqrt{x}}} \\ &=& \int{(\sqrt{x + 1} - \sqrt{x})dx} \\ &=& \frac{2}{3}(x+1)^{\frac{3}{2}} - \frac{2}{3}x^{\frac{3}{2}} + C \end{eqnarray*} $

Saturday, November 28, 2015

Scientific Computing - Quiz 4 - Problem 3-13

Problem:

To be copied

Solution:

The differential equation is so easy so we can first solve it analytically, again, using Laplace transform.

First, let $ y(x) = \psi(x - 1) $, that allow us to pose the initial condition at $ x = -1 $ to $ x = 0 $.

$ \begin{eqnarray*} y'' &=& \psi''(x - 1) \\ &=& (\beta - 100)\psi(x - 1) \\ &=& (\beta - 100)y \\ \mathcal{L}(y'') &=& \mathcal{L}((\beta - 100)y) \\ s\mathcal{L}(y') - y'(0) &=& (\beta - 100)\mathcal{L}(y) \\ s\mathcal{L}(y') - 1 &=& (\beta - 100)\mathcal{L}(y) \\ s(s\mathcal{L}(y) - y(0)) - 1 &=& (\beta - 100)\mathcal{L}(y) \\ s(s\mathcal{L}(y) - 0) - 1 &=& (\beta - 100)\mathcal{L}(y) \\ s^2\mathcal{L}(y) - 1 &=& (\beta - 100)\mathcal{L}(y) \\ s^2\mathcal{L}(y) + (100 - \beta)\mathcal{L}(y) &=& 1 \\ \mathcal{L}(y) &=& \frac{1}{s^2 + (100 - \beta)} \\ \mathcal{L}(y) &=& \frac{1}{\sqrt{(100 - \beta)}}\frac{\sqrt{(100 - \beta)}}{s^2 + (100 - \beta)} \\ y &=& \frac{1}{\sqrt{(100 - \beta)}}\sin(\sqrt{(100 - \beta)}x) \\ \psi(x) &=& \frac{1}{\sqrt{(100 - \beta)}}\sin(\sqrt{(100 - \beta)}(x + 1)) \\ \end{eqnarray*} $

Here is the MATLAB code for solving the ODE:

clear all; close all; clc

main driver (just paste into MATLAB)
tol = 10^(-4);
xspan = [-1 1];
A = 1;
ic = [0 A];
beta = 91;
[t y] = ode45('f_rhs', xspan, ic, [], beta);
plot(t, y(:,1))
y(end, 1)

and the function to be solved:

function rhs=f_rhs(x, ic, dummy, beta)
  y1 = ic(1);
  y2 = ic(2);
  rhs = [y2;
         (beta - 100)*y1];

this is the overall code for finding all eigenvalues

clear all;                                         % clear all previously defined variables
close all;                                         % clear all previously defined figures

tol=10^(-4);                                       % define a tolerance level to be achieved by the shooting algorithm
col=[’r’,’b’,’g’,’c’,’m’,’k’];                     % eigenfunction colors
n0=100;                                            % define the parameter n0
A=1;                                               % define the initial slope at x=-1
x0=[0 A];                                          % initial conditions: x1(-1)=0, x1’(-1)=A
xp=[-1 1];                                         % define the span of the computational domain
beta_start=n0;                                     % beginning value of beta

for modes=1:5                                      % begin mode loop
  beta=beta_start;                                 % initial value of eigenvalue beta
  dbeta=n0/100;                                    % default step size in beta
  for j=1:1000                                     % begin convergence loop for beta
    [t,y]=ode45(’f_rhs’,xp,x0,[],n0,beta);         % solve ODEs
    if abs(y(end,1)-0) < tol                       % check for convergence
      beta                                         % write out eigenvalue
      break                                        % get out of convergence loop
    end
    if (-1)^(modes+1)*y(end,1)>0                   % this IF statement block
      beta=beta-dbeta;                             % checks to see if beta
    else                                           % needs to be higher or lower
      beta=beta+dbeta/2;                           % and uses bisection to
      dbeta=dbeta/2;                               % converge to the solution
    end %
  end % end convergence loop
  beta_start=beta-0.1;                             % after finding eigenvalue, pick new starting value for next mode
  norm=trapz(t,y(:,1).*y(:,1))                     % calculate the normalization
  plot(t,y(:,1)/sqrt(norm),col(modes)); hold on    % plot modes
end                                                % end mode loop

Now we can check with the analytic answers - note the output beta values actually lead to full/half cycle of the sine.

In order for $ \psi(1) = 0 $, we need $ \frac{1}{\sqrt{(100 - \beta)}}\sin(2\sqrt{(100 - \beta)}) = 0 $, of course that correspond to $ \sqrt{100 - \beta} $ is a multiple of $ \frac{\pi}{2} $

Friday, November 27, 2015

Scientific Computing - Quiz 4 - Problem 1, 2

Problem:

Consider the differential equation
$ y''' + y'y +y^2 = \cos(t) $

which is the correct conversion of this equation into first-order form

Consider also the boundary conditions

$ y′′(0)=5,y(0)=3,y(1)y′(1)+y(1)=0 $

What is the correct implementation of these boundary conditions in the first-order system.

Solution:

Let $ y_1 = y $, $ y_2 = y' $, $ y_3 = y'' $, we have

$ y_1' = y_2 $
$ y_2' = y_3 $
$ y_3' = y''' = \cos(t) - y'y - y^2 = \cos(t) - y_1y_2 - y_1^2 $

$ y''(0) = 5 \implies y_3(0) = 5 $
$ y(0) = 3 \implies y_1(0) = 3 $
$ y(1)y′(1)+y(1)=0 \implies y_1(1)y_2(1) +y_1(1) = 0 $

Scientific Computing - Quiz 3 - Question 1-3

Problem:

Solve the simple boundary value problem
$ y′′=−4y $ with $ y(0)=0 $, $ y′(1)=\cos(2) $

(Use your above work and solution to continue with this question)

With boundary value problem considered previously
$ y′′=−4y $ with $ y(0)=0 $, $y′(1)=\cos(2) $

Consider instead

$ y′′=−4y $ with $ y(0) = 0 $, $ y′(0) = A $ and use a bisection to compute the iterative values of $ A_1 = 0.5 $ that converge to the solution using a shooting algorithm (NOTE: use your known solution in the interval $t \in [0,1]$. Here assume that $ A_1 = 0.5 $ (too low) and $ A_2 = 2 $ (too high) to compute (a) $A_3$, (b) $A_4$ and (c) $A_5$.

Solution:

Taking Laplace transform on both side gives

$ \begin{eqnarray*} \mathcal{L}(y'') &=& \mathcal{L}(-4y) \\ s\mathcal{L}(y') - y'(0) &=& -4\mathcal{L}(y) \\ s(s\mathcal{L}(y) - y(0))- y'(0) &=& -4\mathcal{L}(y) \\ s(s\mathcal{L}(y))- y'(0) &=& -4\mathcal{L}(y) \\ s^2\mathcal{L}(y) + 4\mathcal{L}(y) &=& y'(0) \\ \mathcal{L}(y) &=& \frac{y'(0)}{s^2 + 4} \\ \mathcal{L}(y) &=& \frac{y'(0)}{2}\frac{2}{s^2 + 4} \\ y(t) &=& \frac{y'(0)}{2}\sin(2t) \\ \end{eqnarray*} $

Now we see the general form of $ y $, using the boundary condition we can solve for the unknown $ y'(0) $ as follow:

$ \begin{eqnarray*} y'(t) &=& y'(0)\cos(2t) \\ y'(1) &=& y'(0)\cos(2) \\ \cos(2) &=& y'(0)\cos(2) \\ y'(0) &=& 1 \\ y(t) &=& \frac{1}{2}\sin(2t) \\ \end{eqnarray*} $

The rest is just bisection.

Note that $ y'(1) = Acos(2) $

$ A $
$ y'(1) $
goal
$ y'(1) $ is …
$ A $ is …
0.5000
-0.2081
-0.4161
too high
too low
2.0000
-0.8323
-0.4161
too low
too high
1.2500
-0.5202
-0.4161
too low
too high
0.8750
-0.3641
-0.4161
too high
too low
1.0625
-0.4422
-0.4161
too low
too high

Note that the question is confusing me saying $ A = 0.5 $ is too low while $ y'(1) $ when $ A = 0.5 $ is actually too high :(

Also be very careful with the requirement for the number of digits.

Wednesday, November 25, 2015

Algorithms: Design and Analysis, Part 1 - Index

Problem Sets:

Problem Set 1:

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 5

Problem Set 2:

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 5

Problem Set 3:

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 5

Problem Set 4:

Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 5

Problem Set 5:

Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 5

Problem Set 6

Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 1
Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 2
Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 3
Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 4
Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 5

Programming Assignments:

Algorithms: Design and Analysis, Part 1 - Programming Question 1
Algorithms: Design and Analysis, Part 1 - Programming Question 2
Algorithms: Design and Analysis, Part 1 - Programming Question 3
Algorithms: Design and Analysis, Part 1 - Programming Question 4
Algorithms: Design and Analysis, Part 1 - Programming Question 5
Algorithms: Design and Analysis, Part 1 - Programming Question 6 - Part 1
Algorithms: Design and Analysis, Part 1 - Programming Question 6 - Part 2

Final Exam:

Algorithms: Design and Analysis, Part 1 - Exam Question 1
Algorithms: Design and Analysis, Part 1 - Exam Question 2
Algorithms: Design and Analysis, Part 1 - Exam Question 3
Algorithms: Design and Analysis, Part 1 - Exam Question 4
Algorithms: Design and Analysis, Part 1 - Exam Question 5
Algorithms: Design and Analysis, Part 1 - Exam Question 6
Algorithms: Design and Analysis, Part 1 - Exam Question 7
Algorithms: Design and Analysis, Part 1 - Exam Question 8
Algorithms: Design and Analysis, Part 1 - Exam Question 9
Algorithms: Design and Analysis, Part 1 - Exam Question 10
Algorithms: Design and Analysis, Part 1 - Exam Question 11
Algorithms: Design and Analysis, Part 1 - Exam Question 12
Algorithms: Design and Analysis, Part 1 - Exam Question 13
Algorithms: Design and Analysis, Part 1 - Exam Question 14
Algorithms: Design and Analysis, Part 1 - Exam Question 15
Algorithms: Design and Analysis, Part 1 - Exam Question 16
Algorithms: Design and Analysis, Part 1 - Exam Question 17
Algorithms: Design and Analysis, Part 1 - Exam Question 18
Algorithms: Design and Analysis, Part 1 - Exam Question 19
Algorithms: Design and Analysis, Part 1 - Exam Question 20

Algorithms: Design and Analysis, Part 1 - Exam Question 20

Problem:

Recall the Master Method and its three parameters $ a,b,d $. Which of the following is the best interpretation of $ b^d $, in the context of divide-and-conquer algorithms?

Solution:

I revisited the lecture video for this one, and now I am explaining in my own words.

The current amount of work is $ O(n^d) $.
The problem size become $ \frac{n}{b} $, and then the amount of work (for the merge step, ignoring recursive calls is $ O((\frac{n}{b})^d) $.

Therefore the amount of work is reduced by a factor of $ O(b^d) $, that's why this option is correct.

(Option 1) The rate at which the work-per-subproblem is shrinking (per level of recursion).

Algorithms: Design and Analysis, Part 1 - Exam Question 19

Problem:

Running time of Strassen's matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence $ T(n)=7*T(n/2)+n$2 $. What's the overall asymptotic running time (i.e., the value of $ T(n) $)?

Solution:

Applying master theorem, we have the variables $ a = 7, b = 2, d = 2 $, and we have the $ 7 = a > b^d = 4 $ case, therefore the answer is $ \theta(n^{\log_2{7}}) $