Saturday, August 15, 2009

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.

Monday, August 10, 2009

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.

Friday, August 07, 2009


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