So, I am now trying to while away time in this totally freaking awesome thanksgiving break when its just too hard to find vegetarian food (I don’t know why people are hell bent on making life difficult for vegetarians, aren’t plants easier to grow than animals?), or people in this dorm. Well, here is a life update — I have managed to get into the A slot (not the A+ though ). I applied to an REU and got rejected after which I decided to wait it out and apply for an REU in spring, it sure would be nice to take grad school admissions head on (considering I am still a lazy freshman, I should probably keep that enthusiasm for later).

I’ve managed to make life difficult for TAs by conveniently neglecting to read the homework description. This discrete math class I was in had an assignment on modular arithmetic and it contained the brilliant RSA…… I like this great dude submitted a program and the output to the TA who then told me that I had made life infinitely more difficult for him and that I should have used a pen and paper like everyone else (I hate pens / papers / pencils, I can’t understand what I write myself). Here is the worst RSA implementation in the world: http://shriphani.com/RSA/rsa.html.

Then I applied for an REU and got turned down thanks to the fact that it was just my first semester… anyway, I just hope I manage an A in CS etc…..

Got to get back to finishing a GUI programming assignment, ascend the PE ratings and finish watching 30 rock season two. It is just weird, it is snowing outside and I’ve got a fan running at full blast in my room thanks to our hyperactive heater.

While suffering from conjuctivitis, fever, a sore throat and what seems to be a case of swollen tonsils determined to make nutrition a pain for the next week or two, I decided to solve a problem on Project Euler. The question I picked was Problem 33: Find all fractions with the given unorthodox cancelling method (just click the fscking link for heaven’s sake!).

I thought this problem can be solved by beginning with a base fraction and adding a numbers in the tens place to both the numerator and the denominator, then adding a number in the units place to the numerator and the denominator, adding to the units place in the numerator and the tens in the denominator and the other way round.

The code needed (in Python2.6 - just love the Fractions module there):

BTW, it is funny how total nutjobs with no clue about probes, payloads, science or physics take up the job of reporting the Chandrayaan’s progress.

Peace…..

As I sit here sipping my 10th cup of coffee ( a clear indication that my coffee drinking habits border on “poisoning” ), I whip up the last remaining lines of code for a Problem on project euler. I can’t help but wonder that my blogging, project euler problem solving frequency has dipped way too low. I also can’t answer why. Maybe it is because life is not treating me too well. Let us now imagine what conjuctivitis + fever feel like on the eve of an exam….. considering that I am weird (everyone tells me I am eccentric and weird… so many people can’t be wrong), I decide to go sit through the exam just because I want to be done with it.

So here is a list of my characteristics:

1. Nocturnal: (Ever since school, I realized that I could get anything done in the night. Hence, I have made it a point to occupy the Lawson CS Building at night for reading / homework etc., it is really quiet and lets me make awesome progress in w/e I want to do). The downsides are that I sleep in the morning, something that doesn’t fly too well with my Tuesday and Thursday Math recitations and leads other people to just assume that I am weird

2. Caffeine: Needless to say, I consume a lot of this substance and believe that it is God’s gift to mankind.

3. Bashing Most Non-*nix based OSes: Lots of targets, doesn’t get you a great reputation.

4. Theory fanboyism - I really love TCS. That is not a view most budding computer scientists seem to share….

5. Low levels of personal hygiene (however, dental, hands and other such departments are taken good care of).

So, I am weird.

Anyway, wikipedia says that eccentric dudes are pretty intelligent (usually) and that is some consolation.

So, I’ve had the best week of my life and let me tell you folks, nothing’s better than sitting in front of one of the most awesome boxes in the world - the macbook pro. Yes, the alpha and the omega is here, I am now the proud owner of a macbook pro (not the new ones, this is the older version). So, here are the specs:

2.5 GHz

2 GB RAM (Vista was a PITA on 2 Gigs, OS X is such a beauty)

512 MB NVidia 8600M GeForce

Intel Core2Duo (obviously)

And so, here are a few select screenshots:

And of course:

And then comes:

By the way, that is how beautiful Komodo looks.

Then of course:

That is what iPhoto looks like. 

BTW, between a tough courseload which does not require me to use Python, I managed to squeeze some time for myself so I could automate a few modular arithmetic algorithms.

The first one I shall be dealing with is modular exponentiation. 

If we have a^k mod n, then we can express it as
(a mod n)^k mod n.

This allows us to express this in the form of code as:

Then of course comes finding the modular inverse using euclid’s algorithm:

That should return a tuple whose first element is the GCD. Well, I am going to have fun with the Macbook.

Since I was quite bored this week (thanks to an October break I spent entirely in my room) and a homework assignment that quite seriously sucked balls, I decided to read something about strings and read about Suffix trees and decided to whip up an algorithm that would create a neat suffix tree by walking over a string and failed incredibly to get it to split at the right positions. Which means that while the suffix tree for “mississippi” is:

       |(1:mississippi)|leaf
tree:|
      |     |       |(6:ssippi)|leaf
      |     |(3:ssi)|
      |     |       |(9:ppi)|leaf
      |(2:i)|
      |     |(9:ppi)|leaf
      |
      |     |      |(6:ssippi)|leaf
      |     |(4:si)|
      |     |      |(9:ppi)|leaf
      |(3:s)|
      |     |     |(6:ssippi)|leaf
      |     |(5:i)|
      |     |     |(9:ppi)|leaf
      |
      |     |(10:pi)|leaf
      |(9:p)|
      |     |(11:i)|leaf

all I can get is a single level tree and I have no motivation whatsoever to get it to work correctly considering that we are covering computational complexity theory and that kenneth rosen makes it so hard for mankind to put his book down. By the way, here is my partial (decent word for “wrong”) suffix tree generator:

And this is what I get for a bunch of strings:

shriphani@linux-s359:~/scripts/Strings> python suffix.py mississippi
{'i': ['ssissippi', 'ssippi', 'ppi', ''], 'p': ['pi', 'i'], 's': ['sissippi', 'issippi', 'sippi', 'ippi'], 'm': ['ississippi']}

shriphani@linux-s359:~/scripts/Strings> python suffix.py shriphani
{'a': ['ni'], 'i': ['phani', ''], 'h': ['riphani', 'ani'], 'n': ['i'], 'p': ['hani'], 's': ['hriphani'], 'r': ['iphani']}

shriphani@linux-s359:~/scripts/Strings> python suffix.py palakodety
{'a': ['lakodety', 'kodety'], 'e': ['ty'], 'd': ['ety'], 'k': ['odety'], 'l': ['akodety'], 'o': ['dety'], 'p': ['alakodety'], 't': ['y'], 'y': ['']}

shriphani@linux-s359:~/scripts/Strings> python suffix.py scrappycoco
{'a': ['ppycoco'], 'c': ['rappycoco', 'oco', 'o'], 'o': ['co', ''], 'p': ['pycoco', 'ycoco'], 's': ['crappycoco'], 'r': ['appycoco'], 'y': ['coco']}

Bingo.

Anyway, I was listening to a bunch of Erik Demaine lectures courtesy OCW (and I am extremely jealous of Demaine, he got his BS at age 14 !) and I sort of wondered when he mentioned that the Big O didn’t work when we had a chain of functions such as n² = O(n³) = O(n⁴) but this doesn’t carry on indefinitely.

I couldn’t help wondering:

So n = o(n²) and then I am left wondering, but I wrote n = O(n²);c=1, n₀=1 and here I am stating that I have n is << n^2 so it is no longer an asymptotic upper bound…. So my question is, am I getting everything wrong here?

Leaving all that aside, I am setting new records for low personal hygiene standards (although I am quite careful about dental, hand and the rectal departments)… college life rocks….

So, I came across this blog called desitech which covers technologies that would aid Indians as they lead their lives. The blog speaks about interesting startups, events, personalities and so on.

As per the site, we can soon see Indian monuments in 3D courtesy Microsoft Research’s “Digital Heritage” project. Or how about that post on TechVista (which I really want to attend). Finally, someone has taken the responsibility to put together something that will help us figure out which Tech event is being held where and what we can expect to learn from it (trust me, it was a headache when I was trying to find out) and I think they (Prashanth Mohan and Bhavish) deserve applause for maintaining desitech.

So, after a ghastly essay season in fall 2007 where I managed to get myself rejected from a bunch of colleges, I find myself in a similar situation again. This time, its Google/MS to whom I should be bragging without seeming like I’m bragging. Although these two have assumed that freshmen are losers, I plan to turn in an app because my chances will go from 0.005 to 0 if I don’t bother applying. 

Google wants me to babble about the toughest CS chanllenge I’ve faced. I am in this dilemma now:

• Powerset Algorithm; or,
• Lexicographic permutation;
• Nothing Else;

I had the opportunity to work on an interesting problem:

Find a decent approximation for the Zeta function (large values), given by:

So, to make any sort of headway, I decided that I would have to look at the graph. Hence, I whipped up a script in Python:

This looks a like:

plot of the zeta function

Observe this plot. We can see that there is a horizontal asymptote at x = 1.65 . 

Hence,

This leads me to conclude one bloody thing:

And,

Now, it shouldn’t come a surprise to all math or CS majors that g(x) is a function whose denominator has a higher degree than the numerator. So for the sake of simplicity, I shall assume that;

Another reason prompting my eagerness to pick that particular function is because of the following observation:

• 1/x is a rectangular hyperbola which looks like:
  

  Rectangular Hyperbola

• If you use -1/x , the graph is rotated about the X axis and it looks like:   
  

  Inverted Rectangular Hyperbola

• So, if you look at the positive X axis, we have already managed to replicate behavior of the Zeta function. All we need to do is move it up and ensure that the limit stays.
• To move this graph up, just add 1.65 to f(x) and it will work:   
  

  Inverted Rectangular Hyperbola Moved Up by 1.65

• So, the limits match, the behavior matches and all we need to do is test:

And this looks like:

A Plot of Proposed Approximation and The Zeta Function

Hey, this thing seems to replicate the behavior of the Zeta function way below x=100. Assignment done !!!!

I had another question which is coming up in the next post. I am in love with Discrete math.

Anyway, I attended this job fair thingy and got free stuff from Google, MS and others (MS was giving us ping-pong balls…). Google’s pens are serving me well. Anyway, I am sure I won’t be accepted as an intern anywhere thanks to the fact that every company thinks that freshmen are losers and don’t deserve to be emloyed right in their first year.

Anyway, keep waiting for the second approximation I did.

I feel like an arsehole right now. I forgot to change the output to god-damned lowercase on an intro CS project and managed to score 90…..

Any way,

Dumb, Dumber and Dumbest, that is how my intellect is deteriorating. I feel like a n00b. Bloody spec was so long for such a short POS.

Anyway, I was trying to use matplotlib to do interesting stuff in my discrete math class (I actually made a blooper in homework 1 over there as well, awesome kick off, isn’t it?).

Anyway, with my awesome track record in carelessness, this was supposed to happen. Did any of you guys blow up intro CS classes as well?

Anyway, we have moved to proof theory in Discrete Math and I have seen the weirdest names in the world already- modus ponens ?

Exams approaching soon. This blog is really deteriorating in quality.

Deccan chronicle is a leading newspaper in Southern India and its online version is marketed by a company - Pressmart. Deccan Chronicle’s blog carried the following ads this morning:

The Indian media….