Posts from — April 2008
In Honor of Professor Tim Berners Lee
I want to dedicate this post to professor Tim Berners Lee, the creator of the World Wide Web for having given us an excellent invention. The web has been integral to my education, to my recreation and in general in all walks of life. It has helped me reach out to individuals across the globe and learn from them.
Enough said, Happy 15th Birthday W3 !
April 30, 2008 1 Comment
Roman Numerals - More Python
Since I love Python and since 90 % of those online judges won’t allow me to use Python to submit my solutions, I have to contend with writing the script and hoping it is right. I am now solving a few ICPC sums from last year and I absolutely love them. I first picked the North America, East/Central Problem Set and found this question on roman numerals. Basically subtracting two supplied roman numbers. Guess what this reminded me of, Claude Shannon of course ! Shannon designed a box that used only roman numbers. All hail God Shannon - the best the world had to offer. Well, I hacked up a simple solution in a few seconds. It looks horrible but who cares.
#Author: Shriphani Palakodety
#Roman Numerals Problem.
#Solution to:
#ICPC North America East-Central Problem1
#Roman to Decimal dictionary
rom2dec_dict = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}
def romToDec(roman_string):
”‘Convert from Roman to Decimal’”
#Move from right to left.
number_dec = 0
i = len(roman_string) - 1
if i % 2 != 0:
while i > 0:
if rom2dec_dict[roman_string[i]] > rom2dec_dict[roman_string[i-1]]:
number_dec += rom2dec_dict[roman_string[i]] - rom2dec_dict[roman_string[i-1]]
i = i - 2
continue
else:
number_dec += rom2dec_dict[roman_string[i]] + rom2dec_dict[roman_string[i-1]]
i = i - 2
continue
else:
while i > 1:
if rom2dec_dict[roman_string[i]] > rom2dec_dict[roman_string[i-1]]:
number_dec +- rom2dec_dict[roman_string[i]] - rom2dec_dict[roman_string[i-1]]
i = i - 2
continue
else:
number_dec += rom2dec_dict[roman_string[i]] + rom2dec_dict[roman_string[i-1]]
i = i - 2
continue
number_dec += rom2dec_dict[roman_string[0]]
return number_dec
There, first ICPC problem. I would love to crunch this set in this week. Some problems seem tough and I really would love to solve them all. I found another interesting problem on circular combination locks. I am still thinking about that one and I hope I can solve it tomorrow.
Well, I am just loving the freedom. Happy Coding! 
April 29, 2008 No Comments
School Life’s Finished
So, I’ve managed a measly 94 % overall in the Intermediate Public Examinations and life’s good.
Well, I guess that in my life there was math, code and more math. I have realized that I get this excellent feeling when beautifully written Python code ( ever saw Python code in Komodo ? With the indentation, it looks beautiful ) performs primality tests, crunches out the Kaprekar / Collatz depths. By now, I think I think ( and a few people certainly think ) that I might be the best candidate to replace an academic and why not ? Most of the people I idolize are in academia and I want to be there as well.
I was browsing through the archives of Scott Aaronson’s Blog and I happened to read an entry where he ranted on CollegeBoard’s decision to remove the CS AP exam. He mentioned that he ate up everything there was to eat in that computer science course. That is true love for the subject. I had a similar experience with the book, “Post’s Machine” by V. A. Uspensky ( the third time I have mentioned it on my blog ). I just kept reading again and again. Talk about great books and that should be mentioned. I knew from then on that whatever the author was, I wanted to be too. Well, Scott’s got a lot going for him. He went to Cornell for Undergrad, went to Berkeley for Grad and is now teaching quantum computing at MIT.
On the other hand, I am going to a less “glorious” place, will probably never end up as a decent computer scientist as well. Well, I can dream on, can’t I?
I have met a lot of interesting people online. Well, I am shit at doing anything in real life, I can at least act as a tiger online, can’t I? 
I’ve got an interesting reading list and I plan to read quite a lot in this week. First, I’ve got to read “Programming Pearls” completely. So far, I’ve been reading pieces of it. Then comes a book called “A Gentle Introduction to Symbolic Programming”. It is an excellent book. I would recommend that as well ( but since I have assigned the n00b status to myself, it might not be that good a read for everyone else ). I’ve got a few other *legally free* ebooks and I’m going to finish reading them tomorrow.
Well, I am out of school ( officially ) now and not a lot has changed. People on the IRC server I first wandered to still call me “charlie” owing to the fact that I have managed to make a complete fool of myself a lot of times when I spoke on topics like “British History”, “Politics” and so on.
I am going to solve a few puzzles I have collected ( Math Puzzles in case you were wondering ). Will blog about them soon. Till next time, goodbye
April 28, 2008 No Comments
A Book on Algorithms.
My Guru and an individual in whose service, I am ready to spend the rest of my life, Mr./ Uncle / Dr. ( I don’t know what he wants to be called ) Prashanth Mohan recommended that I get this cool book entitled, “Programming Pearls” by “Jon Bentley”. I happen to like the warnings the author puts into his book such as, “Boring Material Ahead. Skip to section 4.4 if drowsiness strikes.”. I love the fact the the pseudocode is laid out in such an excellent fashion ( compared so some “pseudocode” I have seen… ). I jumped straight away to the section on “Searching” and realized that I was doing injustice to the writing capabilities of Jon Bentley ( which deserve a lot of respect ).
The only requirements of the book are knowing how to program in a high level language and thats it ! I would recommend that people pick this marvel of a book and add it to their collection ( although looking at the popularity this book seems to enjoy in programmer circles, you might already have it in your collection ).
Oh by the way, I am working on something extremely useless but its a top-secret mission of mine and I will write about it later.
Got involved in some fight with a bunch of “elites” from India’s “elite” engr. college ( no need to ask ). I happened to mention that I liked CS a lot and the discussion veered to something more unrelated to the field such as the methods institutions chose to fill their computer science classes. I mentioned that those who had programmed should be given first priority because the guys would have had *some* idea about process. I realized that I had made the biggest mistake of my life then and there. What followed is:
elite_guy: CS is not about coding. If you want to code in college, why not take those IT courses that are abundant in this nation.
Me: I know what CS is, I might not have a paper which certifies that I am a Computer Scientist, but I have a fairly good idea of what CS is.
elite_guy: CS is about math.
Ah, the classic statement. Like I never knew.
Me: I know it is about math but its basically imperative knowledge of math as opposed to declarative knowledge.
elite_guy: It is declarative knowledge
elite guy links me to SICP.
There are only two conclusions I could come to with that statement:
- The guy skimmed through the book, encountered the words declarative and imperative and felt happy enough to throw them in without knowing what Prof. Abelson intended to say.
- The guy was not interested in getting what he said, right. His aim was to somehow contradict me, even at the cost of speaking the right thing.
By the way elite_guy is just some stupid nick I could come up with. I didn’t want to stain his reputation by directly mentioning his name.
Got to go and work. Goodbye !
April 26, 2008 3 Comments
Sorting Algorithms - Python Implementations
Well, I have to admit, I don’t know how to begin 1/2 the posts on topics like these. Let me just point out that I was trying to arrange a list of words in dictionary order without using the sort() method available for lists in Python and since I am a lazy what-not, I only wrote a small bubblesort implementation the crux of which was:
alphas = string.uppercase
alpha_dict = {}
for i in range (1, 27):
alpha_dict[alphas[i-1]] = i
So, I created a dictionary which went like:
{”A”: 1, “B”: 2, “C”: 3 ………, “Z”: 26}
One of the words in the list which had to be sorted was “BABELFISH”. Using the dictionary, I created a list consisting of numbers corresponding to the letters which composed the word.
for char in word:
nums_list.append(str(alpha_dict[char]))
num = int(("").join(nums_list))
Then comes the actual bubblesort implementation. And when OpenBySource dissed me for sticking to something so inefficient, I decided I would go and read as much about sorting as I could and well, here is what I have learned.
First, the sorting algorithm that I always knew, BubbleSort. The algorithm is pretty simple. Begin at the first element, if this element is greater than the next element, swap their positions and proceed to the next element. This is how it is supposed to go. Here is a Python implementation:
#Author: Shriphani Palakodety
#Bubble Sort Algorithm Implementationimport copy
def sorter(num_list):
new_num_list = copy.copy(num_list)
n = 0
for i in range(len(num_list)-1):
if num_list[i] < num_list[i+1]:
continue
else:
num_list[i+1] = new_num_list[i]
num_list[i] = new_num_list[i+1]
new_num_list = copy.copy(num_list)
n += 1
return num_list, n
num_list = [2,7,1,5,8,6]
def checker(num_list):
while True:
sacred_tuple = sorter(num_list)
if sacred_tuple[1] != 0:
num_list = sacred_tuple[0]
else:
return sacred_tuple[0]
print checker(num_list)
I can see the question coming up ( if it isn’t, please don’t bother telling me ). “What is that checker() doing there ?”. The thing is that you can always keep running the sorter function. The checker stops the sorting process run by the sorter function when no sorting is performed when sorter(list_name) is run.
The next algorithm I encountered struck me as stupid. Every single kid must have used it. I am ashamed of myself to even have written this thing. Anyway, it is called the “Selection Sort” algorithm. You pick the least valued term in a list, assign it to the first position, from the remaining elements, pick the smallest number, put it at the second position and so on. Here is what I wrote ( and what every 5 year old out there could have written ):
#Author: Shriphani Palakodety
def selSort(list_name):
sorted_list = []
while True:
least_number = min(list_name)
sorted_list.append(least_number)
list_name.remove(least_number)
if len(list_name) == 0:
return sorted_list
break
else:
continue
unsorted_list = [2, 1, 8, 10, 12, 9, 42, 21]
print selSort(unsorted_list)
Actually the code displayed above is a cross between what is known as the “Insertion Sort” algorithm and the “Selection Sort” algorithm. In the insertion sort algorithm, the sorted list is built one element at a time.
The next algorithm I am going to cover is the “Merge Sort” algorithm. This algorithm works by diving a list into a number of sublists and then merging them back to get a sorted list.
Here is the merge function:
left_index, right_index = 0, 0
result = []
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index = left_index + 1
else:
result.append(right[right_index])
right_index = right_index + 1
result += left[i:]
result += right[j:]
return result
And of course, now comes the splitter() function. I am too tired to explain wtf is going on.
if len(list_name) < 2:
return list
else:
middle = len(list_name) / 2
left = splitter(list_name[:middle])
right = splitter(list_name[middle:])
return merger(left, right)
Happy Coding.
April 17, 2008 No Comments
A Few List Methods
I hate reading reference manuals. They bug me to no end and I generally do not get beyond page number 10. These excellent habits of mine were the main reason for my taking up this task. I decided to brush up on my knowledge of Python’s built-in sequence-types and of course, since I love using lists in most of my code, I will attempt to write down some of the List methods in Python. I am not too sure if the same algorithms are used in Python but these work. Well, here goes:
First comes the very familiar append() method.
Usage: some_list.append(element)
#Author: Shriphani Palakodety
def append(list_name, element):
list_name[len(list_name):] = element
>>> list_name = [1,2,3] >>> list_name.append(4) >>> print list_name [1, 2, 3, 4] >>>
Next comes the extend() method. This method takes a list as an argument and appends its elements to the current list.
list_name[len(list_name):] = list_to_add
A bunch of no-brainer methods follow. They are:
def insert(list_name, position, element):
list_name = list_name[0:position] + [element] + list_name[position+1:]
#index(element) - return the index of the first item whose value
#is equal to the supplied argument
def index(list_name, element):
for i in range(len(list_name)):
if list_name[i] == element:
break
return i
else:
continue
return "Element doesn’t exist"
#remove(element) - remove first item from list whose value is "element"
def remove(list_name, element):
position = list_name.index(element)
list_name = list_name[0:position] + list_name[position+1:]
The next method is the count() method. The count method returns the number of times an element has been repeated in a list. This is what I wrote in a few seconds:
freq_dict = {}
index = 0
freq_dict[element] = 0
for i in range(len(list_name)):
if list_name[i] == element:
freq_dict[element] += 1
else:
continue
return freq_dict[element]
That is the count() method. Finally, we have the reverse() method. When used, it reverses all the elements in a list.
new_list = copy.copy(list_name)
for i in range(len(new_list)):
list_name[i] = new_list[len(new_list)-1 - i]
That session served me quite well. I got to write some code and also got myself to read the reference manual.
Well, Happy Coding !
April 10, 2008 2 Comments
Prime numbers, Miller-Rabin
I was looking at a few interesting algorithms to figure out whether a given number was a prime, all because I wanted the fastest solutions possible while solving project euler sums involving prime numbers. And after that session, the sum is still not over and might never be as I have gotten around to post on this blog, the stuff I’ve gathered.The AKS algorithm is of extreme academic importance but has horrible speeds and hence is of no use to me whose main aim to get prime number with utter ease.
I then looked at the Miller-Rabin algorithm and then moved to try out an implementation on my own. I cheated by trying to look at implementations on the cookbook and understood nothing. So it was back to me to figure out something. The algorithm goes like this:
To check if “n” is prime, “n” should obviously be 2 or odd. Forget 2, because if you don’t, I will call you names ( and who needs miller-rabin to prove if 2 is prime ? ).
Since n is odd, n-1 is even. Try expressing n - 1 as . It seems relatively simple. Here is the code to do that:
#Miller-Rabin Primality Test.
#Author: Shriphani Palakodety a.k.a PSP#Now comes one of the world’s fastest primality tests:
def twoPower(n):
factors = []
s = 0
while n > 0:
if n % 2 == 0:
factors.append(0)
n = n / 2
s += 1
else:
factors.append(n)
d = n
break
return s, d
Once that is done, we need to generate a random number which lies in the range . Here is the code to do that:
def randGen(n):
return randint(1, n)
Ok, I agree there was no need for that snippet. Let us move on anyway. The crux of this algorithm lies in the following statement:
if 
and 
for all r in the range 
] then return composite.
Well, this is quite easy to implement in Python:
#Modulo Check
def moduloCheck(rand_int, odd_no, n):
if rand_int ** odd_no == 1 % n:
for i in range(0, n):
if rand_int ** ( ( 2**i) * odd_no ) == -1 % n:
continue
else:
break
return "Prime"
else:
return "Prime"
return "Composite"
Now comes the trouble:
odd_no = twoPower(number - 1)[1]
rand_int = randGen(n - 1)
print moduloCheck(rand_int, odd_no, n)
Have a look at what I get:
shriphani@psp-laptop:~/project_euler$ python miller_rabin.py Prime shriphani@psp-laptop:~/project_euler$ python miller_rabin.py Prime shriphani@psp-laptop:~/project_euler$ python miller_rabin.py Prime shriphani@psp-laptop:~/project_euler$ python miller_rabin.py Composite
BOOM !
The trick to avoiding such problems is to just run the moduloCheck function as many times as possible and if we get more Primes than Composites, then the number is Prime, else Composite
I then decided to create a parameter “k” which would determine the number of times the moduloCheck function should run. Then I implemented a counter to check the frequency of the strings - “Prime” and “Composite” thrown out by the script. Here is the code:
def freqCheck(k, odd_no, n):
freq_list = []
for i in range(0, k):
freq_list.append(moduloCheck(randGen(n - 1), odd_no, n))
if freq_list.count("Prime") > freq_list.count("Composite"):
return "Prime"
else:
return "Composite"
So, the entire script looks like this: http://shriphani.com/scripts/miller-rabin.html
April 9, 2008 No Comments
I’m Going Places !
I recently featured in the comments of Ms. Sramana Mitra’s blog. Sramana as you all know is an entrepreneur who did cool stuff after college. She went to Smith College for a B.S. and to MIT ( !!!! ) for an M.S. in EECS ( !!!! ). I will be there in 4 years don’t worry.
If you have noticed, I haven’t posted a lot in the past few days. The reason is that I am brushing up on my Django skills which have rusted in the past few months. After that I plan to creep back into the FOSS world but till I get something done, I won’t put it up here and that is my policy.
Instead, let me talk of some cool memories that revisited me when I was disturbing the one inch thick dust layer in my room by trying to bring about an order. I happened to come across a booklet that I had loved reading a few years back when I was recovering from my accident - The “Post’s Machine” by V. A. Uspensky.
Tears just welled into my eyes when I saw the tiny booklet, a part of the extremely coveted “Little Mathematics Library”. Indeed, this is such an excellent book on such a simple toy - the Post’s Machine. The author mentioned concepts like programming, algorithms etc, all through an instruction set peculiar to the Post’s Machine which I can still remember to be:
This book had approximately 30 problems I think and I had extreme fun solving each one of these. Well, if the field of Computer Science has to pursue some aggressive methods to improve dwindling numbers of searches, this priceless booklet might just be the right tool to use.
I am pretty sure that this was the book that got me interested in Computer Science. For those of you who can grab this booklet, I am sure you will enjoy it.
April 6, 2008 No Comments
I have Failed to……..
- Impress a bunch of liberal arts majors.
- Failed to prove to a bunch of liberal arts majors that I along with a million others will save the planet from imminent doom.
- Failed to make a liberal arts guy laugh. I can make most laugh at someone else.
- Failed to get them equal opportunity guys to look at even one link ( Google analytics is a handy tool )
- Failed to make it to a decent college and now the entire society around me will consider my few contribs as “invalid and a perfect joke”. The society I live in is full of paper tigers.
- Failed to get a few PE sums to work in < 8 secs.
And yeah, this is not intended to express views of my employer - Shriphani Palakodety and my benefactor - Shriphani Palakodety.
- by Shriphani Palakodety
P.S.: I am going to kick them liberal arts guys in the ballz.
April 2, 2008 No Comments
