## Sunday, July 09, 2017

### Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don't these these algorithms are the most efficient algorithms

#
# dynamic programming for binomial co-efficient
#
def dynamic_bc(n, k, indent=0):
#
# return (n k) using dynamic programming
# tail cases are k == 0 or k == 1
# (n 0) = 1 and (n 1) = n
for i in range(0, indent):
print " ",
print "%d:%d" %(n, k)
if (k == 0):
arr[n][k] = 1
return 1
if (k == 1):
arr[n][k] = n
return n
if (n == k):
arr[n][k] = 1
return 1
# (n k) = (n!)/(n-k)!k!, lets split it further
# n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!
# or (n k) = (n-1 k) + (n -1 k-1)
if (arr[n-1][k-1] == 0):
arr[n-1][k-1] = dynamic_bc(n-1,k-1,indent+1)
if (arr[n-1][k] == 0):
arr[n-1][k] = dynamic_bc(n-1, k,indent+1)
return arr[n-1][k] + arr[n-1][k-1]

def bc(n, k, indent=0):
#
# tail cases are k == 0 or k == 1
# (n 0) = 1 and (n 1) = n
for i in range(0, indent):
print " ",
print "%d:%d" %(n, k)
if (k == 0):
return 1
if (k == 1):
return n
if (n == k):
return 1
# (n k) = (n!)/(n-k)!k!, lets split it further
# n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!
# or (n k) = (n-1 k) + (n -1 k-1)
return bc(n-1,k,indent+1) + bc(n-1,k-1,indent+1)

number = 6
select = 3
arr = [[0 for x in range(0, number)] for x in range(0, number)]

print bc(number, select)
print dynamic_bc(number, select)
The output for the first call with full recursion

6:3
5:3
4:3
3:3
3:2
2:2
2:1
4:2
3:2
2:2
2:1
3:1
5:2
4:2
3:2
2:2
2:1
3:1
4:1
20


The output for For the first call with full recursion

6:3
5:2
4:1
4:2
3:1
3:2
2:1
2:2
5:3
4:3
3:3
20

Python supports memoization via functools (wraps, lru_cache, etc). I am using the wrapper (decorator pattern). Using the following pattern makes the programming so transparent
#
# dynamic programming for binomial co-efficient
#
from functools import wraps

def dynamic_bc2(func):
cache = {}
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap

@dynamic_bc2
def bc2(n, k, indent=0):
#
# return (n k) using dynamic programming
# tail cases are k == 0 or k == 1
# (n 0) = 1 and (n 1) = n
for i in range(0, indent):
print " ",
print "%d:%d" %(n, k)
if (k == 0):
return 1
if (k == 1):
return n
if (n == k):
return 1
# (n k) = (n!)/(n-k)!k!, lets split it further
# n!/(n-k)!k! = n(n-1)!/(n-k)!k(k-1)!
# or (n k) = (n-1 k) + (n -1 k-1)
return bc2(n-1,k-1,indent+1) + bc2(n-1,k,indent+1)

number = 6
select = 3

print bc2(number, select)

Comparing the output will show the affect of functools. The output with functools is:
6:3
5:2
4:1
4:2
3:1
3:2
2:1
2:2
5:3
4:3
3:3
20



## Thursday, July 06, 2017

### Iterative combinations algorithm

The algorithm is quite straight forward, see the code in python below

#
# Do iterative combinations generation
# From Knuth's observation, we know for (6 3) that
# [0, 1, 2]
# [0, 1, 3]
# ..
# [3, 4, 5]
# Basically we can see a set of for loops, if we call the columns c1,c2 and c3 then
#
# for c3 = 2 to n-1
#  for c2 = 1 to c3-1
#   for c1 = 0 to c2-1
#
# The loop gives us what we need
# My implementation is based on an index (i) and max (n)
# which are used to determine the next value to generate
#
def iterative_combination(n, k):
a = [i for i in range(0, n)]
index = k - 1
done = False
while (done == False):
print a[0:k]
while (a[index] == n - (k - index)): # boundary for that index
index = index - 1
if (index < 0):
done = True
break
a[index] = a[index] + 1
while (index < k - 1):
index = index + 1
if (a[index] == (n - (k - index))): # initialize the next neighbour
a[index] = a[index - 1] + 1



### Random CS picture

Here is a random picture from a computer science topic

The picture is a counter example of why greedy selection does not work optimally for the set cover problem. If the picture seems not so well done, it's because my asymptote skills are lacking :)

You can probably guess what I'm reading by connecting set cover with combinatorial generation of combinations.

## Wednesday, July 05, 2017

### Combinations revisited

I've been trying to relearn some of the combinatorics I used to know, I redid a nice recursive algorithm (from early university days), with python it looks so beautiful and nice. A simple implementation is below, so nice and simple.

#
# I'm inspired by two algorithms I saw, both are recursive.
#
# Example:
# ((1, 2, 3, 4), 2) - means select 2 out of 3
# should produce (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)
#
# The idea from a recursive perspective is this
# we pick an index - say 1, then we pick the next (n-1) elements
# to go with it
#

def rec_comb(a, i, j, k, n):
#
# array a built upto index i
# selected k at a time of max
# length n
#
if (i == k):
print a[0:k]
return
for l in range(j, n):
a[i] = l
rec_comb(a, i+1, l+1, k, n)
return

def combination(n, k):
#
# n (numbers from 1..n), chosen k at a time
#
a = [0 for i in range(0, n)]
rec_comb(a, 0, 0, k, n)
The sample output for ${6 \choose 3}$ is:

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 1, 5]
[0, 2, 3]
[0, 2, 4]
[0, 2, 5]
[0, 3, 4]
[0, 3, 5]
[0, 4, 5]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

The output lends itself to a simple and nice iterative algorithm, I'll follow up on.

The interesting follow up to combinatorial generation algorithms is using ranking and unranking. At this point, I think we need a O(n) to identify if two combinations are the same -- given in any order of elements. For example to compare $\{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{3, 1, 2\}, \{2, 3, 1\}, \{3, 2, 1\}$ we need to identify them and associate the same rank with them. I think for a subset of size $k$, the cost of ranking is $\theta(k)$, but I need to see if there is a better way to do it.

## Friday, July 01, 2016

### Thoughts on Agile programming - team size

I've been thinking about this for a very long time. What would be an ideal agile team size -- what would be a core team size to be more precise. I've been told in the past that it's 5, but I think it's 4 and here is how I think the team should be organized

Role Role Role Role
Developer1 Developer2 Reviewer/Test1 Reviewer/Test2
Here Reviewer/Tester and Developers should exchange roles if required and be flexible to work both ways for maximum efficiency. Note the role of Reviewer/Tester could be easily done by another Developer.

Here is how I would schedule their interactions

Day Room1 Room2
1 Developer1 and Reviewer/Test1 Developer2 and Reviewer/Test2
2 Developer2, Developer1 and Reviewer/Test1 Reviewer/Test2
3 Developer2, Developer1 and Reviewer/Test2 Reviewer/Test1
4 Reviewer/Test2, Developer1 and Reviewer/Test1 Developer2
5 Reviewer/Test2, Developer1 and Reviewer/Test2 Developer1
6 Developer2, DeveloperReviewer/Test2 and Reviewer/Test1

Teams will think I am crazy for suggesting working 6 days a week, this problem can be resolved by splitting day 6 into some hours each day. For example 1.5 hours a day could be kept aside each day for the developers/reviewer-tester to interact and day 6 could be eliminated all together

In my scheme, each person gets a day/some time to themselves each week. All of them collaborate together and work together frequently. In this scheme indepedence is as important as the inter-dependance between each member

What do you think?

### Live patching on PPC64LE

Michael Ellerman has a great blog with all the technical details. There was a lot of work, brain storming and discussions involved. Check out http://mpe.github.io/posts/2016/05/23/kernel-live-patching-for-ppc64le/

## Thursday, October 15, 2015

### Some programming basics

As our programming knowledge grows, we sometimes forget that computers are not human. Although the incremental and consistent growth of AI techniques, mining may make us believe otherwise :) This is not a blog about AI or ML, but about some basics

From my understanding of real numbers, I can easily postulate that

0.1 + 0.1 = 0.2 -- (1)
and
0.1 + 0.1 + 0.1 = 0.3 -- (2)

But for a computer formula (2) can be hard to comprehend and as a computer programmer we forget that from time to time

I asked my python interpreter

>>> 0.1+0.1+0.1 == 0.3
False

and later asked what is 0.1+0.1+0.1

>>> 0.1+0.1+0.1
0.30000000000000004

Try this in your favorite language and see what you get -- the math underneath should be the same

Reference - https://docs.python.org/2/tutorial/floatingpoint.html

## Sunday, September 27, 2015

### Some more interesting combinatorics

I tried to solve the following problems from the book by Lovasz and got wrong - well atleast the basic thinking was right :)

Problem 1: We have $20$ different presents that we want to distribute to $12$ different children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?
Problem 2: We have $20$ kinds of presents with unlimited supply of each kind. We want to give this to $12$ children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?

What do you think the answers are?

## Monday, January 12, 2015

### Happy New Year 2015

A happy/prosperous/safe/healthy new year to one and all. 2014 has been great, but also unexpected. My home Linux box crashed and I was forced to move to my MAC-MINI for my day-to-day work. Hopefully this year, I'll buy a good machine and get back to Linux soon. Desktops are getting harder to find and maintain (in terms of space), but still the best option IMHO. The sound of the spinning hard drive, powering on the desktop after a long vacation is just too much of fun to miss. My last desktop was AMD based, I have to move to Intel, may be I'll wait a bit more. May be I'll get lucky and someone will send me new cool hardware for free to hack on :) Hint, Hint!

I did not mean to make this about my need for new compute. Here are my predictions for 2015/16 (yeah.. a bit more)

1. Data center compute will get interesting with new processors and workloads
2. OS Wars will light up again
3. Children/Kids will get earlier access to computers and buy more hardware
4. Internet and bandwidth consolidation will across several devices - phone/computer/TV
5. People will start paying for cloud storage, storage is now a key bottleneck
6. MAC OS will continue to gain desktop share
I am avoiding any security based predictions, you can guess why? I'll revise these soon, some time in Q2 this year

## Tuesday, October 07, 2014

### Quick Review - The race of my life

I just finished reading Milkha's autobiography - The race of my life. I loved the simple writing and the length of the book. I must confess that having seen the movie earlier made it easier for me to read the book, however the movie and the book do not map 1:1.

Milkha's book is filled with a story of tragedy of the bloody partition, determinism of a father to educate a child, hardwork and struggle of the youth of Milkha and his progress from an Army Jawan to almost a lieutenant, his days as sports administrator and his feelings for the current state of sports.

All the events in which he participated, the cultural gaps between India and the rest of the world and his ability to learn & improve and work hard with the coaches is clearly demonstrated. They are some hilarious moments about his sister Isher thinking he was shot during a race :)

A great read, should not take you very long to complete and you'll end up feeling motivated to reach your goals.

## Sunday, August 17, 2014

### Math by brute force

I came across a problem in a book on Combinatorics

In how many ways can 5 gentleman and 3 ladies be seated such that no two ladies sit next to each other?

The book's answer was 5!. Clearly not very believable, I decided to warm myself up and try and find an answer.

My first answer was

8! - 2.7! - 6.6!

Something did not seem right, so I decided to use brute force. I wrote quick python code to list 8! permutations (all of them) and discard positions with two ladies together (yes, I permuted classes with numbers and types). The answer was 14400. Clearly I missed something and the computer cannot be wrong - well brute force is usually slow but right :)

A little more thought and use of common sense got me to the right answer

8! - (3 C 2)*2*7! + 6.6! (via inclusion/exclusion principle)

I am so excited to use brute force to check my answers - do you?

## Friday, May 23, 2014

### Lessons learnt - cheap Android devices

One of the best things about an Android device is that it comes in various form factors and various price ranges. Over the years I've bought close to 6 Android devices. My first device was expensive and had no GPU hardware. I could not play games on it, so I decided to move to another one. This time I got a Nexus 4 as a gift

Then I decided to buy a device from an Indian manufacturer with a quad-core CPU/1GB RAM/GPU and a decent display resolution with a 5" screen (Karbonn S5). The device was cheap and I could not help but compare the device and be delighted with my purchase. Over the year of usage of this device, I learnt my lesson

1. There are absolutely no updates for the device - why do I care, what this meant is that I was left open to OpenSSL heartbleed.
2. The phone's hardware, touch screen started failing, some areas stopped responding
3. The firmware on the phone was signed using test-keys. A lot of useful software started detecting the phone as rooted :)
4. The key bottleneck for most software is not number of CPU's, but the amount of RAM/Speed of the processor and the quality of the GPU

Lesson learnt - buy a phone with good reliable hardware and frequent updates, use the cheap ones for experimentation and development

The good news is that since the hardware was cheap, I could easily replace it and keep the phone to try a cyanogenmod upgrade on it. Can't do much about the bad hardware though except use it as a device to try experiments on :)

## Wednesday, December 11, 2013

### Interesting combinatorics problem

I saw this problem in an old book on combinatorics I had, it took me a while to solve, but it is easy if you are familiar with the work of Euler.

Prove that an even length palindrome of integers is divisible by 11

If you know the answer - post it in the comments. If not, wait for a post by me :)

## Monday, October 28, 2013

### My first useful JavaScript program

I was recently going through my son's workbook and it had an interest way of teaching addition - probably the Montessori method. The idea was to create a table of sum's of a few numbers and color numbers to see a pattern. I was quite amused and decided to see if I could write the code in JavaScript, a language I am trying to learn, I am going to do some additional work like graphical Towers of Hanoi with it as well, but for now I wanted to start simple

Guess what - I succeeded in writing what I consider as a useful program (although I wrote it quite badly)

Here is the code
Here is the Javascript Here is the output

## Friday, October 11, 2013

### Your code is only as good as the tests you run on it

Computer programs have an interesting well known quality - even incorrect programs can produce the desired output for a subset of inputs. I recently re-learnt this while doing my graphical convex hull implementation

I started with a test strategy of random test generation. Use  a good random number generator to generate

1. Number of random points as input
2. The random points themselves

This strategy helped me test the program from crashes/instability and showed a potential functional issue that showed up when a large number of points were generated. See the diagram below
Can you spot the problem? I now need a specific test case to isolate the problem, random inputs did not provide the necessary clue with smaller inputs. Luckily for me, I found a good set of inputs at http://stackoverflow.com/questions/482278/test-case-data-for-convex-hull

I ran three test cases and found the first two ran fine

The third one was a hit, it broke my algorithm
Beautiful visualization, but the code was clearly broken. After looking at the diagram and looking at the code, I realized that I was not handling co-linear points correctly. Finally, I got

Now, I am back to the random testing strategy and have gotten satisfactory results so far

NOTE: My test feedback strategy is based on visualization, one could even automate the tests

## Wednesday, September 25, 2013

### Who inspires you?

Many of us are inspired by role models around us, in person, in media, in history, men and women who lead by example. I remember an instance - a colleague of mine was asked about role models and he was selected because he mentioned his grandfather. Other colleagues who mentioned names like Mahatma Gandhi were rejected, because in the HR's mind, a role model has to be someone you personally know. I felt those were very strong opinions to make a judgement for employment

In the past, I've had several role models

• My dad - for simplicity, integrity and courage to do the right thing and caring for others. Ability to network, empathize. Social causes and care for poor.
• My mom - for her ability to manage so many things, manage the family, swiftness, love and extreme courage. Her ability to network
• Mahatma Gandhi - For large traits of what I saw in my dad.
• Don Knuth - For being so nice, smart and humble
• Ex-leads - technical leads in my first job, software architects, distinguished engineers from whom I've learnt a lot. Learnt virtues of caring for people beyond the scope of work.
• Relatives and friends - who've stood by thick and thin, good and bad times
Today I was inspired by our security guard. His simplicity, his dedication to work and sincerity inspired me. I write this blog and dedicate it to all those who inspired me. I think we don't need to look very far for inspiration, it is right around the corner, in my case right at my doorstep.

I hope all of us find many role models who inspire us to do the right thing for ourselves and the society we build together.

## Thursday, September 19, 2013

### The call for better reading/writing skills

I am sure you've faced it and done it to others - not read the entire email in totality or communication in full and missed parts of it. With the abundance of information comes the challenge for the new age of engineers to read and parse information completely. There is a challenge that people writing blog posts such as me, do a good job of delivering the information in manner that key points are not missed

### Summary of the problem

• Of late, I've seen people ask questions already answered in the email they are replying too
• People chain emails expecting everybody to read things top to bottom
• Most people reply on top of emails. Top Posting

I think the open source community solved this problem with rules and netiquettes, but most of us who are not aware of them - fail to see the importance of communicating clearly so as to get maximum retention benefits from the audience of the communication.

### In my mind, here are the best practices

• Make sure that the key information is not hidden in a paragraph, but upfront
• Try to summarize, re-emphasize
• Use best practices, netiquettes
• Don't forward or reply to long chains, clearly snip out irrelevant content
• Use smart subjects
• Highlight important points

### If you are on the receiving side

• Spend some time on important emails, if required re-read
• Try to limit the amount of emails you read - batch process, don't switch too often
• Remember, email is official communication

## Wednesday, September 18, 2013

### A poor way to do sorting in an OO language (java)

Going back to Java after so many years is an interesting experience. I made the classic rookie mistake with implementation of a sorting library. All good programming practices tell you that manipulation methods on a collection should always be static and not bound to the class. To top it all, this was the first time I was using generics after spending some time reading about them :)

I had done things the other way around, almost as if I had implemented a stack with data. My ego was too big for me not to succeed with that technique. Here is an implementation of selection sort. Below is what I ended up implementing

/**
*
* @author balbir
* @param
*/
public class SelectionSort < Item extends Comparable > {
private Item[] elements;
SelectionSort(int N)
{
elements = (Item[]) new Comparable[N];
}

public void sort()
{
int min;
for (int i = 0; i < elements.length; i++)
{
min = i;
for (int j = i+1; j < elements.length; j++)
{
if (elements[j].compareTo(elements[min]) < 0)
min = j;
}
Item tmp;
tmp = elements[i];
elements[i] = elements[min];
elements[min] = tmp;

}
}

public void dump()
{
for (int i = 0; i < elements.length; i++)
System.out.print(elements[i] + " ");
System.out.println();
}

public void load(Item a[])
{
for (int i = 0; i < elements.length; i++)
elements[i] = a[i];
}

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Integer[] a = {1, 2, -1, 3, 0, 5, 7, 9, 4};
SelectionSort s = new SelectionSort(a.length);
s.dump();
s.sort();
s.dump();
}

}



It is funny how I had to use a load class to get the data and call the sort method. What a bad decision, the reason I shared this post is just to show that with generics one can indeed mix classes and class templates. I for example mixed Integer and Comparable and the default implementation worked.

## Sunday, August 04, 2013

### I keep going back to concrete math, but this time I went with a tool

Of late, I seem to be stuck in a loop with books. I read parts of them and then seem to come back to the very beginning of the same book and discover something new. I am stuck in a partial loop in an "open form". Of late that has happened with Concrete Mathematics. I started with the first chapter on Recurrent problems - you seen the irony :)

Anyway, one of the problems is Towers of Hanoi with limitation. Don't go to the intermediate peg directly, go to the destination peg and then go to the intermediate peg. I remember reading somewhere that Knuth used Macsyma for a bunch of verification on Metafont (I could be wrong). I decided to use Maxima. I used the solve_rec procedure

The recurrence equation is

solve_rec(a[n] = 3*a[n-1] + 1, a[n]));

and Maxima was quick to respond with the answer

I wonder if Knuth is right, in the future most of the burden of mathematical complexity of finding a solution will be delegated to computers.

### Fedora 17 EOL

For those who missed it, the notification is at Fedoa 17 EOL announcement. Looks like I'll be forced to upgrade :)

## Sunday, February 03, 2013

### My prediction for the new wave of consumer electronics

Remember the time when new laptops/desktops were fun to have. A laptop was a must have for college (I never had one, but thanks to my brother I had a great computer, where I learnt all my programming). The new rage is now the new era of merged functionality

• Mobile
• Photos
• Email
• Maps & GPS
• Games
• Internet browsing
• Video calling

The gadgets out there are amazing, to be honest I own quite a few of them. I've had a prediction for a while on what would happen next (happen next to the laptop/notebook world). Lets look at the pros and cons of the mobile computing era devices versus laptop/desktop world

Pros

1. Easier to carry around
2. Single device to carry (integrated functionality)
3. Cheaper software licensing cost (games for \$5, etc)
4. Touch capability (better user experience)
5. Growing compute and memory capacity

Cons

1. Limited storage
2. More frequent recycling
3. Not upgradable in any sense
4. Faster obsolescence
5. Harder to create content (programming to be done on laptops/desktops, documents are hard to create)
6. Very limited screen size

Gadgets are fun and most people don't care about limited storage today or content creation, but limited storage along with faster obsolescence along with limited ability to create content will help the desktop/laptop world emerge back.

My prediction based limited storage and changing laptop world (touch screen) is that the laptop world will emerge back and win again.

## Sunday, January 27, 2013

### Operating Systems and their UI era

This afternoon as I had free time to ponder on something totally unrelated to the need of the hour, I was thinking of user interface evolution through time. I'd like to quickly classify them as

1. *NIX era
2. Desktop era//Gaming console era
3. Mobile device/Tablet/Cloud computing

NOTE: *NIX/Desktop and Mobile devices do co-exist today, but the era classification is based on popularity as read through magazine articles/online and casual discussions

The first *NIX era was a terminal era, with limited terminals (remember the phosphor screens) and wonderful keyboards that lacked (arrow keys, I just have to assume looking at the design of the original vi). The UI was quite straight forward (text), of course there were some high end workstations as time evolved. The most popular *NIXes were BSD and AT&T variants

The desktop era started with the PC and DOS. Keyboards were designed for non programmers, they were friendlier. With the introduction of GUI OS's, mice and keyboard were the primary input devices (supplemented by new generation pen & other new input techniques, but the focus was mice and keyboard). They had good GUI's, nice video and sound cards and were optimized for keyboard and mice. This lead to a sporadic growth in Internet usage, gaming. DOS/Windows/OS-X and MAC-OS variants with new design inspired from *NIX, but still different were the ruling OSes. *NIX were pushed to large systems where they would continue to run and serve large workloads as before.

The latest trend is mobile/tablet computing, this is again a market captured back by variants of *NIX (Linux - Android) and iOS (BSD) variants. Touch screen with LCD front ends with gesture awareness and multiple sensors are dominant UI inputs. It is good to see OS's designed on older principles race into the new era where voice input/GPS sensors/Cameras/touch screens/gestures are the primary interaction points with a lot of automation and simplicity built into the software on top of them. As I write, these devices are making their way into gaming consoles as well. These workloads are well supported in the back end with cloud computing work flows that provide the necessary horse power for calculating complex map routes, document editing and much more (most of these are again based on Linux servers).

I suspect the next generation will be projector driven devices, it will be interesting to see how *NIX variants will drive the next generation of computing devices.

## Monday, September 03, 2012

### Algorithms beyond school

I was working on a list of algorithms a new college graduate ought to know to either

• Do well in an interview
• Make quick progress through the learning curve

Here is the list I have so far, I would appreciate comments on what else to add

1. Population Counting
2. Multi-precision Arithmetic
3. Fast Fourier Transform
4. Fast Prime Number Generation
5. Quicksort
6. Union-Find
7. String searching (KMP, Regular Expressions)
8. Polynomial Multiplication
9. Calculation of Pi
10. 8 Queens Problem
11. Instance of a turing machine simulation
12. Tries
14. Red Black Tree
15. Huffman's algorithm
16. Graphs - DFS, BFS
17. Graphs - Bipartite
18. Minimum Spanning Tree
19. Hashing algorithms
20. Linear programming?
21. Classes of problems - P/NP/?
22. Vertex Cover?
23. Synchronization (locks/mutex/spin locks)
24. Lockless algorithms
How does the list look?

## Friday, June 29, 2012

### Power of programming - online

An article of mine got posted online, check out http://www.linuxforu.com/2012/06/power-programming-bitwise-tips-tricks/

## Saturday, March 31, 2012

### Poem of Physics

Oh! I hope you see my plight
Why does light travel at the speed of light
Which almost seems infinite!
When I think of infinite, I think of god
Does he hide,
Like the infinite?
Hidden in corners, exposed by the equations right
I can see the infinite, but not his might
In a circle so beautiful, like the zero
But, yes sometimes I wish I never know
For its the unknown that makes us go

-- Balbir Singh

## Saturday, February 11, 2012

### Wish list of books - need suggestions

I've got a big list of books that I own. Here is what I intend to purchase in the next set. I am looking for suggestions on what would make useful reading? I am open to all categories of fiction/non-fiction/technical books. It would help if you point me to a review or provide me your own review comments

### Enumerative Combinatorics - volume 1 (second edition)

The second edition is out and available at math.mit.edu/~rstan/ec/ec1.pdf

The book is extremely well written, although I've forgotten and probably never read a few of the topics mentioned in chapter 1, like one dimensional complete local ring. From where I stand at the moment, completing chapter 1 and understanding the twelve fold way will be quite an accomplishment :)

Do checkout the book. The first chapter is 221 pages with 203 exercises at the end.

# Sage Beginner's Guide  is an introductory book for the Sage math software, an open source mathematics system. Sage is a free alternative to Mathematica, Maple, and Matlab. The book does a great job explaining the basics of Sage. Each chapter is well written with my favorite "Time for Action", that allows the reader to explore the software and understand the experiment in depth. It is a great way to explore how things work and completely in line with what the book says "learning by doing: less theory, more results".

The first chapter is a tour of "what can be done with Sage". The second chapter deals with installing Sage across a variety of platforms. Chapter three eases the user into the sage interface, it discusses how to use the CLI, the notebook interface and get help. Chapter four is all about python; the chapter does a great job introducing python: one of the best I've seen in a book. It arms the reader to work with Sage and python.

Chapter five focuses on vectors, matrices and linear algebra. Sage include numpy and the chapter covers numpy in good detail. Chapter six is my favorite. I love plotting graphs, the chapter discusses various types of plots. The chapter does a great job explaining Matplotlib. Chapter seven is all about symbolic mathematics: integrals, differentials, ODE's, solving equations, finding roots, Taylor series and more. Chapter eight is about solving problems numerically and for me this is the best chapter in the book. It covers a variety of topics -- finding roots, maxima and minima of functions, gradients, integration, discrete Fourier transforms, window functions, solving ODE's. linear programming, constrained optimization to probability. Chapters five to eight are the meat of the book and I expect all readers to keep referring back to these chapters time and again.

Chapter nine is about advanced python programming, but I was a little let down based on what I had seen in chapter four. The chapter covers OOP, modules, exception handling and unit testing. What I did not like was the way the code is formatted and occupies a majority of the contents of the chapter. Chapter ten is about my favorite tool, LaTeX, it covers integration of LaTeX and Sage. No mathematical software is complete unless one can build interactive workbooks and the author does a great job explaining how to go about that business with interactive graphics and good typesetting.

Given the capabilities of Sage, the book fails to cover some of the discrete mathematics aspects, like graph theory, combinatorics and cryptography. To be fair, the author does mention in the preface the focus is on calculus, ODE and linear algebra.

Sage is a beast with several projects integrated under a single umbrella. This book meets the goals it sets out to achieve and does so in an incredible manner with clear definition of chapter goals, good summaries and excellent examples. The breadth of coverage of topics is very good for an introductory book on Sage. If there is one book I could recommend on getting started with Sage, it would be this "Sage beginners guide"

## Friday, May 13, 2011

### Slingers - More Lasit's?

In todays IPL match between Kings XI Punjab verus Kochi Tuskers, the Kochi blowers were seen imitating Lasit (Slinger) Malinga in their bowling action. Surprise, Surprise, is this going to become a trend soon?

## Saturday, April 30, 2011

### Match fixing (WC 2011)

I wonder if such controversies are created to make people believe that the losing team was too good for the opposition (winning team), but money got in the way.

Somehow, the WC 2011 win does not seem fixed, I remember seeing the joy on Mahela's face and the joy when the Srilankan's got to the half way mark. They thought they had won the match.

Allegations take away from the hard work of the players and glory. It sure is hard on players who are dedicated to the cause of their teams.

### ATI driver 11.4 is out

It is here works perfectly well with my Fedora 15, beta system. I hate moving away from the open source driver, but I've got to do so for thermal (probably) and speed reasons (6x). Mesa has some interesting changes, including support for direct3D, but for now it is time for me to experiment with OpenCL :)

## Saturday, April 23, 2011

### Draft of Enumerative Combinatorics - volume I

Richard P Stanley has the draft of the second edition available at http://www-math.mit.edu/~rstan/ec/ec1/. The book is a classic and highly recommended if you are interested in combinatorics. The book assumes advanced knowledge of mathematics (commutative integral domains, generating functions, etc). I am reading the first chapter and I've been ignoring some of the rigor to get the most from it.

## Friday, March 18, 2011

### Knuth's Earth Shaking Announcement

I found the video here (http://river-valley.tv/tug-2010/an-earthshaking-announcement). It is quite awesome!! Earth shaking reminds me that I request all readers of this blog  wish Japan all the very best as the country tries to cope with the enormous loss and devastation.

## Wednesday, February 23, 2011

### Kernel Mode Setting and Resolution

The main pain of upgrading to rawhide on Fedora has always been -- "Hey, what about my proprietary graphics card support?". I've been bitten a few times. When I made the decision to buy a card, I chose ATI so that I can enjoy the benefits of a good open source driver.

Rawhide has moved to gnome 3, and gnome shell requires 3D graphics or falls back to the old style gnome. With kernel mode setting, there is sufficient support in the form of DRI/DRI2 and Mesa 3D to support OpenGL.

My main issue was getting the right resolution. Here is a well known way of solving the problem

Solution

1. Run the cvt(1) command, specify the resolution and refresh rate, it will output a set of mode lines. See http://www.arachnoid.com/modelines/ for a good tutorial on mode lines (NOTE: You might not need to do this if EDID works fine for you)
2. Modify /etc/X11/xorg.conf and add the following under the monitor section
3. Modeline "...." (whatever cvt output)
4. Option "PreferredMode" "Name of the mode used above"

This should get you going and help you come to the desired resolution

Solutions that did not work

1. Adding video=... at boot time
2. Disabling KMS, helps fix the resolution, but the correct 3D driver (mesa DRI) does not load, you are left to Software 3D emulation (that sucks)

Enjoy, I hope someday we'll get an open source driver for openCL :)

## Wednesday, January 26, 2011

### Distro Hopping

After trying some more distros, I decided to move to debian part-time. I was surprised to see Linux Mint support debian (albeit only the "testing", also known as "Squeeze" release).

I am in love with the combination of mint and debian. The version of the kernel is still 2.6.32, but debian stability and support is rock solid. I'll slowly migrate to the experimental version when "Squeeze" is released.

The rich packaging and stability of debian with the front ending of the very best makes this a lovable distro.

I am posting some screenshots, enjoy!