2008 March « Thoughts on my Mind

Codes March 27, 2008

Posted by putnam120 in Life Events, Programming Related.
add a comment

Well this semester is almost over, and I could not be any happier about it. Classes are starting to get on my nerves. Really it is just the non-math classes but this general feeling of resentment is being carried over to the math classes and that is never a good thing. Economics should have been interesting but it turns out that he spends a semester teaching you how to do basic optimization problems. By basic I mean only require calculus 1 and there are no round off errors. French is being as some would say, “French”. It isn’t so much the class in this case as much as it is the having a test every other week or just about. By the end of the semester you are just burnt out and would rather get a 50 on a test than look at another word of French.

Registration for the next semester is coming up soon for me, I think my registration date is either the 30th or the 31st. In any case I still have to narrow down my class choices. Right now the only classes that I know I will be taking for sure are; Modern Analysis 1 (a first year graduate class) and an Advanced Programming Fundamentals for CIS Majors, which is an introduction to computer science for students with prior programming experience. As for my other classes I am still torn between Introductory Numerical Analysis and Numerical Linear Algebra (another first year graduate class). Regardless of which class I take in the fall, I will be taking Numerical Analysis (the graduate level) in the spring, so chances are I will be taking the Into. Numerical Analysis. Finally there is a Fourier Series and Transforms class being offered which I would really like to take, but after talking to an adviser, I was informed that the class might be canceled if not enough students register.

Things have gotten to the point that in my copious spare time I decide to work on SPOJ problems. The problem that I have just recently completed after about a week is BITMAP, for those of you that are interested. My initial approach was to solve this problem with dynamic programming which seems reasonable. However, it was a few days ago that I learned about what I think is called a “breath first” search. I am not sure if this method is actually faster than the dynamic programming idea I had but it is definitely easier to program for this particular problem. I suppose that actually having a class in C++ would have it’s benefits, mainly in that I would get a better idea of how particular ideas can be used to solve problems. For instance, before I knew about queues but they never seemed useful since it appeared that anything they could do, vectors could do better (I am sure you could create a vector that acts like a queue but it would require unnecessary amounts of code). This is the main reason I am taking the
Advanced Programming Fundamentals class.

Right about now I should be getting back to finishing my take home Abstract Algebra test, which is due tomorrow around 12:30.

Overdue Spring Break Post March 18, 2008

Posted by putnam120 in Uncategorized.
1 comment so far

You don’t realize just how much you need a break until you get one. Mine wasn’t too eventful, I just went back home and decided to relax a little (honestly it was more like a lot). Even though I didn’t do all that much it was still enjoyable.

Firstly I heard back from the REUs that I had applied to last month. I got an offer from one of the REUs and will be working on one of the more interesting problems in my opinion. Here is the description of the project that is provided on their website:

In the mid 1990’s an electronic puzzle called “Light’s Out” became popular. The puzzle consists of a grid of lights, and at the start, some of these lights are on. Pressing one of the lights will toggle it and the four lights adjacent to it on and off. (Diagonal neighbors are not affected.) To win, one must switch off all of the lights. This puzzle can be reformulated in terms of graph theory with vertices representing lights and edges representing adjacency. One can then study graph theoretic properties of the puzzle, as well as optimal winning strategies and “always winnable” graphs.

This project will deal with adding a probabilistic element to the puzzle. One question relates to the expected number of moves required to win under a strategy of randomly pressing vertices on a winnable graph. Another avenue of research would involve assigning probabilities to various edges, so that lights are only toggled on or off with a certain probability when any vertex is pressed. The study of these questions may lead to other interesting variations on this theme.

This program runs from June 2nd to July 25th and is in Holland, Michigan which is only about two hours away from Chicago.

In addition to this great news I got to hang out with some friends. Don’t think I will need to play Guitar Hero for at least another 2 months. Also went and saw Definitely Maybe with Ann, the movie was fantastic until the ending where it all sort of fell apart. I suppose they couldn’t have thought of a better ending. The next movie I want to see is 21, this is kind of a big deal since I normally don’t set out to see specific movies.

Bernstein Polynomial March 17, 2008

Posted by putnam120 in Math Related.
add a comment

Recently in Analysis we learned about a famous theorem due to Weierstrass. This theorem asserts that ANY continuous function on a closed interval can be approximated by a polynomial. The proof in Rudin’s Principles of Mathematical Analysis was kind of easy to follow but really required that you fill in many gaps, as is usual with many of his proofs. However, over spring break I was reading A First Course in Numerical Analysis by Ralston and Rabinowitz and they provided a proof that was not only much easier to follow but seemed more natural to some extent. It should be noted however, that some of the steps in their proof assumed that you have some background in analysis in order to justify some of their claims. Anyway what follows is their statement of the theorem and its proof.

Theorem:
If $f(x)$ is continuous on a finite interval $[a,b]$ , then given any $\epsilon>0$ , there exist and $n$ and a polynomial $P_n(x)$ of degree $n$ such that $|f(x)-P_n(x)|<\epsilon$ , for all $x$ in $[a,b]$ .

Lemmas: The following lemmas are easily proven by the binomial theorem, and thus left to be done so by the reader. (Don’t you just hate when books do this to you)
1: $\displaystyle\sum_{k=0}^{n}{n\choose k}x^k(1-x)^{n-k}=1$

2: $\displaystyle\sum_{k=0}^{n}\frac{k}{n}{n\choose k}x^k(1-x)^{n-k}=x$

3: $\displaystyle\sum_{k=0}^{n}\frac{k^2}{n^2}{n\choose k}x^k(1-x)^{n-k}=\left(1-\frac{1}{n}\right)x^2+\frac{1}{n}x$

Proof:
Define the polynomial $\displaystyle B_n(x)=\sum_{k=0}^{n}{n\choose k}x^k(1-x)^{n-k}f\left(\frac{k}{n}\right)$ . From the lemmas we have that

$\displaystyle\sum_{k=0}^{n}\left(\frac{k}{n}-x\right)^2{n\choose k}x^k(1-x)^{n-k}=\frac{x(1-x)}{n}$ , from this we have that

$\displaystyle f(x)-B_n(x)=\sum_{k=0}^{n}\left[f(x)-f\left(\frac{k}{n}\right)\right]{n\choose k}x^k(1-x)^{n-k}$ . Let $M=\sup{|f(x)|}$ on $[0,1]$ (we can turn any finite interval into $[0,1]$ by a simple rescaling). Now $|f(x_1)-f(x_2)|<\epsilon$ if $|x_1-x_2|<\delta$ . We

next proceed to define two sets, $A=\left\{\frac kn: \left|\frac kn -x\right|<\delta\right\}$ for any x in the interval and $k=0,1,\dots, n$ , and $B$ is the set of remaining points.

Using the above identities we have that $\displaystyle\left|\sum_A\left[f(x)-f\left(\frac kn\right)\right]{n\choose k}x^k(1-x)^{n-k}\right|<\epsilon\sum_a{n\choose k}x^k(1-x)^{n-k}\leq\epsilon$ .

For the set $B$ we have $\begin{eqnarray*} \left|\sum_B\left[f(x)-f\left(\frac kn\right)\right]{n\choose k}x^k(1-x)^{n-k}\right|&\leq & 2M\sum_B{n\choose k}x^k(1-x)^{n-k}\\ &=&2M\sum_B\frac{(k/n-x)^2}{(k/n-x)^2}{n\choose k}x^k(1-x)^{n-k}\\ &\leq&\frac{M}{2n\delta^2}\\ &<& \epsilon \end{eqnarray*}$

for $n$ large enough. (note that $x(1-x)\leq \frac 14$ on $[0,1]$ )

Thus $|f(x)-B_n(x)|<2\epsilon$ .
$\mathbb{Q.E.D.}$

Compared to Rudin’s proof this one is much easier to follow if you actually prove the lemmas. The above proof was given by Bernstein in 1912, it should be mentioned that I might have left out a few details but the general idea is there. In case you didn’t do it, the rescaling done with the interval is just $f(x)\mapsto f\left(\frac{x}{b-a}-\frac{a}{b-a}\right)$ , so $f(a)\mapsto f(0)$ and $f(b)\mapsto f(1)$ and anything in between $a$ and $b$ maps to $f(\alpha)$ with $\alpha\in(0,1)$ .

Challenge Problem:
If $F(t)$ is a periodic continuous function of period $2\pi$ prove that for any $\epsilon>0$ there exist $n$ such that $|F(t)-S_n(t)|<\epsilon$ . Where $S_n(t)=a_0+\sum_{k=1}^{n} \left[a_k\cos(kt)+b_k\sin(kt)\right]$ .

My Solutions March 8, 2008

Posted by putnam120 in Life Events, Math Related, Programming Related.
add a comment

Well spring break officially starts today, even though I started on Thursday after my managerial economics test. After the exam I went out to a club with a friend and her neighbor. It was the second time that we went to this particular club, luckily this time was more enjoyable than the previous visit. Even though I had a great time, I would not say that this was my best clubbing experience. It had nothing to do the people I went with since they are some of my best friends, it’s just that they are not the group of friends that I normally go to clubs with so it was just a little awkward for me and took some getting used to. The next morning I woke up feeling horrible, the only way I know to describe it would be as hung over, but I haven’t had any alcohol in about two to three months. In any case it was not fun getting up and going to my 8:30 class on Friday. Even though I felt like crap class was well worth it, since there were very few people there we got to practice our speaking (this is French class by the way).

As of now I am not exactly sure when my ride back home is leaving, all I know is that it will either be on Sunday or Monday. With the free time I have while waiting to leave I should really be doing the homework so that I won’t have to do it later. Guess I will start on that once I finish this post. Right now I am just reading some C++ books and working on SPOJ problems. I have solved three more problems the only issue is that I need to find a way to improve my method so that I can fit in their ridiculous time constraints.

Well I am going to post my solutions to some of the problems in the previous post.

1:
Choose $x,y,\in{I}$ , then by the mean value theorem there exist an $a\in(x,y)$ such that $f(x)-f(y)=(x-y)f'(a)$ . From the given it follows that $|f(x)-f(y)|<M(x-y)$ , and $f$ being uniformly continuous trivially follows.

2:
part 1: Since $g$ is continuous at $x=0$ , for every $\epsilon>0$ there exist a $\delta>0$ such that $|g(t)-g(x)|<\epsilon$ when $|t-x|<\delta$ . Now choose an $\epsilon>0$ and its corresponding $\delta$ , then
$\left|\frac{f(t)-f(0)}{t-0}-g(0)\right|=\left|\frac{f(t)}{t}-g(0)\right|=|g(t)-g(0)|<\epsilon$ . Thus $f$ is differentiable at $x=0$ and $f'(0)=g(0)$ .

Part two follows with ease.

6:
Let $g(t)=f(t)-\lambda{t}$ , so $g(t)$ is also differentiable on $[a,b]$ , and $g'(a)<0<g'(b)$ . Thus there exist a $\delta>0$ such that $g(t_1)<g(a)$ and $g(t_2)<g(b)$ when $t_1\in(a,a+\delta)$ and $t_2\in(b-\delta,b)$ . Since $[a,b]$ is compact, we know that $g$ attains a minimum value somewhere on the interval; and because it is differentiable on this interval its derivative at this point is 0. So there exist $c\in(a,b)$ such that $g'(c)=0\Longrightarrow f'(c)=\lambda$ .

Miller-Rabin and Primes March 4, 2008

Posted by putnam120 in Math Related, Programming Related.
add a comment

For those of you who do not know, Miller-Rabin is a probabilistic algorithm for testing the primality of numbers. This is different from a deterministic algorithm since with Miller-Rabin there is a change that even if the test says a number is prime that it is in fact composite. However, we can make the probability of this happening so small that we are not worried. On the other hand, if the algorithm says that a number is composite then there is no doubt that it is so.

Here is how the algorithm works. You are given a number $N$ and wish to find out if it is prime. So we choose a random integer $d\in{[2,N-1]$ . First we compute $gcd(N,d)$ , if this is not 1 then we know immediately that $N$ is not prime. If this is in fact 1, we then proceed to calculate $N-1=M\cdot{2^B}$ where $M$ is an odd integer. Next we calculate $d^M\bmod{N}$ , if this is $\pm{1}$ we choose another random integer. If it is not then we proceed with the following “cycle”. Let $Y_1=d^M\bmod{N}$ and continue to iterate in the following manner, $Y_n=Y_{n-1}^2$ , until $n=B-1$ . If none of these $Y_k\equiv{-1}\bmod{N}$ , then $N$ is composite. But if one does satisfy this criteria then $N$ is a probable prime.

Now for the reasoning behind the algorithm. From Fermat’s Little Theorem we know that $a^{p-1}\equiv{1}\bmod{p}$ where $p$ is a prime and $gcd(a,p)=1$ . Using this and a few other techniques we can see that we must have that $Y_B\equiv{1}\bmod{N}$ . Now if $N$ is a prime number then $\displaystyle\mathbb{Z}_N$ is a field and thus there are only 2 square roots of 1, namely 1 and negative 1. Thus if none of the $Y_k$ is equivalent to negative 1 modulo $N$ then we have found a third square root and can immediately conclude that $N$ is not prime.

It can be shown (not it this post) that after running the algorithm with $g$ “testers” (the random integers) which all point to $N$ being prime then the probability that $N$ is composite is $\frac{1}{4^g}$ . Also the algorithm has runtime of $O\left(k\log^3(n)\right)$ where $k$ is the number of testers. It should be noted that this can be improved to $O\left(k\log^2(x)\right)$ if we use the fast Fourier transform to do the multiplications.

Well below is my C++ code for the Miller-Rabin algorithm.

//a plays the role of N and b is the tester
bool MR(long long a, long long b)
{
if(gcd(a,b)!=1)
return false;
unsigned long long Y;
int B=0; //a-1=M(2^B)
long long M=a-1;
while(M%2==0)
{
B++;
M=M/2;
}
Y=RS(b,M,a); //I use repeated squaring, instead of FFT, to calculate b^M
if(Y==1 || Y==a-1)
return true;
int j;
for(j between 0 and M) //this is not real code it just did this so that it would show up in blogger
{
Y=RS(Y,2,a);
if(Y==a-1)
return true;
}
return false;
}

Yes I know this looks ugly (thanks a lot blogger) but it is still readable. Below is the code for the repeated squaring function.

unsigned long long RS(long long a, long long b, long long c) // a^b mod c
{
if(b==0)
return 1;
if(b%2==0)
return (RS(a,b/2,c)*RS(a,b/2,c))%c;
if(b%2==1)
return (a*RS(a,(b-1)/2,c)*RS(a,(b-1)/2,c))%c;
}

This algorithm calculates $a^n$ in $O\left(\log(n)\right)$ time.

Well if any of you are compelled to try using this here are a few cool “easy” problems you can try.
Prime Generator
Prime or Not
(Note: Using Miller-Rabin might not be the best method to solve both of these problems)

S	M	T	W	T	F	S
« Feb				Apr »
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Thoughts on my Mind

Overdue Spring Break Post March 18, 2008

About...

Recent Posts

Categories

Archive

Feeds

Thoughts on my Mind

Codes March 27, 2008

Overdue Spring Break Post March 18, 2008

Bernstein Polynomial March 17, 2008

My Solutions March 8, 2008

Analysis Midterm March 6, 2008

Miller-Rabin and Primes March 4, 2008

About...

Recent Posts

Categories

Archive

Blogroll

Feeds