Break, Trigonometric Function Formula!

Today, I’ll post something about trigonometric functions.

I found a useful posting about this but it’s in Korean so my work will merely translating them.

You can check it here if you can read Korean.

http://blog.naver.com/PostView.nhn?blogId=dalsapcho&logNo=20131746494

First, we will look at the form of ” asinx + bcosx”.

Note that the angles of sin and cos are same.

Think about a circle with 1 radius and its cross point between the vector (a,b)

Then cosΘ is the x-coordinate and sinΘ is the y-coordinate.

Hence, we can prove the formula like the above.

Addition, subtraction etc of trigonometric functions.

The proof is like below.

The reason of A is below

You can get other formula by using the first one.

e.g., but -B instead of B in the first formula.

 So you need to remember only first one.

There are three 2 and 2 things to alternate (sin -> cos, + -> -)

I’ll upload about this if I need it.

Advertisements

Divide and Conquer(Find two closest dots)

I searched up Internet and I got a nice information out of it. So my writing will basically, explain the information from it.

The link is -> http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

————————————————————————————————

It’s a pretty interesting topic in Divide and Conquer(let’s call it DC), I think.

Because, you need to use this to solve many problems.

For example, to make a nice navigation system, you want to know the most fastest way to get to a some point from the present position. Something like that.

There can be many approach to solve this problem.

One of the most naive one will take O(n^2).

For each dot, you will check the distance from it to every other dots.

Can we do better than this?

Yes, by using DC!

Let’s think about the 1-d case first.

First, we sort the point first and divided them as a half.

Second, get the pair with the minimum length from the left and another pair from the right.

So now you might want to compare two things and get the minimum out of it but..

Wait!

There might be a case that the distance of one point from the one side and the point from the other side is the closest pair!

Let’s say we found “%” is the minimum length from S1 and S2. Then, we just need to check the distance of dots in the range of  (m-%, m+%) where m is the mid line.

You might say,

“Well… what if there are a lot of dots in the S1 side that are in the range?”

No! there can be only 1…

If there were more than 1 in the one side, well then they have smaller length then % and it’s contradict our observation.

So there is only one in the (m-% m] and another one [m, m+%), So we need to check only two dots.

So the pseudo code is like below.

The running time for Closest-Pair is O(1) and we need to compare all the input and get the mid point so it’s O(n) work, the total running time will be like this.

T(n)= 2*T(n/2) + O(n)

By using the master theorem,

b = 2, a= 2 and c = 1 hence, 0(nlogn).

2-d case is very similar with this, the only reason I’m doing this is for my term test.

So yes, as you can see now it’s 2-d ,but all the same. (Except for one thing, actually)

We just need to make a mid line according to the one coordinate.

Either x or y doesn’t really matter.

The thing that has changed is the number of dots that can be around the mid line, when we need to check them.  But don’t worry, the points in the P1 and P2 have a bit interesting feature with them.

To find a point to be the closest pair in the other side, p have two box to check.( i.e., check upside and downside to the left side. )

And the box can only contain up to 6 points.

For one side there can be 2/n points, and for each point for 2/n points there are 6 points at the other side to get the distance from it.

Nasty! Right?

I do agree. CS is very powerful but super Nasty….. :S

But it will pay off… hopefully!

If you ask why there are 2/n points at one side just think, that we divide n points by half

so for each side there are n/2 points and for the worst case they are all in the range of

delt/2 from the mid line.

So the comparing took 6* n/2  hence it’s O(n).

So T(n) = T(n/2) + T(n/2) + O(n)

T(n/2) => get the closest pair from the one side

Okay by the 2-d, we can go for n-d but I don’t want to right now..

This is done for today!

Divide and Conquer(n-bits integer multiplication)

Yesterday, I watched a Youtube video of a Statistics Introduction class in Harvard. A prof in the video said, “The best way to solve any problem is divide to the small piece of problem and work it out from them and combine later on”.

Yes, I do agree. Bit by Bit.

So the algorithm, I’ll talk about is totally same thing.

You just divide the problem into few pieces and solve and put them back.

There are few interesting problem, we can look at it.

1) Multiply lots of bits

In our computer, we can’t store enormous size of integer due to the limitation of storage problem.

So the program was multiplying two integers and you got 2 integers with huge length, how would you treat them?

You can divide and calculate small amount and store it first, and precede your work till you reach to the end. At last, you can just combine the all little solution in to one piece.

Let’s get to the detail.

Let’s say your computer only store 2 integer like 11, 22, 01 at one time and You want to compute the multiplication of the above.

How would you do that?

First, you break 1101 to 11,01 and 1011 to 10,11 and you have 4 pieces.

And multiply them by units and put them in their position later.

So the formula for doing that is like above.

n is 4 here because it’s 4 bit integer. i.e., 1101 is composed of 4 integers.

You might feel frustrated when you looked at 2^n and 2^(n/2). This is just messy stuff. I know. But just think since x1 actually is 1100 = 11 * 2^2 ( 2 = n / 2 ) and y1 is actually also 10000 = 10 * 2^2

but we treat them as if they are 11 and 10. We need to pay back what we borrowed from them.

Since we borrowed half and half and after the multiplication it became n (b/c n/2 + n/2 = n)

So it became 2^n and x1y0 we only mistreat x1 here and for y1x0 we only mistreat y1 so we need to pay 2^n/2 here.

It’s like that.

Seems darn boring. But there’s an interesting trick with this.

It’s called “Gauss’ trick”.

In the original image

we need to compute 4 things but by using the trick we only need to compute 3 chunks.

So if you have 2 n-bit integers, you need to n^2 multiplication but by using the trick, you need to work less.

That’s sort of saving but not much because you need to manipulate some code more and it just only make one multiplication less.

Well, sounds bit boring. Hmm.

Well. Next page might be more interesting I guess.

In the next problem, you will try to look for the closed pair of dots.

Sounds more fun?

Yay………………………

Midterm Preparation(problem and the answer)

Like prof said, it will be enough if we cover the quiz 1, quiz 2 and quiz 3 and the additional material ,So here we will solve some problems straightly for each.

Quiz 3

1.6.

Compactness: If a set S is closed and bounded, it’s compact.

Characterization of compactness (BW): S is compact if and only if every sub-sequence has a convergent sub-sequence whose limit is in S.

Extreme Value theorem: if f is continuous ans S is compact then f has an absolute minimum value and an absolute maximum value on S.

1.7.

Disconnection: if S = S1 U S2 and S1 ∩ S2 closure = empty and S1 closure ∩ S2  = empty

connected set: if the set is not disconnected, then the set is connected.

Intermediate value theorem:  If f: S -> R and V is a subset of S and if a, b are elements in V, and f(a)< t < f(b) then, there is c included in V such that f(c) is = t.

2.1.

Differentiability in R:  there should me a number m, such that  f(a+h) = f(a) + mh + E(h), where E(h) /h->0

Role’s theorem: if f is continuous on the [a,b] and f(a) = f(b) and f is differentiable on (a,b) then there should be c, such that f ‘(c) = 0.

Mean Value theorem: if f is continuous [a,b] and differentiable on (a,b) then there is c such that

f ‘(c) = f(a) – f(b)/ a – b

1.6. compactness

a. S = [1,3] then f(x) = 1/x-2 (x != 2) and 1 when x = 2.

b. f(x) = c, c for some constant

The answer of the text book:

 

Because, R is both open and closed. ( I forgot about it!)

a. 1/x

b.

1.7.

a. x >= 0 and x < 0 because the graph is like below.

b. a included in R, R/a

c. x + , x- case

For my mind, there is a vague answer

which is just getting two points and make a plane and cut the sphere with the plane and make the function  that goes around the arc.

There is an answer for this problem! I got almost right except for thing that I forgot to add origin to make a plane(How come I came up with the idea that I want to make a plane with just two points!)

I understand this proof finally! Yeah! This is glorious for me!

But not by the proof that is given from the text I think there’s something wrong..

Because, f(0) = (2,0) I think it should be f(0) = (2,1) because there’s no (2,0) in S.

However, I found more conceivable prf

Correctness(1)

I’m so lost in the lecture of correctness.

We didn’t go through to the end (to the point about loop invariant) but I felt bit lost.
Actually I wonder whether it’s practical because it takes too much time for even one merge sort to prove something. Well, anyway let’s start. (at least it will give me a mark)

Well, for me, if I think about “correct” the first thing comes to my mind is AUTOCORRECT lol.

LoL, but it ,of course, means something different in Computer Science.

Program is a function. You give a input and it gives you a out put.

Let’s say it supposed to get sugar from you and gives back a candy to you.

But what if you put salt by mistake? Even if I can get a candy from the program, I don’t think it’s worthwhile to try.

So, here we go, Precondition is correctness of input.

You must give it to sugar, not salt nor white beach sand.

So if you give the correct input, you must get a correct output which is a candy.

But what if you got a …report card that trashed?  It might remind of your old days.

 

Oh, that’s no good.

So the correctness of output is PostCondition.

So it looks like we got everything that must be “correct” when we’re running a program.

But, what if after you put a sugar and you waited but it doesn’t come out? 

Like jammed printer.

How much time are you going to wait for a silly candy?

while sleeping?

The program must exist some point (i.e., it must give me a candy!)

So, the correctness includes the part of termination of program.

So by means that the program is correct is postcondition, precondition and termination should holds.

Easy? right?

This is the basic of correctness!