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