Programming Related « Thoughts on my Mind

Voting and Coding September 13, 2008

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

Well as the title indicates, this post will be mainly about two thing; voting and coding.

Voting:
Don’t you just find it a little discouraging that when you turn 18 you are finally able to vote and be drafted into the military (assuming you are male). What really bothers me about this isn’t so much the service aspect but rather the fact that when I turned 18 I was sent a card saying that I had registered for the selective service. Now I don’t remember doing a damn thing for this, I’m not complaining, but still. On the other hand when I wanted to register to vote I had to go out of my way in order to do so. And you wonder why so few young people decide to vote. It’s viewed as a burden, I mean if they can register for the service on their own they sure as hell can register you to vote, even if it’s as an independent and then you have to go and change your party affiliation if you so desire.

Coding:
This year I think I am going to take programming team practices a little more seriously. I guess it is because now I know that in most competitions I will be able to solve about one or two problems “easily”. However, I would like to be able to do more and in order to accomplish this goal I will have to learn more algorithms (or at least the thought process behind them). At the most recent practice I learned a pretty efficient algorithm for finding the longest common substring between two strings. Before seeing the algorithm I would have been able to do this problem but my method would have been very inefficient and complicated to code.
Also I have finally found a blank CD for me to make a Linux boot CD. I am going to install Ubuntu on my portable hard drive instead of partitioning the hard drive on my desktop or laptop. I really don’t have a problem with having Ubuntu being the main OS on my laptop but I am not sure how to go about installing MatLab on that system so I am going to avoid the potential problems. Also one of my classes works primarally in a Linux environment so having Linux on my comptuer will make things easier (although I could still do most if not all of the work under Windows if I really wanted to).

Sum of Two Squares May 23, 2008

Posted by putnam120 in Math Related, Programming Related.
1 comment so far

I know that I haven’t had a post about math or anything math related for a while, so I think it is time to change this.

Well the problem discussed here really isn’t that difficult but it is interesting enough to mention. “Given an integer $n$ determine if $n$ can be written as the sum of two squares.” For example if $n=29=5^2+2^2$ , however, if instead we had $n=14$ it can be shown that it is not possible to have $14=x^2+y^2$ where $x,y\in\mathbb{N}$ .

Sure you could try using “brute force” to solve this but that is boring and definitely not worthy of its own post. The necessary key insight is a theorem by Fermat. The theorem states that a prime number $p$ can be expressed as the sum of two squares if and only if $p\equiv 1\bmod 4$ . The proof of one direction is not that difficult but a proof of the other direction (that if $p\equiv 1\bmod 4$ then $p$ is the sum of two squares) requires a little more work. I don’t feel like posting them here but feel free to look on Wikipedia, where you will find numerous proofs. The proof by Euler is quite straight forward but is quite long and split into many sections (your call on whether this is a good thing or not). My personal favorite is the first proof by Dedekind using Gaussian Integers.

Now another important fact to know is the following. If two integers, $x$ and $y$ , can each be written as the sum of two squares, then their product, $xy$ can be written as the sum of two squares. The proof is just a basic exercise in equation manipulation, if you have not proven this fact for yourself I suggest you try to in your spare time.

Using these two facts the problem basically boils down to “factor $n$ .” Actually our task is even easier than this, we only need to find the prime factors, $p$ , of $n$ such that $p\equiv 3\bmod 4$ . Thus if $n$ factors as $p_1^{\alpha_1}\dots p_r^{\alpha_r}$ and for some $w$ , $1\le w\le r$ we have that $p_w\equiv 3\bmod 4$ and $\alpha_w$ is odd, then $n$ can not be expressed as the sum of two squares.

Pretty simple, now writing a program to actually do all of these things is a little harder but not by that much.

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.

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)

Change of Interest November 17, 2007

Posted by putnam120 in Life Events, Programming Related.
2 comments

Recently I have been somewhat distracted. Not distracted in the normal sense of the word, it’s just that I have been adsorbed in different things. Until recently I used to be all about Analysis and Putnam preparation. However, now I am quite determined to become better at coding. Currently I am only working in C++ since it was the first language I learned and decided that I should become somewhat efficient with it before learning others. If things go as planned I should start learning Java by the beginning of my junior year. So far I understand the basics; loops, cases/switches, variable types, and functions, mainly I need to learn more about what the various libraries have to offer and how to best use them. A few days ago I was introduced to the algorithm library, and needless to say this saved me a lot of coding. Now instead of having to write a function to sort the elements of a list/vector/array I can just use the sort function and then move on the more important things. Also looked through the vector library and found some useful functions there, but have not needed to use them as often as the ones in the algorithm library.
To get practice I have been doing problems at SPOJ, my only problem with the site is the insane number of test cases they require your code to run, usually around 20000 or more. So even if your code runs perfectly it might not pass because of the time limit constraint. When this happens I just move on to the next problem and might one day come back and attempt to find a solution with better time complexity (faster algorithm in short). Even though not much “high level” mathematics is involved it is a great place to get practice with problem solving since there is usually an obvious (usually brute force) solution but you try to find one that is more efficient. Kind of like finding the elegant solution to a problem. Another site with good problems is Project Euler, even though their problems are geared towards the mathematically enticed programmer.
Don’t get me wrong I am still preparing for the Putnam; currently reading Problem Solving Through Problems (notice how it is no longer under my books I wish to own section). The book is better than all they hype. Sure there are no solutions but if you actually read the sections then there is no real need for one, even though there will be the occasional problem that is just beyond your immediate grasp. Honestly I wish I had purchased this book sooner.
Here is what I will be taking during the spring ’08 semester:

Advanced Calculus 2 (MAA 4212) – MWF
Abstract Algebra (MAS 4301) – MWF
Beginning French 2 (FRE 1131) – MTWRF
Managerial Economics (ECP 3703) – Online

Apart from classes I plan to continue with my coding en devours, as well as read a textbook called “Mathematical Economics and Finance”. Still debating with the prospect of taking more differential equations classes, so I might go and review my notes from Elementary Differential Equations and actually read the book or buy an actual differential equations book geared for the “mathematically gifted”.

May 2012
S	M	T	W	T	F	S
« Jun
		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

Homecoming Weekend October 27, 2008

Comfortable in an Open World October 19, 2008

I Have Wireless September 21, 2008

Voting and Coding September 13, 2008

Sum of Two Squares May 23, 2008

Codes March 27, 2008

My Solutions March 8, 2008

Miller-Rabin and Primes March 4, 2008

Change of Interest November 17, 2007

About...

Recent Posts

Categories

Archive

Blogroll

Feeds

Follow “Thoughts on my Mind”