Best of 2009

Well it is that time once again. Just like last year, I am going to provide you with a overview of what I have been listening to. All of the information will be coming from Last.fm: even though this isn't 100% accurate in the number of plays it does seem to provide the correct ordering in each of the list to follow. Similar to last year I will provide the names and play counts for the top artist, albums, and tracks (songs). However, this year I will provide the top 15 instead of the top 10.

Before I being I would like to say that this year I recently switched over from having Windows as my primary OS and am now using Ubuntu. Thus it was a while (probably a week or two) before I noticed that I could use Amarok to update my Last.fm listening trends. In addition I have used Grooveshark quite a bit and this fact isn't portrayed in the data below.

One last thing, in the traks section, each artist will only appear once. However, if they have multiple songs that are in the top 15 I will let you know. As a result this will cause me to list tracks that are not in the actual top 15. Don't worry, I will indicate their actual position.

Artist:

1: Portugal. The Man [664 plays]
2: Lil' Wayne [540 plays]
3: Nine Black Alps [409 plays]
4: Kanye West [395 plays]
5: The Hush Sound [360 plays]
6: Fabolous [357 plays]
7: Lupe Fiasco [341 plays]
8: T.I. [258 plays]
9: Muse [255 plays]
10: Eminem [251 plays]
11(t): Jay-Z [247 plays]
11(t): Rise Against [247 plays]
13: Ludacris [240 plays]
14: This Providence [232 plays]
15: Nada Surf [229 plays]


Albums:

1: Waiter-"You Vultures!" by Portugal. The Man [398 plays]
2: Everything Is by Nine Black Alps [244 plays]
3(t): Goodbye Blues by The Hush Sound [243 plays]
3(t): The Sufferer and the Witness by Rise Against [243 plays]
5: This Providence by This Providence [232 plays]
6: Loso's Way by Fabolous [230 plays]
7: Swan Songs by Hollywood Undead [208 plays]
8: The Cool by Lupe Fiasco [189 plays]
9: Love/Hate by Nine Black Alps [165 plays]
10: The Satanic Satanist by Portugal. The Man [155 plays]
11: Flying Colours by Bliss N' Eso [146 plays]
12: The Carter III by Lil' Wayne [144 plays]
13: Paper Trail by T.I. [142 plays]
14: Used and Abused by Danger Radio [137 plays]
15: Absolution by Muse [134 plays]

Tracks (songs):

1: Headlights by Nine Black Alps [50 plays] (also in real top 15: Ironside)
2: How the Leopard Got Its Spots by Portugal. The Man [44 plays] (also in real top 15: Gold Fronts, AKA M80 the Wolf, Stables and Chairs, House Warming Party, Kill Me. The King, Waiter, Marching With 6)
3: The Good Left Undone by Rise Against [38 plays] (also in real top 15: Roadside)
4: Always Strapped by Birdman ft. Lil' Wayne [34 plays]
5: A Wolf in Sheep's Clothing by This Providence [31 plays]
6: Plenty Money by Plies [30 plays]
7(t): Imma Do It by Fabolous ft. Kobe [28 plays]
7(t): The Diary by Hollywood Undeaad [28 plays]
9: Uptown by Drake ft. Bun B. & Lil' Wayne [27 plays] (actual position: 18)
10(t): Wasted by Gucci Mane [26 plays] (actual position: 22)
10(t): As You Cry by The Hush Sound [26 plays] (actual position: 22)
10(t): In Our Bedroom After the War by Stars [26 plays] (actual position: 22)
13: All of the Above by Maine ft. T-Pain [24 plays] (actual position: 30)
14: Imma Star (Everywhere we Are) by Jeremih [21 plays] (actual position: 40)
14(t): See These Bones by Nada Surf [21 plays] (actual position: 40)

Needless to say, but Portugal. The Man did this year what Lil' Wayne did in 2008...pwnd.

Another Fall Semester Gone

So keeping to tradition I'll say a little bit about each of my classes this semester and then at the end mention what I hope from the next one.

Data Structures and Algorithms: (A-)
Quite possibly the worst presentation of the topic I have ever seen. Basically the professor read from PowerPoint slides and had the TAs do all of the work. The TAs; wrote and graded the homework, wrote and graded the test and also had to respond to any questions the students had (even if they were intended for the professor). Luckily I was part of the programming team so I already knew all of the material that would be covered in this class.
The homework assignments weren't difficult at all but rather annoying. Especially when they gave you defective code to use. I would have preferred if we have been told to solve a particular problem, and that a certain data structure/algorithm was necessary. Instead they gave us a template to modify, and you didn't even have to know how to implement a Breath First Search for instance. All you had to know how to do was make a method call to the super class which you were extending. It is quite disappointing.

Topology 1: (A)
Well it doesn't help that about 3 weeks into the course we got a new professor (the original instructor had a stroke). The new professor expected that we knew more than was previously covered and also in much more detail. Needless to say, much of the semester was spent playing catch up. Normally I am a fan of the Moore method (students present all the work/answer questions) but I don't feel that it is appropriate for an introductory course. Especially one quite this abstract. In the end I am ashamed to say that the only thing I took away from this course were the portions that had direct applications to analysis.

Analysis: (A)
Not much to say, we started with a quick (1 day) review of basic things such as the monotone and dominated convergence theorems. After this it was some pretty cool stuff about signed measures. Which lead to the Lebesgue Differentiation Theorem and the Lebesgue-Radon-Nikodym Theorem. At the end of the semester we started with some introductory Functional Analysis (kind of like infinite dimensional Linear Algebra) and talking about Banach spaces.

Set Theory: (A)
The class wasn't that difficult. However, unlike most other easy classes I did like the way this was set up. This is not to say that it didn't have its flaws. This was another class that was taught with the Moore method. The professor would post the problem sets on his websites and then the students chose which problems they wanted to present to the class. The problems, at least the ones that didn't deal with the axiom of choice, weren't that difficult. Mainly it was a class to get students used to providing rigorous proofs to generally accepted facts. I will say however, that some of the results from this class I was able to use right away in some of my other classes, so that was nice. My main problem with the class was the test. All the questions came from the problem sets, so you really only needed to memorize the presented proofs and not actually understand the reasoning behind it. I would much rather have preferred the questions to make us apply something we had seen before, but oh well.

Overall I would say that this was a very successful semester. I managed to get my grades, manage work, do some reading for my honors thesis (which I need to read a lot more for), apply to graduate schools, and see friends every now and then. I'm actually looking forward to next semester, even though it will be my last.
At the moment I am currently signed up for 6 classes. However, I will only be taking 4 (2 will be dropped during drop add), the only problem is that there are 5 that I would like to take and am not sure which to drop. The choices are Theory of Measure and Integration 2, Operating Systems, Theory of Probability and Stochastic Processes 2, Partial Differential Equations, and Moder C++. The problem is that I can't decide between PDE and C++, which I would rather take. I can see both being useful, but one is going to be more work (C++) but it will be more enjoyable.

My Final Putnam Exam...2009 Edition

Well a few weeks ago I took my last Putnam exam. And I can say with a smile on my face that not only did I perform just as well as last year, but I have even exceeded the expectations I held when first entering UF. Initially I expected that I would only be able to answer two questions on the whole exam by the time I graduated. However, this year I answered (though probably not in enough detail for full credit) 4 question. The amazing thing is that even of the questions that I didn't answer I was headed in the right direction for most of them. For instance, one question asked you to find all possible values for some variable given some conditions. Finding the upper bound was rather trivial, but the lower bound wasn't quite as obvious. During the contest I found the correct lower bound, but didn't realize that I had arrived at it by evaluating a Riemann sum. Oh well you win some you lose some.

I'll post the problems and as much of a solution for each problem (if possible) on my other blog. I would have done it here but sadly I don't have LaTex enabled, so it would not only look ugly but also be a pain for me to write (as well as you to read).

One last thing, on the off chance that I haven't mentioned it earlier, I am applying to graduate schools. At the moment the list consist of Columbia, Carnegie Mellon, Cornell, Duke, NYU, and Wisconsin-Madison. All would be great places to attend, so fingers crossed.

Code Reuse

So here is a pretty useful trick/hack.
Say you need to create a max-heap. However, the code that you are forced to use will only create a min-heap. What do you do?
Well one solution is to just negate all the input entries, and then create a min-heap. Then the most negative (or most positive depending on how you view things) will be at the top.

I used this trick on my last Data Structures homework assignment. The code that we were allowed to use would create a tree with the smallest element as the root. But we needed to find the largest element. Now I could have easily written my own code, but why should I when code has already been provided? So all I had to do was negate the input and then copy the given code (though I did have to change a few inequalities around). Overall it was a great feeling, like I was "beating the system".
I prefer to look at this as being creative and not as being lazy.

Sadly, I can't take all the credit for this method. I had seen it before while reading a TopCoder tutorial on the C++ STL. They were talking about how to implement Dijkstra's algorithm with a priority queue. In C++ the priority queue container will always put the largest element at the top by default (though you can easily change this).

Being In Control

So whenever I ask someone why they chose to drive a manual transmission instead of an automatic, the response usually sounds something like this. "Because I like the feel of being in control. It's like you, and not the car, are doing the actual driving." Now the funny thing is that this is also the reply I get from some people when asked why they prefer Windows over Linux. Well, they don't say driving, but rather talk about being in control of the computer. Guess that being in control means accepting that there are things you can't control.

Super Freak

I was talking to Ashley yesterday. The conversation was going pretty well. She was talking about how she is enjoying her time in Chicago before going back to MIT. Then somehow we got to talking about programming languages and physics. Personally, I'm pretty surprised that she didn't complain about having to learn to program. Back in high school she would avoid anything that involved using a computer, that wasn't looking stuff up on Google or Wikipedia. But I suppose you can only avoid it for so long while being at MIT.

Well after talking to her, for some reason I started to really freak out about the whole graduate school application process. I still have to write a draft of my personal statement, and take the Math GRE subject test. I have gotten all As in my major classes, participated in a summer research program (paper under consideration for publication), and also plan to do a senior thesis. All this on top of what I am sure will be strong recommendations. Yet for some reason I am still worried. I suppose that I am worried that this won't be good enough to get into the school(s) that I really want to attend.

Correction

Well I fixed my algorithm and managed to solve the problem (see previous post). Here is a general overview.

1. Create array of cumulative sums
2. Create Segment tree
3. Answer queries using segment tree

Each node of the segment tree contained about the location of the max and min elements of the cumulative sum array, that was spanned by the interval. For instance, the node that pertained to the interval [2,4] would contain information about the max and min elements of Sum[2...4], where Sum[] is the cumulative sum array. Also other information might need to be stored in each node, but I'll leave that up to you to discover. Don't want to spoil all the fun now do I?

Now I'm moving onto GSS3, which is more or less the same problem but with the ability to update sequence elements in addition to making queries. At the moment I plan to use the same code but modify certain parts so they they use binary indexed trees.

Found this to be a pretty interesting problem. Think I might try to implement a version for working with 2D arrays. Really it's not too hard to extend to more dimensions but the code just gets longer though the thought process stays the same. To me this is probably the major advantage of using segment trees over sparse arrays. But I must admit that I am not all that comfortable with the sparse array method, so it might extend just as easily (though I don't see it).

Range Minimums and Maximums

WARNING!!! The following algorithm is incorrect! For a counter example consider the set { 9 , -10 , -10 , 5 , 5 }. It will say that the answer to Q(1 , 5) is 9, but it is fact 10. However, though it is incorrect it does provide you with a good place to start.


At first I was going to talk about the SPOJ problem ORDERS in this post, but decided to put that off. Mainly because I found something else more interesting in addition to the fact that I still haven't completely finished ORDERS.


First off, here is a link to a TopCoder tutorial on RMQ (range minimum query). This post is by no meant a substitute for the tutorial. I would recommend reading the tutorial after this post (only because you are already here) to see more on the topic. Now the problem I will be discussing is GSS1. I would like to point out at this time that the solution I am going to give WILL NOT GET ACCEPTED!! It is far too slow, but should give you a good idea on where to start or proceed.

So suppose we were naieve and decided to do all our preprocessing at the beginning and then ansewr each query in O(1). Obvioulsy the first data structe we think of is an array. So we will let Ans[i][j] be the answer to the query Q(i,j).
Now how does one go about creating this array? Well obviouly the answer to Q(i,i) is the input[i], where input[] is the given array, so

Ans[i][i] = input[i].

Now suppose that we know the value of A[i][j] how would we find Ans[i][j+1]? Well, there are three possibilities.

1. Ans[i][j+1] = Ans[i][j]
2. Ans[i][j+1] = input[j+1]
3. Ans[i][j+1] = Ans[i][j] + Sum(input, k+1, j+1)
   

In the above k is the index of the last element that is used to make A[i][j] (more on this in the example later on). So using this we can build our array Ans[][] in O(n^2), which actually isn't that bad for small cases.

EXAMPLE:
input = { 1 , 2 , -2 , 4 , -1 , 1 }

So Ans[][] will be a 6x6 array.

Ans[1][1] = 1 clearly. Now for Ans[1][2], we can either use Ans[1][1], only use input[2] or add to Ans[1][1]. So in this case we will want to add to Ans[1][1], thus giving Ans[1][2] = 3. Note that k was 1 so Sum(input, k+1, j+1) = 2

Now for Ans[1][3] we have the following cases;

1. Ans[1][3] = Ans[1][2] = 3
2. Ans[1][3] = input[3] = -2
3. Ans[1][3] = Ans[1][2] + Sum(input, 3, 3) = 3 - 2 = 1

So trivially we want Ans[1][3] = Ans[1][2] = 3.

Just for good measure consider Ans[1][4];

1. Ans[1][4] = Ans[1][3] = 3
2. Ans[1][4] = input[4] = 4
3. Ans[1][4] = Ans[1][3] + Sum(input, 3, 4) = 3 -2 + 4 = 5

Thus it is best to take all the elements in this case giving Ans[1][4] = 5. And you continue this process.

Well here is the C++ code that you have been waiting for (unless you like some other language). Once again I would like to say that this method WILL NOT WORK!! for the case on SPOJ. (note I assume that the first element of the array input[] is 0, just to make things easier to code)

Ans[n+1][n+1];
memset(Ans,0,sizeof(Ans));//not needed but I just like to know what's in my arrays

for( int i = 1; i!=(n+1); ++i)
Ans[i][i]=input[i];

for( int i = 1; i!=(n+1); ++i)
for( int j = i+1; j!=(n+1); ++j)
   Ans[i][j]=my_max(Ans[i][j-1],input[j],Ans[i][j]+Sum(input,k+1,j));

I'll leave the implementation of my_max( ) and Sum( ) up to you, along with a way to keep track of k. Note that you will need to be "creative" when making Sum( ) so that the above stays O( n^2) and doesn't become O( n^3).

In the link to the tutorial at the beginning of this post he describes other methods to solve this problem. Some have much better performance. The one I plan on using has preprocessing time O( n) and answers queries in O( log n). Some of the other methods that he claims are easy to code (though I would disagree) have preprocessing time O( n) and answers queries in O( sqrt(n)) and preprocessing time O( n log n) and answers queries in O(1).

DAGs and DP: aka one thing I'm good at and another that I'm not

So I haven't solved an SPOJ problem in a while. Mainly because I've been doing other things. Well today the drought is over. I managed to solve RENT.

I'll just describe how I went about solving this one. I should mention that the idea was not totally mine. Anyway, I will assume that you have either read the problem or are familiar with it's statement.

Well first off there is the obvious O(2^n) algorithm but obviously this is out of the question considering that the program has 3s to run and n can be as large as 10000. So the next thing to try is looking for a DP solution. This is where DAGs (Directed Acyclic Graphs) come into play, though it might not be obvious.

You construct the graph in the following way. There is an edge between vertex U and vertex V if there is an even starting at time U and ending at time V. Also the weight of the edge is equal to the amount of money you will get for selecting that activity. At this point you execute the DP portion by using a variation of a DFS (So as to not spoil the problem completely I'll let you figure that part out yourself). Just remember that you are looking to make the MOST money in the alloted time.

This method is O(E+V) once you have created your graph. I think the way I created my graph is close to O(E). With a few optimizations the above will work (at least in C++), my solution finished in 1.71s so if you are using Java or another language that isn't particularly "fast" some additional tweaks (or a completely different algorithm) might be necessary. I would like to mention that there are other methods to solve this problem but I didn't find them to be quite is intuitive or obvious. Plus I like working with graphs, and thought that transforming this into a graph problem was rather interesting.

EDIT: Now I also want to edit my algorithm so that it will also tell you which events to select. I don't see this being all that difficult, so I'll probably think about it later this week, and hopefully have an solution (an efficient one that is) by Sunday.

New News

Not sure if I mentioned on here before, but I have a job for the summer. Sure I'm glad to have a job but I really would rather be doing something that is more math or computer related. And more computer related than using MSOffice. This has further motivated me to become quant. Also I'm preparing for the GRE, ideally I would like to take it before I start school again. However, I am not sure I'll be able to learn all the vocab (random words and roots) by that time; as well as do lots of practice problems and test. Then I get to take the math subject test in October, and again in November if needed.

In some of the free time I have I've managed to start another blog, start leaning regular expressions, learn Bash programming, read a few chapters from an algorithms book, and learn a little more about C++. So not too bad if I don't say so myself, however none of these topics has really been explored to much depth. Notice the lack of math on that list, it's pretty depressing. I'm considering buying a book on Measure Theory (either with relation to probability or integration) and another on Stochastic Processes.

Well that's all for now. Just though I'd drop by and give a brief update since I've been somewhat busy recently.

Facebook Quizzes

For some reason these things are just so addicting, even though the results can be total BS at times.

Quiz : What is Your Secret Innermost Desire for Your Life...?
Result: Sexual Stimulation
Your subconscious mind is driven most by sexuality. What this means is that when your unconscious mind sees an opportunity to remind you of your sexual desires, it takes full advantage of it. Because of this, things that have very little sexual content or that seem sexually neutral to others, may register as sexually charged to you, at least on an unconscious level. Your unconscious mind recognizes the value of sexuality. The reason it may do so, is because of a deep-rooted fear of the opposite living a life that is numb to sexual desire or is turned cold by it. You unconscious mind may be trying to avoid this sexual dullness, and so it reacts by swinging to the opposite extreme, strong sexual desire. By sending you these sexual messages on a regular basis, your unconscious makes sure you don't forget about sex. Demure who can resist your seductive charm? You have mastered the art of flirting so well that all you have to do is sit there and look pretty and they come to you.

Quiz: How Dateable are You?
Result: Completely Dateable
You are the perfect gentleman/lady and you know everything anybody needs to know about dating and flirting

Quiz: What are you Born to Do?
Result: Best at Everything
you are the social person who make usefull contacts. you introduce important people to influencial people and always reap some sort of reward as a result...but you dont enjoy the spotlight as much. you prefer to stay in the back as there is more room to strech and you like the feeling that you are the one with the power and most of the time that is true... you will do well in almost anyfield you know how to flater without being to obivous and you can make just about anyone like you

Quiz: Which Transformer are You?
Result: Bumblebee
Bumblebee is a cautious, yet brave warrior of the Autobots. He is the symbol of friendship with mankind because of his bond with his human; Sam Witwicky. His feelings are sometimes hurt very quickly if put down or harassed. He is loyal to Optimus Prime and Sam. His original vehicle form was a 1976 Chevy Camero, but upgrades it to a 2009 version. Motto: "The least likely can be the most dangerous."

I'm Not Into Dating

Below is and edited version of a conversation I found.

(05:48:36 PM) Person1: wow. yeah, I've been there. I dated a guy last year who wasn't "big on relationships"....which I discovered was code which really meant "you're not worth me making a big deal out of what we have". Once I realized that, I wasn't sad to see him go
(05:49:11 PM) Person2: oh wow never though of it that way
(05:49:16 PM) Person1: if someone doesn't think you're worth dating officially, then they're not worth you wasting your time over them.
(05:50:38 PM) Person1: yeah. Even farther back in time, a few years ago, I was one of those people. It wasn't that I didn't want a relationship, because nobody is going to turn down a relationship with the person that they think is right for them. The fact is that I didn't like the guy enough to commit to him.
(05:51:52 PM) Person1: [EDITED], but learn from my mistakes: get rid of this girl and don't waste more time on her, time that you could spend finding a girl who treats you well
(05:52:54 PM) Person2: wow that was really helpful. more so than the usual "move on/get over it" from others. thanks
(05:53:10 PM) Person1: you're welcome, I'm glad I could help.

Just Friends...Forever

This was good for a small laugh. Not sure where it came from since a friend sent me the article and not a link. Anyway enjoy, oh and I don't feel this way about anyone so don't think that it's personal in anyway. Though my past would beg to differ.

"I really like you. I do. You're so nice, and sweet, and you listen to all my problems and respond with the appropriate compliments. But, well, I don't really see a relationship in our future. It would be terrible if we let sex destroy this great friendship we have where I get everything I want and you get nothing you want. Don't you think?

I knew you would understand. You always do.

We're so perfect as friends, you know? I can tell you anything, and you know you can always come to me anytime you need to hear me bitch about work or how ugly I feel. You wouldn't want to ruin a friendship like that just so you could be my boyfriend, and have me look at you with desire and longing in my eyes, if only once—would you? Of course not. Well, if we started dating, it would only complicate this wonderful setup I've got going here.

It's just…you're like my best friend, and I would hate for something you desperately want to change that. I mean, sure, we could go on some dates, maybe mess around a little and finally validate the six years you've spent languishing in this platonic nightmare, but then what? How could we ever go back to the way we were, where I take advantage of your clear attraction to me so I can have someone at my beck and call? That part of our friendship means so much to me.

No. We are just destined to be really, really good friends who only hang out when I don't have a boyfriend, but still need male attention to boost my fragile and all-consuming ego.

Anything can happen once you bring romance in. Think about how awful my last relationship was at the end, remember? The guy I'd call you crying about at 3 a.m. because he wouldn't answer my texts? The guy I met at the birthday party you threw me? I had insanely passionate sex with him for four months and now we don't even talk anymore. God, I would die if something like that happened to us.

Plus, ick, can you even imagine getting naked in front of each other? I've known you so long, you're more like a brother that I've drunkenly made out with twice and never mentioned again. It'd be way too weird. And if we did, then whenever you'd come shopping with me, or go to one of my performances or charity events, or take me for ice cream when I've had a bad day at work, you'd be looking at me like, "I've seen her breasts." God, I can't think of anything more awkward that that.

Oh, before I forget, my mom says hi.

Anyway, you would totally hate me as your girlfriend. I'd be all needy and dramatic and slowly growing to love you. If I was your girlfriend, I would never be able to tell you all about the other asshole guys I date and pretend I don't see how much it crushes you. Let's never lose that. That's what makes us us.

Don't worry. You're so funny and smart and amazing, any girl but me would be lucky to date you. You'll find someone, I know it. And when you do, I'll be right by your side to suddenly become all flirty and affectionate with you in front of her, until she grows jealous and won't believe it when you say we're just friends. But when she dumps you, that's just what we'll be.

Best friends. Friends forever."

1984

Currently reading 1984 and am about half way through so far. Can't say that it has lived up to the hype as of yet but who knows. Well I think I have found the best line in the whole book, yes I am willing to bet that it is better than anything I will read in the second half.

"If you loved someone, you loved him, and when you had nothing else to give, you still gave him love."

Personally I feel that it would be better if 'him' were changed to 'them' but that's just a minor detail.

How to Separate Interface From Implementation

Well I've finally managed to see how to separate implementation from interface. The basic idea is pretty simple and that only took about a minuet to understand. This was mainly due the fact that it was easy to find lots of examples online. Really the only problem was that they didn't tell you HOW to use this to make a functional program.

So I'll just put together a quick "how-to", where I'll walk through a simple example.

We will create a class called Base, below is the base.h file.

#ifndef BASE_H
#define BASE_H
class Base
{
   int value;
   public:
      void set_value(int);
      int get_value();
};
#endif

So that's the interface for our class, not to create the implementation. This will be in a file called base.cpp

#include "base.h"
void Base::set_value(int x)
{
   this->value=x;
}
int Base::get_value()
{
   return this->value;
}

Finally here is the main program. Since we don't want to be original we shall just call it main.cpp and it looks something like this.

#include< iostream >
#include "base.h"
using namespace std;
int main()
{
   Base X;
   X.set_value(120);
   cout<< X.get_value()<< endl;
}

Now to we create an object file from base.cpp by entering g++ -c base.cpp into the terminal. Then to link this with main.cpp we type g++ main.cpp base.o into the terminal. If all has worked you should see the number 120 printed to the screen when you run your program. (with ./a.out in cause you were wondering)

Progress Update II

Well I ended up starting over. My original plans were a little too complicated for a first attempt at a game. However, the way things are set up it is moderately easy to make any desired updates. One "mistake", well more of a not sticking to convention, is that I did not separate the interface and implementation of things in my header files. Right now I'm reading more on why this should be done, but haven't gotten far enough to be able to see much real benefit.

Here are all the header files I use as well as a brief description of what they do.

Hero.h
Used to make the hero class, also known as the character you control.

Enemy.h
Basic information that all enemies in the game share; such as health, a name, and strength.

Save.h and Load.h
Used to save and load game data.

Fight.h
Control all the aspects of combat. This would include things like if an attack hits, how much damage attacks do, and knowing when a fight is over.

Menu.h
All the menus that appear in the game are in this file. It contains a number of functions that return characters or strings, to let the game know what the user has decided to do.

Engine.h
Contains the Play_game( ) function that more or less controls the flow of the game.

Derrick Rose

Found this article to be quite though provoking. Don't think I'll say where I stand on the issue but he does raise a few good question.

My two favorite excerpts are below.

This isn’t to absolve the people involved, but the question shouldn’t just be did Derrick Rose cheat on his SAT?

It should be why the heck did he have to take it in the first place?

No one cared when Danica Patrick went pro as a race car driver at 16. No one tried to prevent Shawn Johnson from winning an Olympic gold at the same age or Miley Cyrus from making millions singing and acting with her dad even younger than that.

And no one ever required them to recognize analogies before doing so.

So why do we make Derrick Rose?

Progress Update I

So far everything is going pretty smoothly. This is due largely in part to having created a UML, and doing some documentation before I started coding. However, I feel that I will have to go back and change and/or add somethings. The biggest problem right now is memory management. I don't yet fully understand how the delete keyword works, so my classes at this point don't have deconstructors (yes I know wasted memory, but the game shouldn't be that big so I will worry about it later). This is the main reason that I considered writing the game in Java and not C++.


Creating and using my own header files is actually easier that I had first assumed. Every now and then I will make sure that they work by trying to use them in a small test program that I wrote. Most of the time if there is a problem with a file it is because of a stupid typo or forgetting to include another needed header file, so nothing too detrimental.

Even though everything works so far, and by that I mean compiles with no errors or warning, I still have no idea if they work as intended.

I'll post a quick overview of all the current and planned header files in the next update.

Y-Game

So I have come up with a personal summer project. I am going to recreate "Y-Game". Basically this was a text bases RPG that my friend created back in high school for the TI-83/84.
Right now it will still be text based, but that might change depending on how much time I end up having. Also it will be more elaborate since I will be writing the game in C++ (or Java, but not likely).
From this I am basically hoping to become more familiar with header files, linking files, and most of all writing and reading data from a file. I already know how to read and write to a file, I would like to do that so that it is possible to save your progress in the game and then come back at a later time and continue.
More than likely the next few post will be updates on how things are coming along.

Moving Through Trees

Well this week has been pretty successful so far. I've managed to solve 4 SPOJ problems I think, though one was just applying a "basic" geometry formula.

Of the remaining problems the first was about playing a game optimally. Usually I detest doing these kinds of problems, but once I noticed that there were solutions in Brainf**k I knew that there was something I was missing. Here is the link to the problem, as far as hints go all I will say is play the game by hand for the first few (under 30) numbers and you should notice a pattern.

The next two problems are pretty similar. Since I am going be describing how I actually solved them I will not be providing a link. They were both asking you to find the longest path within a given tree. The naive approach (and probably more difficult to program) approach would be to find the distance between very possible pair of vertices. This is going to result in an O(n^2) algorithm, and not to mention that it isn't immediately obvious how to find the distance between two given vertices. Naturally the next I idea was to use a depth first or breath first search, the issue now becomes knowing if you have found the longest path. Well here is the approach that I used; start with any vertex of the tree and then use DFS (depth first search) to find the vertex that is farthest from it, call this vertex X1. Now do another DFS starting with X1 and find the vertex X2 that it is furthers from. The distance between X1 and X2 will be the longest path in the tree (though I don't feel like proving rigerously or even using hand waving to explain why).

Here is a sample of the code I used to solve the case where all the paths had the same length. It isn't too difficult to modify for weighted trees.

pair< int,int > dfs(vector< int > >&G,int v)
{
   stack< int > S;
   S.push(v);
   vector< int > visit(G.size(),0);
   while(!S.empty())
   {
      int parent=S.top();
      S.pop();
      tr(G[parent],i)
      {
         if(visit[*i]==0)
         {
            S.push(*i);
            visit[*i]=visit[parent]+1;
         }
      }
    }
    vector< int >::iterator    i=max_element(visit.begin(),visit.end());
   return make_pair(i-visit.begin(),*i);
}

The first entry of the returned pair is the vertex farthest from the starting point, while the second entry is the distance. Thus you will run the DFS two times as previously mentioned. So the complexity of this method is O(n) which is much better than the other approach.
It should be noted that the following is at the beginning of the code

#define tr(a,i) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)

Summer Job

So I most likely will have to find a job this summer. I am pretty set on avoiding fast food and being a waiter. As of now the list of potential places of employment are as follows:

• Kohl's
• ACM
• Boston Market
• Jo-Ann's
• Sears

I don't really consider Boston Market to be quite as bad as normal fast food restaurants so that is why it is included on the list.

In addition to possibly working I will also be preparing for the GRE and hopefully start studying for the FM actuarial exam. Oh and I should also email my thesis advisor asking him if there are any papers he would like me to read over the summer.

Terminal

A little while ago I installed Ubuntu 8.10 onto my desktop, along with Windows XP. Truthfully speaking, the only reason I boot into Windows more often is because I have a program that lets me watch tv on my computer (which is nice seeing as how I don't currently have a real tv).

Anyway, after changing most of the Ubuntu settings so that things are the way I like them; I realized that I still hadn't "fixed" the terminal size. Well at first I did a little Google search to see what the necessary command(s) I would have to run were. However, most of what I found required me to make a launcher, which I didn't want to do. Though I have a feeling that this is the way I solved this issue when I installed Ubuntu onto a portable HD for my laptop.

Finally I found a much nicer way to change the default terminal size. Here it is;

1) Open up a terminal

2) Tyep the following:

sudo gedit /usr/share/vte/termcap/xterm

*in the above you could replace gedit with vim if you wanted, but I just like using gedit personally.

3) Find the following line:

:co#80:it#8:li#24

4) Change it to the following:

:co#A:it#8:li#B

Where A and B are the dimensions you desire. (Your teminal will have dimensions A x B)

Daydreamin

Yesterday I went to a Lupe Fiasco concert. Definitely not an experience that will be forgotten any time soon. My only complaint would have to be the excessive use of strobe lights, though after a while I did manage to get used to them.

There was one song in particular that he performed that stood out more than the others. Not because of the lyrics or the beat, but rather because of a past experience that involved the song. I won't go into what the experience was on this blog, but you will get a video of the song, along with the lyrics.




Lyrics:

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

[Lupe Fiasco]
As I spy from behind my giant robot's eyes
I keep him happy 'cause I might fall out if he cries
Scared of heights so I might pass out if he flies
Keep him on autopilot 'cause I can't drive
Room enough for one I tell my homies they can't ride
Unless they sittin on the shoulders but that's way too high
Let's try not to step on the children
The news cameras filmin
This walkin project buildin
Now there's hoes sellin hoes like right around the toes
And the crackheads beg at about the lower leg
There's crooked police that's stationed at the knees
And they do drive-bys like up and down the thighs
And there's a car chase goin on at the waist
Keep a vest on my chest
I'm sittin in my room as I'm lookin out the face
Somethin to write about
I still got some damage from fightin the whitehouse, just a

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

[Lupe Fiasco]
Now come on everybody, let's make cocaine cool
We need a few more half naked women up in the pool
And hold this MAC-10 that's all covered in jewels
And can you please put your titties closer to the 22s?
And where's the champagne? We need champagne
Now look as hard as you can with this blunt in your hand
And now hold up your chain slow motion through the flames
Now cue the smoke machines and the simulated rain
But not too loud 'cause the baby's sleepin
I wonder if it knows what the world is keepin
Up both sleeves while he lay there dreamin
Me and my robot tip-toe 'round creepin
I had to turn my back on what got you paid
I couldn't see half the hood on me like Abu Ghraib
But I'd like to thank the streets that drove me crazy
And all the televisions out there that raised me, I was

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

Daydream
I fell asleep beneath the flowers
For a couple of hours
On a beautiful day
Daydream
I dream of you amid the flowers
For a couple of hours
Such a beautiful day

Drains

This post just made my day. The next time I have a blocked drain I am totally going to try this.

http://hpuew.blogspot.com/2009/04/bi-carb-soda.html

Christina Aguilera

I was on Yahoo reading an article about someone's 10 Finest DIVAS. Here is what they had to say about Christina Aguilera.

She almost made my pop list, since I enjoy her as a radio pop star, but you know the inside line on Ms. Aguilera is how unlike so many of her contemporaries, she can actually sing! Imagine how exciting that must be for the studio engineers and record producers who work with her. It's like hiring an electrician and discovering after he leaves that your house now has actual electricity and the light switches all work! Such competence in this day and age? What next? A CD player that doesn't break after only four years? Crazy!

And I'm not afraid to admit that I am a fan. Honestly talent is sexy and you and I both know that she is a damn good singer.

BigInteger

Well I now have a working C++ BigInteger class. The only problem is that so far it is only able to do addition and multiplication. I am fine with the speed of the additions since you can't do any better. The multiplication is where the main problems are located. Sure the method works but it is way too slow. I just need to figure out how to convert a string that represents a number in base 10 into a string that represents the same number in binary. Once I am able to do this I know how to perform faster multiplication algorithms. A similar problem will be converting the answer (which will be in binary) back to decimal.

Regardless I would still like to add a method for modular arithmetic and possibly division, these would just be nice to have but not necessary. Also I should probably work on getting it to handle negative numbers as well.

Printer Simulation

PQUEUE

The question above was my "SPOJ victory of the day." On my first attempt at the problem I was thinking too hard about all possible cases. Needless to say this resulted in WA. However, today I looked at the problem and noticed that the bounds were extremely low. So I thought about just simulating the process, and realized after a little thinking that this would be O(n^2) in the worst case, which was not a problem considering the fact that the upper bound on n was about 100. After getting my solution accepted I noticed that there were relatively few TLEs, this should have alerted me sooner that a "trivial solution" was possible

I think the problem would be more interesting if they gave you the times that each job was added to the printer queue. The problem would still be solvable by simulation but it would require a little more "creativity" in doing so. However, the way I coded my solution, it wouldn't be too hard to adapt it for this variation. Basically I used a double-ended queue to keep track of the order of each job request. The reason for using this structure is that it has the ability to quickly add and element to the back and delete and element from the front. In addition I used a heap to keep track of which job currently had the highest priority.

Nice Quote

I was talking to my analysis professor about which classes I should take next semester. We were both clear that I was taking the 6000 level analysis, but then for my other class there was a choice between Functions of Complex Variables and Elements of Topology. His opinion on the subject can be summed up in the following quote,

"If we (the math department) were to only offer one course this (complex analysis) should be it."

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.

My 2008 Putnam Results

As expected I managed to score a 20/120, in addition to this I finished 616/3627, so top 17%. To be honest I was hoping that I would have been in the top 15% but I'm not going to complain.

Oh in addition to this our school finished 12th, which is our best finish ever from what I've been told. Sadly I wasn't on the team (I had class at the time of the T.S.T), but hopefully I will be next year and we will finish just as high if not better.

Hello World

#include <iostream>
int main()
{
   cout<<"Hello world.\n";
   return 0;
} 

You have no idea how long it took to get that to look nice. The part that caused the most problems was getting the '<' and '>'signs to display properly, thanks HTML. After that it was pretty straight forward, you just put the code in between either

<blockquote> ... </blockquote>
or
<code><pre> ... </pre></code>.

In case you were wondering, in order to display '<' you typed &_l_t_; (without the underscores). For some reason you can make '>' with the one on the keyboard, but you can also do &_g_t_; (once again without the underscores).

Units Actually do Matter

Just another reason no one likes biased news; be it liberal, conservative, 'Apple', or whatever.





You might remember this from a while back, if not then enjoy it now.

[Inert Your Title Here]

Well it is almost the end of another Spring Break. I had originally planned to copy the Measure Theory portion of my Analysis notes into my new notebook, study look over some Differential Equations, and get in some SPOJ time. Needless to say things didn't go as planned. Pretty much all my free time was spent working on SPOJ.

Most of the problems were ones that I had previously started but for some reason was unable to generate an acceptable solution. The only totally "new" problems were JAVAC, SUMITR, and TRICENTR. None of these were all that difficult, but the source limit on SUMITR did cause some issues. I ended up writing the solution for that in C rather than C++.

Here are the other solved problems and my remarks.

ADOMINO: Exactly the same as AGGRCOW but there are some cases that AGGRCOW didn't have so some modifications needed to be added in order to work around these. Not sure if this should even count as a "new" problem really, but why not, it did take me more than 1 submission.

SBANK: I just needed to use a faster way to read the input. To think that I had this problem unsolved for about half a year only because of this.

SHPATH: I had to implement Dijkstra's with a priority queue (a heap like data structure) rather than a set. Personally I prefer to use the set solution but I can see why the priority queue method is faster.

STABLEMP: My idea of using a greedy algorithm was correct. The problem was in the way I was storing the necessary information. Just imagine my embarrassment when I discovered this small but important mistake.

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