Beauty: March 2008

Thursday, March 27, 2008

Codes

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.

Tuesday, March 18, 2008

Overdue Spring Break Post

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.

Monday, March 17, 2008

Bernstein Polynomial

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]$ .

Saturday, March 08, 2008

My Solutions

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$ .