Back From a Hectic "Vacation"

Wow it has been a while since I have updated this blog. Quite a bit has gone on in my life since then, but I won't go into those things on this blog (that's what the other blog is for quite frankly). As far as school goes I am discovering that learning measure theory is almost as confusing as learning basic topology was the first time through. Luckily the professor makes comparisons to continuous functions, and other topological things that we are familiar with. So it could be worse I suppose. I tried reading the chapter in Rudin and needless to say I was left wondering, "what did he just say, and how am I suppose to show that?" Intermediate differential equations is pretty simple, the only bad thing is that some of the problems are quite computationally involved and they bore me to be honest. At times I wish the course was more proof based but I know that in order to do so you would need high level analysis (real or complex I'm not sure) and most of the people in that class (myself included most likely) aren't up to that.

The computer science classes are quite the bore. Though Intro. to computer organization has its interesting moments.

Well that's enough about classes. This Sunday there is going to be a programming contest. Hopefully everything will run smoothly *fingers crossed*.

Also I'm a lot more active on SPOJ now that I was before. I should start looking at more problems that just those I find interesting if I really want to increase my knowledge (or at least that's what I believe). The last problem I solved that required some thinking was a little DP problem. Building the solution wasn't all that bad, what made it a little challenging was making sure you caught all the cases.

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.

Best of 2008

Well yes I know this is a little late but I don't care. I'm going to list the top 10 artist, albums, and songs I listened to in 2008 according to Last.fm Note that when I get to tracks I will only list each artist once. Thus if they actually appear more than once I will only list their top ranking track (just to add some variety) I will however say how many tracks they had in the top 10 and if they actually were in the "official" top 10.

Artist:
1- Lil' Wayne (1444 plays)
2- Linkin Park (902 plays)
3- Yngwie Malmsteen (838 plays)
4- Maroon 5 (817 plays)
5- Alter Bridge (768 plays)
6- AFI (700 plays)
7- Stratovarious (687 plays)
8- Nada Surf (681 plays)
9- Kanye West (680 plays)
10- Muse (471 plays)

Songs:
1- Far Beyond the Sun(95 plays) [Yngwie Malmsteen] (also in real top 10: Black Star)
2- A Milli(91 plays) [Lil' Wayne] (also in real top 10: La La, Got Money, Phone Home, 3Peat, Lollipop, You Ain't Got Nuthin')
3- See These Bones(84 plays) [Nada Surf]
4- Blackbird(73 plays) [Alter Bridge] (actually at position 11)
5- Put On(70 plays) [Young Jezzy]
6- Prayer of the Refugee(62 plays) [Rise Against]
7- Papercut(61 plays) [Linkin Park]
8- Prelude 12/21(60 plays) [AFI]
9- A Beautiful Lie(58 plays) [30 Seconds to Mars]
10- Shiver(55 plays) [Maroon 5]

Albums:
1- The Carter 3 (804 plays) [Lil' Wayne] (was there really any doubt?)
2- Lucky (655 plays) [Nada Surf]
3- Songs About Jane (453 plays) [Maroon 5]
4- Hybrid Theory (401 plays) [Linkin Park]
5(t)- Absolution (364 plays) [Muse]
5(t)- Three Cheers for Sweet Revenge (346 plays) [My Chemical Romance]
7- Late Registration (350) [Kanye West]
8- Concerto Suite for Electric Guitar and Orchestra in E flat (319 plays) [Yngwie Malmsteen]
9- Rising Force (314 plays) [Yngwie Malmsteen]
10- Like Vines (303 plays) [The Hush Sound]

*IMPORTANT: The numbers displayed might not (and most likely are not) be correct. This is due to the fact that I often have music playing and for some reason or another Last.fm is not keeping track of this. This is not Last.fm's fault, but mine since I either choose not to log in or am on a computer that doesn't have (or doesn't support) the software necessary to keep track of played music.

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);
}