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

Another Semester Down

Finally this semester is over. Not that I didn't enjoy it but the classes didn't provide me with enough of a challenge. I don't see too much changing next semester but you never know. I don't see any reason for not making all As since I pretty much destroyed every test and project. Well here's the expected break down of each class.

CIS 3020: Quite uninteresting. All the object oriented stuff we learned in class I already knew, and that was because I spent about an hour reading the OO portion of a C++ tutorial. The lab sessions were quite useful since you actually learned concept, thank god for graduate students. The two things I got out of this were learning some Java and finally switching over to Linux (as far as my laptop, I still have to get around to putting it onto my desktop).

Fourier Analysis: Worst mistake ever. Easy class, but so uninteresting. I was expecting a theoretical approach to the topic, or at least an applied one where theorems were stated and then proofs sketched. However, what I got was "here is what a fourier series is, now here is what MATLAB can do". Needless to say I didn't really learn anything I would consider worthwhile.

Numerical Analysis: Seemed like a computational approach to linear algebra. Though the class did make us use MATLAB he would explain where the equations and algorithms came from before showing how to perform them in MATLAB. Overall could have been a better class but I guess I was expecting too much since I had already started reading a Numerical Analysis book a few years ago.

Modern Analysis: Good review of what I did all last year in Adv. Calc. The problems he assigned were pretty interesting and required some thought, but nothing to the point where you would be banging your head on a desk two hours before the assignment was due. He's a pretty cool guy and an amazing teacher. The phrases of the semester were "blindingly obvious" and "it's easy", so as you can imagine we had some fun with those. OH before I forget he has agreed to be my faculty adviser (or whatever it's called) for my honors thesis. So after the second semester of the course we will get together to discuss thesis topics; looking forward to it.

On a non academic side, today I found out that I was chosen to go through the selection process for an NSA internship. Hope everything goes well and I am chosen, this is honestly my dream internship.

Also if you have lots of time to waste here is a really good site, though I warn you there are a lot of graphs.
Procrastinate

Steven A. Smith on Burress

What more is there to be said.