Hashtables

Well I was looking for a hash-map in C++ since doing something like

myMap[i];

Where myMap is an std::map<> takes logarithmic look up.

So after some looking around I did manage to find that there were hash-maps for C++, but after that I had to do some more searching to see what libraries I needed to include in order to use them.

Below is a little program that just prints the integers 1 to 10 followed by hello world, that makes use of a hash-map.

#include<iostream>
#include<ext/hash_map>
#include<string>
using namespace std;
using namespace __gnu_cxx;

int main()
{
 hash_map<int,int> myhash;
 for(int i=0;i<10;i++)
     myhash[i]=i+1;
 for(typeof(myhash.begin()) i=myhash.begin();i!=myhash.end();i++)
     cout<<i->second<<' ';
 cout<<"hello world\n";
 return 0;
}

Certainly not the most user friendly stuff to type at the beginning but I suppose it is worth it. I should mention that when I wrote the second for loop I had no idea if it would compile or not since I didn't know that you could use iterators on hash_maps. Also unlike std::map, __gnu_cxx::hash_map does not store the keys in an ordered fashion, just something to be aware of.

As a side note, if you didn't add the line

using namespace __gnu_cxx;

you would have to type

__gnu_cxx::hash_map<Tyep&key,Type&value>;

This should be obvious but you never know when/if you'll one day forget.

Annoyance

Well I decided that this year I would like to keep better track of what I listen to, so that when I make the "Best of 2009" post the numbers will be more accurate. Only problem is that I can't for the love of me enable the Last.fm scrobbling program while using Ubuntu. Well that's not entirely true. I've gotten it so that it recognizes the song, the only problem is that when I get it to do this I am unable to actually play the song with my media player. I've looked around and have a general idea of what is causing this problem. Only thing is that I haven't been able to find a solution, well I'm sure I could but right now it's not at the top of my priority list. In addition to this I use pandora quite a bit, and I'm not sure if it keeps track of your listening trends the say way Last.fm does. Oh well.

So I'm using my Windows XP computer for the first time in a few months. One thing I will say is that I miss having a gcc compiler. I have Dev-C++ which usually pretty close to being the same but it's just not the same. I looked around and found a way to get the compiler I want for XP but don't really feel like doing all the necessary work right now, I'll probably end up doing it around the time of finals. The only reason this is a bother is because when I submit solutions to SPOJ problems there is a small chance that there might be a compilation error. It would be really cool if there was an online "compiler" so that I could check before submitting (this is when I'm not writing the program under Ubuntu of course).

One last thing, for those of you who continually ask "What are you going to do with a math degree?" or "Why math?" Here is an answer I'm sure you'll like. Notice how the top rated jobs are mostly math/science related.

Efficient Finals

Well I was reading an algorithms book and here is something that was pointed out that I never considered before.

Assigning times for Final Exams is equivalent to coloring a map.

How so? Well assume that we only have the following restriction, two finals can not be at the same time if they share at least one student. Now let the classes be the vertices of the graph, and place an edge between any two vertices if they share a student. So basically you assign colors (or times) in a way such that no edge has vertices of the same color.

Obviously the four color theorem does not apply when coloring this graph. Just consider the case where a student is taking 5 classes. (go and look up to see how this breaks the necessary assumptions for the theorem). None the less it is still an interesting connection, though I am sure Universities do not use this method to schedule their finals (for some obvious reasons).

Greed

Well I didn't manage to completely solve a SPOJ problem today, what a shame. I managed to think of a method of attack but didn't have the time or motivation to try and code it up or even write pseudo-code. The problem statement can be found here, since I don't want to accidentally leave out any details.

The method I am going to try combines a binary search and greedy algorithm.
First create a sorted array of all the locations of the stalls, then a second array that will keep track of which stalls have cows. Call these arrays A and B respectively. Through out my explanation assume that both arrays are always sorted. Now if you only have 2 cows you place them in the extreme left and right stalls, so add these stalls to B. The general idea is that the best location for cow (N+1) can be built from the best location for cow N. For example, to add the third cow look at the stall that is "half-way " between the 2 stalls with cows. Is the minimum distance at this point less than if you were to move it left or right by one stall? If so add this stall to B. If not do the same thing by looking at the midpoint of the left and right halves (some case work might be able to be applied to minimize this but I haven't thought about it yet). After doing this you can find the best spot for the third cow. To add the 4th cow look at the "interval" between cows 1 and 3, and the interval between cows 3 and 2, and apply the above method.

I haven't really considered the time constraint and input sizes but I might be able to get away with a linear search for the best spot (though I doubt it). I suppose that TopCoder article I read on binary search is coming in handy. Well I probably won't be able to work on this again until Tuesday so hopefully I'll be able to work out any "bugs" before I sit down to code.

*UPDATE: Well I managed to actually write up the code for this earlier than expected. However, there was a change in how I went about doing it. I instead did a binary search on all the possible distances between the stalls, in order to find the largest possible minimum. Basically given a distance and the number of cows I would perform the following operation;

bool(stall, distance, cows) //where they are all the appropriate data type
num=1;
prev=stall[0];
for i from 1 to one less than the number of stalls
. if stall[i]-prev is less than distance do nothing
.else prev=stall[i] and increase num by 1
end for loop
return true if num is at least as big as cows, else return false

This basically tells you the maximum number of cows you can place so that the distance between any 2 is "distance". So if I remember correctly the possible distances between stalls were between 1 and 1 billion. So the above should only needed to be run no more than 30 times.

Making a Fence

Another day and another SPOJ problem complete ( link to problem). In this one you had to implement a way to find the convex hull of a given set of points. This one wasn't that horrible since I already knew a method to perform the desired task. The only problems I encountered were, 1) what do you do about collinear points and 2) what about one and two point sets? Luckily there were examples that covered both of these issues so I adjusted my code accordingly.

The method I used is known as the Graham Scan. First you find the most lowest point, or furthest left point (I personally like to chose the lowest, but going with the furthest left doesn't really change anything). After this is done you sort the remaining points according to the angle the line connecting them and the lowest point, makes with the x-axis. Then create a stack, and add the first two points (the lowest point and the one with the smallest angel measure). I should clarify that this is not actually a stack since we will need the ability to access both the top and second elements. What you do next is easier to explain with pseudo-code in my opinion at least so here it is:

for i=3 to the size of P //P is the collection of points
. while stack.size>=2 and cross(stack.second, stack.top, P[i])<=0)
.. s.pop //remove the top element
. s.push(P[i])

Basically if a right turn is made (cross product less than 0) or collinear points (cross product equal to 0) the point at the top of the stack is not part of the convex hull. If you don't follow draw some points, if you ever make a "right turn" you are moving "out" and thus it is more efficient to not consider the point at where you turned right. (hope that helped). Supplementary stuff: This could be improved by first finding the points with the largest and smallest x and y coordinates. These four points will form a quadrilateral (assuming you have at least 4 points that is), if any point is inside this quadrilateral it is clearly not part of the convex hull, so you only need to consider the remaining points. I would like to get around to adding this to my code by I am a little stuck at finding a way to determine if a point is in the quadrilateral or not.

In case you were wondering this is a O(n*log n) algorithm.

Minimum Spanning Tree

While online I realized that I visit the same sites on a regular basis. So I decided to look through my bookmarks to see what sites I haven't visited in a while. Hey look what I found, SPOJ. Why not try to solve as many problems as I can over this break? I already have bookmarked a few problems I have found to be particularly interesting or will make me implement an algorithm I know but have not coded before.

Well I decided to start with a problem where I was asked to find the minimum spanning tree of a given graph. This falls under the "found to be interesting" category. After thinking about it for a while Dijkstra's Algorithm came to mind, and I said "instead of adding the vertex that has the shortest path to the starting point, why don't I just add the smallest weight?" So I wrote a program to solve the problem this way, with out caring about how efficiency. Then testing it against the example they gave I saw that it worked. So now time to do some improvements, but first to look around the internet (aka Wikipedia) to see what other attacks there are that I might not have considered.

Turns out that the method I though of is known as Prim's Algorithm. Unfortunately the pseudo-code that Wikipedia provided was difficult to follow, but luckily I didn't have to search hard for a site with pseudo-code I could understand. However, there is one thing I still don't understand. Each of the sites mentions how you can put the edges into a heap to help make searching faster. First I don't see how this helps and second how does one decide how one edge comes before another in the heap? Well I guess I'll have more time to consider this.

Here is my implementation of the algorithm, I believe it runs in O(EV) time. Sorry for the horrible formatting, I really wish that blogger would just not auto-format stuff the way MSWord does, so annoying.

void mst(vector&E,int N)
{
vector found(N+1,false);//vector of already solved vertices
found[0]=found[1]=true;
long long wgt=0;//total weight
tpl temp=tpl(-1,-1,-1);

while(N-1>0)
{
vector::iterator II=E.begin();
int sh=2000000;
for(vector::iterator I=E.begin();I!=E.end();++I)
{
tpl R=*I;
if(found[R.first]==true && found[R.second]==false)
{
sh=R.third;
temp=R;
II=I;
break;

}
else if(found[R.first]==false && found[R.second]==true)
{
sh=R.third;
temp=R;
II=I;
break;
}
}
N--;
found[temp.first]=found[temp.second]=true;//another vertex has been solved for
wgt+=temp.third;//update total weight
E.erase(II);
print(found);//print found vertices, used to debug
}
printf("%ull\n",wgt);
}

Oh Java

Well I have been doing a project in Java (obviously not my choice, I would rather be using C++). I have started to get annoyed with how verbose Java can be at times. For instance say you have two string, string1 and string2, and you wanted to see if they were the same; instead of just typing string1 == string2 like you would be able to in C++ you have to type string1.equals(string2). I should note that string1 == string2 is allowed in Java but it checks to see if the two objects point to the same location in memory, and in most cases this is not what you want to check. But check this out, apparently if you want to compare two characters using the == operator is perfectly fine, gosh Java just make up your mind already. Well that's enough Java bashing for a while, I suppose that I just prefer C++ because it is what I learned first and have been using for much longer. I will admit though that Java does have its upsides (this will be left for another post).

The other day I got around to wondering why I never needed to defragment. the drive with Linux. I have just had people tell me this and have read it online but never actually got around to seeing why. So I got on Google did a quick search and found my answer, and was quite pleased with the result. Here is a link to probably the easiest explanation to follow. After reading that article I saw on the page a link to something about how to "properly delete files", something I have always wondered about and now was just as good a time as any to read about it. I won't go into it too much here, but when you just hit the delete button it is similar to just deleting the pointer that tells you where the information is stored and not the information itself. If you want a better explanation and information on how to "delete" the information just follow this link (you will see why I put delete in quotation marks once you read the article/post).

Homecoming Weekend

Well I was not on campus, as a matter of fact I wasn't even in Gainesville, for homecoming this year. Instead I was attending the ACM ICPC Southeast Regional (a programming competition for college students). We took four different teams this year. It was my first time going and I didn't do all that well on the placement test so as a result I ended up on the 4th team. At the competition we managed to answer 3 of the 10 questions and finished 21st out of abut 62 teams. Also we beat the 3rd team. Our school's first team answered 5 questions and got 2nd place (the fist place team also answered 5 questions), while our 2nd team answered 4 question and I am sure that they were in the top 10. Overall I believe that we did very well, considering we were with out the aid of the C++ STL and Java API refernce sites which we were promised.
Any case, it is time to prepare for next year's competition. My goal is to be on the fist team and get 1st place.

Comfortable in an Open World

Now when I use my laptop I mostly boot into Ubuntu Hardy (8.04). The only time I boot into Windows Vista (which I still think is a better OS than XP) is when I need to use MATLAB. However, this is becoming more of a rarity since I have started using Octave and have become quite comfortable with its interface. In addition I find that compiling and running programs is much easier under Ubuntu. I suppose I could set it so that it is just as easy under Vista but that would require some work. All of the applications I use on Ubuntu are Open Source, with the exception of Adobe, and this is only because I find that it is considerably better than any of the Open Source aternatives I have found thus far. I used to have WINE installed but removed it once I realized that I had no need for it sicne it could not install MATLAB and I'm not much of a gamer so really everything I need can be done with Linux compatable programs.

As far as programming goes I have started using Java. It isn't that difficult to pick up since I know C/C++ it just takes a little getting used to. I might go back and try to convert some of the solutions I did for SPOJ problems and convert them to solutions in Java (they are all in C++). Learning a new language really can't hurt since there are some problems I see and am like "I know how to do that but I can't fit the necessary data into as a long long (64 bits) is C++, if only I could use Java's BigInteger."

Next week is the South East Regional Programming Competiton for ACM. Wish me luck. I feel pretty prepared, I have a grasp of most of the basic algorithms we coverd. It is just coming up with the correct data structures to use that is giving me problems now, but that should soon be fixed.

I Have Wireless

So I have finally managed to get my wireless card working with Ubuntu 8.04. You have no idea how happy I am about this. I have been wanting to really give Ubuntu a try but have always been reluctant to because of the fact that it wouldn't work with my wireless card and I would need an ethernet cable in order to connect to the internet. Now I know this happiness will not be too long lived because once I update to the next version of Ubuntu (which in my case will probably be 9.04 and not 8.10) I will most likely have to go through the same process again and hope that it still works on the new version.

On a more "depressing" note; I managed to finish only half of one my my 5 analysis homework problems. They all seem to be about connected sets. One of the funny things is that in Rundin for a set to be connected it must not be able to be written as the union of two separated sets. However, on Wikipedia, Mathworl, and one of my other analysis text they also say that the separated sets must be open sets. Now I know that if two open sets are disjoint they are separated so I don't see the real need for this extra assumption. In any case the problem I managed to solve was as follows.

Let A and B be two connected subsets of a metric space X. Show that is A and B have nonempty intersection then their union is also connected.

The second half of the problem asked us to state and prove a generalized version of this for the union of arbitrary connected sets. I came up with:

Let {A} be collection of connected sets. If for each F in {A} there exist a G in {A} such that the intersection of F and G is nonempty then the union of all the members of {A} is a connected set.

Voting and Coding

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

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 determine if can be written as the sum of two squares." For example if , however, if instead we had it can be shown that it is not possible to have where .

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 can be expressed as the sum of two squares if and only if . The proof of one direction is not that difficult but a proof of the other direction (that if then 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, and , can each be written as the sum of two squares, then their product, 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 ." Actually our task is even easier than this, we only need to find the prime factors, , of such that . Thus if factors as and for some , we have that and is odd, then 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

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

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 , then by the mean value theorem there exist an such that . From the given it follows that , and being uniformly continuous trivially follows.

2:
part 1: Since is continuous at , for every there exist a such that when . Now choose an and its corresponding , then
. Thus is differentiable at and .

Part two follows with ease.

6:
Let , so is also differentiable on , and . Thus there exist a such that and when and . Since is compact, we know that 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 such that .