Niketan Pansare's blog

Iris - siri like software

2012-01-17T18:24:00.000-05:00

Recently I have started a pet project Iris¹ while doing background study for my recent paper.

Voice commands/response:
Like Siri, it takes user commands and can respond using either Voice or Text.

Portable:
Since it is written in Java, it can run on most OS, including Mac, Windows and Linux. I have only tested it on Mac Lion, so I welcome any beta testers using other OS. For now, some of the features like play itunes, open email, etc are only available on Mac. I plan to add these features on other OS as well.

Configurable:
Most of the features such as use of VOICE or TEXT as feedback mechanism, as well as feedback message are configurable through the configuration file ''user_scripts/iris.config". You can also modify any of the predefined apple scripts (for eg: playSong.scpt) in that folder which will be called by Iris on the voice cammand. Also, for advance users, there are ten function commands that he/she can use to perform user-specific tasks.

Easy to install and use:
All you need to do is download and extract the binary file and run following command:

 
java -Xmx200m -jar bin/Iris.jar

The above command asks Java to run the program Iris.jar (in bin folder) and also specifies that it should not use more than 200 MB of memory.

Lightweight:
The whole setup takes about 20MB.

Client-side:
The speech-to-text is done on your laptop/desktop and not on some remote server. This means you can use it even if have no internet connection. This also means that there is no possibility of some big brother monitoring your voice commands.

Open source:
You are free to download and modify the source. As I am working towards a paper deadline, I am looking for collaborators that would help me with following features:

User-friendly: Improving voice commands
More accuracy: Expanding dictionary to include more words and also to add different 'user accents' for a given word.
Expanding grammar to include arbitrary spoken words.
Apple scripts to accessing contacts and recognizing contact names to assist users with various functionality.
Adding GUI interface rather than command line. Since all the responses go through OutputUtility.java, this is going to be easy.
New features: Support for RSS, Top News, Weather, Popular city names, Dictionary/Theasurus, Web/Wikipedia search, Dictation (to text/messages/events/todo item/alarm/reminders), Jokes, Motivational quotes, More Personalization.

If you have suggestions for improvement or want to collaborate with me, email me at 'NiketanPansare AT GMail'.

Iris uses CMU's Sphinx4 for recognizing speech and FreeTTS for text-to-speech conversion.

References:
¹ Iris is name of my friend's dog (well, no pun intended when I use the term 'pet project'). It is also the anagram of the word 'Siri' (a popular Apple's software for IPhone 4s).

C++ workflow

2012-01-02T00:02:00.001-05:00

Recently I had a memory bug that took me 2 days to figure out. Valgrind gave no error message (well, to be honest, it did give out a warning that got lost in my log messages). gdb pointed to completely random place that led me to believe STL's stringstream was the culprit. Since there was no way I could have definitively say it's not the cause, I couldn't rule out that possibility.

My impatience got the best of me and I foolishly rewrote that part of code using a less elegant solution using arrays. Now gdb started pointing to STL's vector.clear() method and believe it or not I was using std::string to store in it, not some user defined class …. I had it … there is no way in the world I am going to believe that gdb was right (thanks to my confidence in Effective C++ and std::vector < str::string >). But, not knowing the bug in a 'single threaded' 'command-line based' C++ code with access to gdb and pretty printing was driving me crazy. My previous blogpost didn't help either :(

So, on the same evening, armed with my music player and hot cup of tea, I decided to ignore the bug and beautify my code with better comments … geek alert !!!That's when it hit me, due to my recent modification, I was writing past the array bounds in a for loop. The funny thing is it is one of the few memory bugs that valgrind does not report in its final assessment and my best guess is that I was writing over vector's header location (and vector only complains about that during its next operation (in my case was clear()) ... which for all intensive purposes is random).

Embarrassed by this stupid mistake that wasted my two days, I felt humbled to revisit my C++ work-flow.

So, here is a sample workflow:
- svn update
- Code using your favorite editor (Make sure you configure it to conform to your style rules).
- Set DEBUGFLAGS in your makefile that does static analysis (make my_proj).
- Test it on local machines using 'make my_test'
- Run valgrind if necessary and check against below given valgrind checklist
- make style
- make doc
- svn update
- svn commit -m "some meaningful message"

The key principle is:

Automate whenever possible (with emphasis on reusability)

Never ever start coding without an SVN (or cvs or git, etc.). It will save you lot of headaches if your machine crashes or if you want to revert back to a previous version.
If the project has multiple coders/testers/collaborators, it helps if you have some kind of project-management tool like trac or jira. Also, if you are going to release your code to public, you might want to consider project hosting sites like Google Code or source forge.
Though this might seem obvious, don't host the svn server on personal machine or at least make sure to take regular backups if you do.

Use a Makefile that takes care of all necessary tasks (compilation, cleaning, data generation, document generation, code beautification, etc) and a user-friendly README file. (Advance coders can consider automate). Here is a sample Makefile of my current project:

 
CC = g++
DEBUGFLAGS = -g -Wall -Wextra
MINUITFLAGS = `root-config --cflags` `root-config --libs` -lMinuit2 -fopenmp
LIBS = -lgsl -lgslcblas -lm -lstdc++

HEADER = Helper.h MathHelper.h LDA.h Configuration.h
SRC = main.cpp MathHelper.cpp Helper.cpp LDA.cpp
OUTPUT = spoken_web

spoken_web:     $(SRC) $(HEADER)
        $(CC) $(SRC) -o $(OUTPUT) $(DEBUGFLAGS) $(LIBS)

doc:    $(HEADER) spokenweb_doxygen_configuration
        doxygen spokenweb_doxygen_configuration 

r_data: GenerateData.R
        R --slave < GenerateData.R

style: $(SRC) $(HEADER)
        astyle --options=spokenweb_astyle_rules $(SRC) $(HEADER)

clean:
        rm -f *.o $(OUTPUT) *~ *.data parameters.txt metaFile.txt *.data

Use a document generator like doxygen. It forces you to write much cleaner documentation and more importantly cleaner interface. Trust me it will help if you had to reuse your code in future.
```
make doc
```
Use code beautifier like astyle that not only shields you against inelegant colleague/coder, but also personalizes the code if you like to do 'Code Reading' (Don't you clean gym equipment after workout, well, why not do the same with your code). Here is sample style rules that I love:
```
 
--style=java
--indent=spaces=2
--indent-classes
--indent-switches
--indent-preprocessor
--indent-col1-comments
--min-conditional-indent=0
--max-instatement-indent=80
--unpad-paren
--break-closing-brackets
--add-brackets
--keep-one-line-blocks
--keep-one-line-statements
--convert-tabs
--align-pointer=type
--align-reference=type
--lineend=linux
--suffix=none
```
If your company follows other style guidelines or if you don't want to change existing formatting, remove '--suffix=none' from the style rules and once you are done, you can restore the original unformatted files (*.orig).
```
make style
```
Familiarize yourself with program analyzers and debugging tools, and have scripts that automate them in your coding process:
- g++'s flags (See DEBUGFLAGS in my makefile)
- Static analysis tools like cppcheck (For more cases, I am satisfied with the above g++'s flags)
- Runtime memory analyzer tool like valgrind. (Please see below given Valgrind checklist, and also my previous blogpost).
- gdb: For stepping through the code for more comprehensive debugging
There are several paid tools that do much better job of analyzing your code that those mentioned above. There are
I like to follow standard directory structure:
./ Makefile and configure scripts
./src cc , h files (Use subdirectories and namespaces if necessary)
./bin build directory
./data data required for testing/running the code
./test test drivers
./doc documentation generated by doxygen

Maintain a list of code snippets (stored in Evernote or a personal notebook) or helper classes that you might have to use again. Note that the helper classes should have good interface and must be well documented (and robust). For example, I use GSL for writing sampling functions for bayesian programs, which has very ugly interface and requires some amount of book-keeping. So, I have coded a wrapper class that gives an R like interface which makes my code extremely readable, less error prone and I don't need to worry about any book-keeping or other numerical issues while calling them.

 
/// \defgroup StatDistribution R-like API for family of probability distributions
/// Naming convention:
/// I have followed the naming conventions of R programming language. 
/// Please see its documentation for further details
///
/// Here is a brief intro:
/// Every distribution that R handles has four functions. There is a root name, 
/// for example, the root name for the normal distribution is norm. 
/// This root is prefixed by one of the letters
///   - d for "density", the density function
///   - r for "random", a random variable having the specified distribution
/// Example: For the normal distribution, these functions are dnorm, and rnorm.
///
/// Important note: Since most bayesian calculation is done in log space, (almost) 
/// every density function is capable of outputing 'numerically robust' logarithmic value. 
/// Hence, use dnorm(x, mean, sd, true) in your code rather than log(dnorm(x, mean, sd))
///
/// Suported continuous distribution:
/// - Uniform (unif - r,d)
/// - Univariate Normal (norm - r, d); Truncated normal (tnorm - r,d);
/// - Multivariate Normal (mnorm - r, d, conditional_r, conditional_rt) (--> Only m = 2, 3 supported)
/// - Beta (beta - r,d)
/// - Inverse Gamma (invgamma - r,d)
///
/// Suported discrete distribution:
/// - Discrete Uniform (dunif - r,d)
/// - Dirichlet (dirichlet - r,d)
/// - Multinomial (multinom - r,d)
/// - Poisson (pois - r,d)
/// @{

/// @name Continuous Uniform Distribution
///@{
/// Returns uniform variable [min, max)
double runif(double min, double max);
double dunif(double x, double min, double max, bool returnLog = false);
///@}

/// @name Discrete Uniform Distribution
///@{
/// Returns uniform variable [min, max) --> i.e. [min, max-1]
int rdunif(int min, int max);
double ddunif(int x, int min, int max, bool returnLog = false);
///@}

/// @name Univariate Normal Distribution
///@{
double rnorm(double mean, double sd);
double dnorm(double x, double mean, double sd, bool returnLog = false);
///@}

/// @name Multinomial distribution
/// Both prob and retVal should be of length sizeOfProb
/// size, say N, specifying the total number of objects that are put into 
/// K (or sizeOfProb) boxes in the typical multinomial experiment.
/// If the array prob is not normalized then its entries will be treated as 
/// weights and normalized appropriately. Furthermore, this function also allows 
/// you to provide log probabilities (in which case, you need to set isProbInLogSpace to true)
/// Eg: double prob[3] = {0.1, 0.2, 0.7}; double retVal[3]; rmultinom(1, 3, prob, retVal, false);
///@{
void rmultinom(int size, int sizeOfProb, double* prob, unsigned int* retVal, bool isProbInLogSpace = false);
double dmultinom(int sizeOfProb, double* prob, unsigned int* x, bool isProbInLogSpace = false, bool returnLog = false);
///@}

So to sample N(10,2), instead of having code like:

 
gsl_rng* rng_obj = gsl_rng_alloc(gsl_rng_mt19937);
double sampledVal = gsl_ran_gaussian(rng_obj, 2) + 10;
gsl_rng_free(rng_obj);

I have to use following code (which if you have coded in R is more readable):

 
StatisticsHelper myStatHelper;
double sampledVal = myStatHelper.rnorm(10, 2);

Valgrind checklist:

First run valgrind's memcheck tool (valgrind --tool=memcheck program_name) and check:

The heap summary (only returns memory leaks, not memory corruption errors) Eg:
```
 
==19691== HEAP SUMMARY:
==19691==     in use at exit: 0 bytes in 0 blocks
==19691==   total heap usage: 12,126 allocs, 12,126 frees, 938,522 bytes allocated
==19691== 
==19691== All heap blocks were freed -- no leaks are possible
```
If number of allocs and the number of frees will differ in o/p, the try
valgrind --tool=memcheck --leak-check=yes --show-reachable=yes program_name

Steps to avoid memory leaks:
- If you are assigning pointers to other pointers, be very explicit as to who is responsible for the deletion of the memory.
- Delete every object created by new (especially in case of exceptions).
Intermediate warning/error messages irrespective of the heap summary. Eg:
```
 
==15633== Invalid write of size 4
==15633==    at 0x4163F3: LDAGibbsSampler::FillInSpeechToTextOutputs() (LDA.cpp:206)
==15633==    by 0x41565A: LDAGibbsSampler::LDAGibbsSampler(int, int, double, double, std::string, double, double, int) (LDA.cpp:28)
==15633==    by 0x402E26: main (main.cpp:34)
```
Note, sometime one error can propagate and throw error messages at different places, so don't panic.

The intermediate error messages can detect:
- Illegal read / Illegal write errors (like the message 'Invalid read of size 4' above): It can mean any of the memory corruptions given below.If the error message is not informative, run valgrind again with '--read-var-info=yes' flag.
  Common memory corruption bugs like these are:
  - Writing/Accessing out of bounds memory (either directly or by array oriented functions like strcpy)
  - Using an unallocated object
```
 
my_class* obj_ptr;
obj_ptr -> var1 = val; // or val = obj_ptr -> var1;
```
  - Using a freed object
  Note: Memcheck (tool of valgrind) does not perform bounds checking for stack or global arrays, so even if you don't get this error/warning message, it does not mean that there is no memory corruption errors.
- Use of uninitialised values (either on stack or heap) in user function: Message looks like 'Conditional jump or move depends on uninitialised value(s)'. To see information on the sources of uninitialised data in your program, use the '--track-origins=yes' option.
- Use of uninitialised values in system calls: Message looks like 'Syscall param write(buf) points to uninitialised byte(s)'.
- Illegal free/deletions: (Invalid free())
  - Calling free() (or delete) on the object that is already freed (or deleted).
  - Deleting object that is created on stack.
- Mismatched operators: (Mismatched free() / delete / delete [])
  - Calling free() on the object that is created by new operator.
  - Calling delete on the object that is created by malloc().
  - Calling delete[] on the object that is created by the new operator.
- Overlapping source and destination blocks: (Source and destination overlap in ...)
  - Look out functions like memcpy, strcpy, strncpy, strcat and strncat.

References:
- http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml
- http://www.yolinux.com/TUTORIALS/C++MemoryCorruptionAndMemoryLeaks.html
- http://www.cprogramming.com/tutorial/memory_debugging_parallel_inspector.html

How to analyze algorithms ?

2011-10-11T14:59:00.001-04:00

Important assumptions:

This process of analysis should be independent of programming language and machine architecture. So you can't just write your algorithm in C++ and compare it using running time of some other algorithm written in Java.
Also, since each algorithm can take as an input arbitrary data structure (eg: graph, array, binary object, tree, ...), there has to be some standard way to specify it. For sake of our analysis, we use input size (n) as the measure for our analysis. For eg: length of array, number of vertices or edges of the graph, number of nodes of a tree etc.

The detailed explanations of these two points is given in Introduction to Algorithms by Cormen, Leiserson, Rivest, .. (CLR)

Setup:

Input of size n ==> Algorithm that takes T(n) steps ==> some output

The number of steps in the algorithm often depends on factors other than the input size. For eg: the number of steps for quicksort for the input [1, 2, 3, 4, 5] is different than as compared to the input [5, 4, 3, 2, 1]; even though both have same input size (and in this case same elements).
Hence, we will try to find 3 functions (upper bound, lower bound and Theta bound) that can capture the effects of these factors:$$ g_1(n), g_2(n) \text{ and } g_3(n) \text{ such that } $$ $$ T(n) \in O(g_1(n)), T(n) \in \Omega(g_2(n)) \text{ and } T(n) \in \Theta(g_3(n))$$Many authors also write above equations as:$$ T(n) = O(g_1(n)), T(n) = \Omega(g_2(n)) \text{ and } T(n) = \Theta(g_3(n))$$

Big-O notations:

Now, let's understand definition of above notations:\begin{align}\text{To prove that } & g_1(n) \text{ is upper bound of T(n), i.e.} T(n) \in O(g_1(n)) \\\text{ find two constants } & c, n_0 \text{ such that } \\& \forall n \geq n_0, T(n) \leq c g_1(n)\end{align}For lower bound, change ≤ sign to ≥ sign and for theta bound find both lower and upper bound:$$ T(n) \in \Theta(g_3(n)) \text{ iff } T(n) \in O(g_3(n)) \text{ and } T(n) \in \Omega(g_3(n))$$
To understand these in more details, I suggest you solve problems from CLR chapter 3. Here are some example you can start with:\begin{align}2n^2 \in O(n^3) & \text{ with } c=1 \text{ and } n_0 = 2 \\\sqrt{n} \in \Omega(lg n) & \text{ with } c=1 \text{ and } n_0 = 16 \\\frac{n^2}{2} - 2n \in \Theta(n^2) & \text{ with } c_1=\frac{1}{4}, c_2=\frac{1}{2} \text{ and } n_0 = 8 \\\end{align}(Note: theoretically very large functions such as infinity^n or n^infinity can always be lower bounds. So, it is necessary to supply as tight bound as possible for any given algorithm. Mathematically, the notations for tight upper bound is small o and for tight lower bound is small omega, but we will ignore them for sake of this discussion)

Common measures for algorithms:

Above three notations are often replaced by the terms 'worst case', 'best case' and 'average case' complexity. But, more precise definitions are as follows:\begin{align}\text{Worst case}& T(n) = max \{ T(x) | \text{ x is an instance of size n} \} \\\text{Best case}& T(n) = min \{ T(x) | \text{x is an instance of size n} \} \\\text{Average case}& T(n) = \sum_{\text{input }x} Prob(x) T(x)\end{align}This means, to find average case complexity of algorithm, you need to find probability of a given input and use it to find expectation of T(n).

Pseudo code to Big-O:

Now, let's address the key question: given a pseudo code, how do we find its lower bound (or upper bound or ...). Here is one possible way to find those bounds:

First, express the algorithm in recursive form
Determine appropriate metric for input size 'n'
Then, find recurrence relation for the algorithm
Solve the recurrence relation using either Substitution method, recursion tree method or the master theorem

For example, the recurrence relations for popular algorithms are:\begin{align}\text{Binary search: } & T(n) & = T(\frac{n}{2}) + O(1) \\\text{Sequential search: } & T(n) & = T(n-1) + O(1) \\\text{Tree traversal: } & T(n) & = 2T(\frac{n}{2}) + O(1) \\\text{Selection sort: } & T(n) & = T(n-1) + O(n) \\\text{Merge sort: } & T(n) & = 2T(\frac{n}{2}) + O(n)\end{align}Try writing the pseudo code for any of the above algorithm and verify the recurrence relations.

Master theorem:

Master theorem can only solve the recurrence relation of the form: T(n) = a T(n/b) + f(n). Here is my modus operandi for master theorem:\begin{align}\text{If } f(n)=n^{log_{b}a}lg^{k+1}n, & \text{ then } T(n) = \Theta(n^{log_{b}a} lg^{k+1}n) \\\text{Else if } n^{log_{b}a} \text{ is polynomially greater than } f(n), & \text{ then } T(n) = \Theta(n^{log_{b}a}) \\\text{Else if } f(n) \text{ is polynomially greater than } n^{log_{b}a}, & \text{ then } T(n) = \Theta(f(n)) \\\text{Else use Substitution method}&\end{align}
Here are solutions to two important recurrence relations, that cannot be solved using Master theorem:\begin{align}\text{Recurrence relation} & & \text{Complexity} \\T(n) = T(n-1) + b n^k & => & O(n^{k+1})\\T(n) = cT(n-1) + b n^k & => & O(c^n)\end{align}
For recurrence relation of other forms, refer to CLR for substitution and recursion tree method.
(In short, for substitution method, you guess the solution and use induction to find the constants and to prove that the guessed solution is correct.
Recursion tree method are often used to find the guess for the substitution method)

Some useful approximations:

For non-negative real b,c,d:
\begin{align}\text{Polynomial growth rate:}&\sum_{i=1}^n i^c &= \Theta(n^{c+1}) \\\text{Logarithmic growth rate:}&\sum_{i=1}^n \dfrac{1}{i} &= \Theta(log(n)) \\\text{Exponential growth rate:}&\sum_{i=1}^n c^i &= \Theta(c^n) \\\text{n-Log(n) growth rate:}&\sum_{i=1}^n log(i)^c &= \Theta(n log(n)^c) \\\text{Combination of above:}&\sum_{i=1}^n log(i)^c i^{d} &= \Theta(n^{d+1} log(n)^c) \\&\sum_{i=1}^n log(i)^c i^d b^{i} &= \Theta(n^{d+1} log(n)^c b^{n}) \\\text{Stirling's approximation:}&n! &= \sqrt(2 \pi n) (\frac{n}{e})^n (1 + \Theta(\frac{1}{n}))\end{align}

Presentation on Online Aggregation for Large MapReduce Jobs

2011-09-29T23:26:00.003-04:00

This post has two purposes:
1. Give information about my Comp 600 presentation at Rice University
2. Enumerate the lesson's learnt while preparing and giving the presentation.

(If the above videos does not work, click on: Dailymotion or Vimeo)

Also, if you have time, go through my slides or better still read my paper :)
- Slides
- Paper

FAQs during the presentation at VLDB:

1. What if the blocks are equally sized and spread across uniformly ?
- We used exactly that configuration. The input blocks of wikipedia logs are approximately of same size and HDFS does good job of spreading the data across uniformly. Still, we found biased results in the beginning.

2. Does your system replace general database ?
- Nope. As of now, it only performs single table aggregation with group-by. For a general online database, see DBO paper by our group.

3. Will you release your code ?
- Yes, we intend to release our code as open-source. For current version, see http://code.google.com/p/hyracks-online-aggregation/

4. Who do you see as potential user of the system ?
- Any company that has massive data stored in HDFS (logically as single table) and want to perform aggregation in online fashion or only till certain accuracy. Note, that the table containing the data need not be pre-randomized.

5. What does user of the system needs to know ?
- Just how to write and run a hadoop job ... All he/she has to do is write a hadoop mapper and set appropriate parameters in job configuration. For details see appendix of our paper.

6. You didn't explain too much statistics in the talk ... I want to know more
- Yes, you are absolutely right. Infact, that was intentional :) ... If I have to give one-line summary of statistics here is it: Sample from a Multi-variate normal on value, processing time and scheduling time (which have correlation factor associated with between each of them) which takes in account the 'lower bound' information of processing time of the blocks that are currently been processed ... rather than simply sampling from the distribution over data.

7. You don't talk about performance ... Isn't randomized scheduling policy bad for performance ?
- We didnt talk about the performance, mainly because we didnot provide any comparative study for performance in our paper. Note that, our policy is not same as a strict randomized policy. We expect the master to maintain a randomize queue and start the timer when a worker asks for the block. If for some reason (say locality), worker doesnot want that block or master has some internal (locality-based) scheduling algorithm, he can leave the timer ON and go for next block in the randomized queue. This is necessary machinery for sampling theory. This will yield performance that is similar to locality-based scheduling. However, in our current implementation, we have not used this mechanism. We intend to do the performance study in our future work.

Presentation tips:

Clearly my presentation has lot of room for improvement, for example: need to talk slower, more uniform layout of the slides, more interaction with audience etc. However, I have learnt a great deal while preparing and giving this presentation. I will summarize few points that I (and probably lot of graduate students) need to be careful about. For more detailed analysis of these points, I suggest you read Presentation Zen, Slide:ology and When the scientist present.

Step 1: Planning your presentation
1. Create a relaxing environment
- Go to a library, coffee place, garden (place where no one will disturb you)
- Take time to relax and forget about daily chores.
- Don't bring your laptop. In this step, you will create rough sketch of the presentation on paper (not slideware)
- Lot of the time, changing locations helps you to be more creative.

2. Make sure you understand the big picture of your presentation.
Can you find 30-45 seconds answer to following questions:
- What is the single most important "key" point that I want my audience to remember
- Why should that point matter to the audience

Also, make sure that your presentation title has keywords that highlights the big picture (as many people (if not all) will come to your talk either reading just the title (and abstract) or your name). This does not mean the title has to be too long; in fact shorter and thought-provoking title are preferred.

3. Now, create a sketch of the presentation. This involves enumerating key ideas you will be presenting and also organising/ordering them. You can use either or all of the following tools:
- Mindmap on whiteboard or paper
- Post-it (use sharpie to make sure you don't misuse post-it)
- Brainstorm the list of ideas + Grouping them
- Sketching or drawing
Nancy Duarte says most effective presentations involves telling a story that audience can connect and relate to, rather than just present the information/data. Also, best professors are good story-tellers. They just don't go through the material in the book, but put their own personality, character and experience into the material in form of a narrative, which is illuminating, engaging and memorable.

The most useful point I have learnt from Presentation Zen is that the presentation consists of three parts:
- Slides the audience will see (which you will create in Step 2)

- Notes only you will see (which you have created in this Step)

- Handouts that audience can take away (so that they don't have to jot down key definition or formula). This in worst case could simply be a copy of your paper.

This essentially means that the slides are not telepromptor, that you read aloud throughout your presentation.

Step 2: Design the slides
To succeed as a presenter, you need to think as a designer (from slide:logy).

1. First few slides are very very important !!!
- I like to give use them to tell the audience the big picture of the presentation.
- It is also necessary that this has to be catch their attention, as we all know the attention-span of audience decreases exponentially after first few minutes. Don't use the first few minutes reading through the 'Outline' slide.
- Use following principle: Tell them what you are going to present, present it, then tell them again what you presented :)

2. Slides should be as simple as possible.
- Don't use fancy, distracting background images. I prefer sticking to simple white background slide.
- Good design has plenty of empty spaces.
- Avoid typical bullet point presentations. They are boring and they do more harm than good.
- Don't use 3D figures when 2D figures can suffice
- Never ever clutter the slides with useless data, words, figures, images, etc

3. 1 message per slide ... not more !!
- Do you understand that message ?
- Does your slide reflect that message ? You don't have to write down the message into your slide
- Can I make this slide simpler and still make sure that the message is conveyed. In most cases, this is done by replace bunch of text either with an appropriate image or animation.
- A lot of the time, entire message can be conveyed just by a quote from a reliable or important person.

4. Try to find a good figure or animation to convey a complex idea, algorithm or system. Here are some tips on creating animation:
- Using same slide background, create many slides (by copy operation). Change only 1 detail per slide. When you keep moving from one slide to next, it would give an effect of animation, something like flip-book. However, this process creates a lot of slides (which is problematic in many cases). So, if you want to fit everything into 1 slide, you can create a flash object, gif file or avi file and embed it into the slide. Most people use Adobe tools to create professional looking flash files, but here is poor man's solution:
- Use flip-book style slide transition technique and desktop recorder (eg: recordmydesktop) to create a movie. It usually creates movie in ogv file format.
- Also, lot of time you need to create animation using statistical distribution. In that case, use animation library of R and create ogv movie using desktop recorder. (This library also allows you store the animation in gif, but I am having some problems with it).

# R code for animation
library(animation)
ani.options(interval = 1, nmax = 20)
sd1 <- 41
for (i in 1:ani.options("nmax")) {
    x=seq(900, 1100,length=200)
    y=dnorm(x,mean=1000,sd=sd1)
    plot(x,y,type="l",lwd=2,col="red")
    ani.pause() ## pause for a while ('interval')
    sd1 <- sd1 - 2
}

a. Convert OGV to AVI:
mencoder input.ogv -ovc xvid -oac mp3lame -xvidencopts pass=1 -speed 0.5 -o output.avi
b. Convert OGV to GIF (or swf):
ffmpeg -i input.ogv -loop_output 0 -pix_fmt rgb24 -r 10 -s 320x240 output.gif
"-loop_output 0" means loop forever.

5. Is the content tailored to meet audience' expectation:
- Employers/future collaborators will try to evaluate you rather than the topic.
- Students (undergrad/first year grads/ ..) or people from different area want to understand the problem and intuition behind the solution. Hence, they are more interested in motivation section.
- Co-author will look for recognition.
- Sponsor will look for acknowledgement.
- People who work in same area will try to see if how your system/solution compares to theirs (i.e. related work) or may be are there to look for a new problem (i.e. your future work).

6. Other design tips:
- Use contrast (using font type, font color, font size, shape, color, images) accentuate the difference. (If it is different, make it very different - Garr Reynolds). It helps audience to identify the message of the slide quickly.
- Repetition: Use same image (or anchor) to represent the same concept throughout the presentation.
- Alignment: Use grids, invisible lines. Audience needs to know the order in which to process the information.
- Proximity
- Hierarchy, Unity
- Use high quality graphics. There are websites that create and sell them like www.istockphoto.com; or even give them for free like http://www.flickr.com/creativecommons, etc.
- Nothing distracts the audience more than a cluttered slide.
- Make sure your font size is greater than 24 point (so that audience can read it from the projector)
- Use comics ... it not only conveys the information efficiently, but also makes the presentation playful. Though many of my colleagues disagree with this, I believe most audience wants to have fun even if it is a research presentation .. so lighten the mood, be creative and "artsy" with your slides :)

"The more strikingly visual your presentation is, the more people will remember it. And more importantly they will remember you" - Paul Arden.
Here are some slides that are well designed:
http://www.slideshare.net/jbrenman
http://www.slideshare.net/chrislandry
http://www.slideshare.net/gkawasaki
http://www.slideshare.net/garr

Step 3: Rehearse and re-rehearse
- Use both notes and slides.
- Rehearse until you can remember and are comfortable with them. Imagine the worst case scenario that you lost your laptop, slides and all your notes ... and you have to give your presentation !!! ... If you can do that, you are ready :)
- Here you also do the job of editing, if you feel certain slides are just fillers and can be removed ... be brutal and delete them.
- Listen to http://www.ted.com/talks for motivation on how to present.

Step 4: Delivery
- Go to the presentation room 15 min before the scheduled time and make sure your slides are compatible, projector works, ... Also, bring a bottle of water, just in case.
- Leave the lights on and face the audience. People are there to see you, not read through the slides. Use wireless presenter so that you don't need to hide behind the podium/monitor.
- Slides are not telepromptor ... so don't keep staring at the monitor ... connect with the audience.

Remember these two quotes:
- Every presentation has potential to be great; every presentation is high stakes; and every audience deserves the absolute best - Nancy Duarte.
- You are presenting yourself rather than the topic. So, negative impact of poor presentation far exceeds failure of getting your point across ... Jean-Luc Lebrun

Thinking in Probability

2011-08-15T01:18:00.002-04:00

This blogpost is based on a lecture I gave at Jacob Sir's classes yesterday. The intent of my lecture was to urge student to ask questions and read "stuff" beyond the textbook. To get the interest of the students, I started with 2 examples, which explained the dependent and independent events and also the need to stick to mathematical rigor rather than intuition.

First example was classic Monte Hall problem, which suprisingly none of my students had heard about. This was fortunate because this meant everyone would have to think about it on their own, rather than provide a prepared answer (thought-through by someone else). So, here is the problem:

There are three doors D1, D2 and D3; behind two of them there is a goat and behind the other is a car. The objective of the game is to win a car. So, you have to guess which door to chose ... Does it make difference whether you chose D1, D2 or D3 ? ... The consensus was NO, because the Prob(win)=0.33 for each of the door. To make the problem interesting the game show host (who know which door has car and which doors has goats), opens one of the remaining door that has goat. He now asks you based on this information whether you would like to switch your earlier choice. For example, earlier you chose D1 and the game show host opens D2 and shows that it has goat. Now you can either stick to D1 or switch to D3. The real question we are interested in is:

Does switching the door make more sense or staying with the same door ? or It does not matter whether you chose D1 or D3.

Interesting but incorrect answers:

1. It does not matter whether you chose D1 or D3, because Prob(win) for each door is now 0.5

2. Staying with the door makes more sense, since we have increased the Prob(win) from 0.3 to 0.5

3. We really don't have plausible reason to switch, hence stay with the same door; especially since the game show host may want to trick us.

The correct answer is switching doubles the Prob(win), hence it makes more sense.

Consider the case where you don't switch:

Prob(win) = Prob(D1 = car) = 0.33 (The probability does not change because of an event outside its scope)

Now consider the case where you switch:

Prob(win) = Prob(D1 = goat) = 0.66

The other way to understand the problem is by enumerating

D1 : C G G

D2 : G C G

D3 : G G C

Swap: G C C => Prob(car) = 0.66

Stay: C G G => Prob(car) = 0.33

For people who chose the third incorrect answer, I asked them not to use information not provided in the problem and show as much restrain as possible to use intuition over logic. Deductive thinking says go from Step 2 to Step 3 only if there is a valid theorem, axiom, or logical reason (not intuition).

Let's move to the second problem:

Say I have a fair coin. I toss the coin four times and I get {Head, Head, Head, Head}, what will you bet on ?

Some students earlier based their answer on gambler's fallacy, stating that Tail is more likely since they have seen four consecutive heads. I then asked them to sit in circle and discuss with each other and then answer my question again. Through this exercise, I wanted them to learn the idea of collaboration to get an answer. And vola ... they came with the correct answer ... It doesnot matter whether we bet on head or tail, since the events are INDEPENDENT and hence each outcome is equally likely => Prob(T5 | H1, H2, H3, H4) = Prob(T5) = 0.5

Finally, I gave them two different explanation of probability:

1. Deterministic view for probability (explained in my earlier blogpost)

2. Measure theoretic approach

After explaining the deterministic view, I emphasized the importance of probability while solving real life problem. For example, in coin tossing experiment, you are able to make some rational predictions, even though you don't know (hidden) parameters like initial angle of coin, weight and density of coin, shape of the coin, velocity of the coin, resistance due to air, characteristics of surface where it lands, etc ... Similarly, you can build simpler probabilistic model for complex scenarios like weather forecasting, stock prediction, traffic congestion, ...

Reference:

1. http://niketanblog.blogspot.com/2009/11/god-does-not-play-dice.html

2. http://en.wikipedia.org/wiki/Monty_Hall_problem

3. http://en.wikipedia.org/wiki/Gambler's_fallacy

4. http://en.wikipedia.org/wiki/Measure_(mathematics)

Nice post about Sachin Tendular after India-SA match

2011-03-15T17:31:00.003-04:00

Remember when you failed an examination. How many people recall that, your class, friends, relatives? You failed to make it to the IITs or IIMs. Who remembers. How many times have you had the feeling of being the best in your class, school , university, state….., you failed to get a visa stamped this quarter…, you missed a promotion this year…, how did it feel when you dad told you in your early twenties that you are good for nothing…..and now your boss tell you the same...

You keep introspecting and go into a shell when people most of whom don’t matter a dime in your life criticize you, back bite you, make fun of you. You are left sad and shattered and you cry when your own kin scoffs at you. You say I am feeling low today. It takes a lot from us to come out of these everyday situations and move on. A lot??? really?

Now here’s a man standing on the third man boundary in the last over of a world cup match. The bowler just has to bowl sensibly to win this game. What the man at the boundary sees is 4 rank bad bowls bowled without any sense of focus, planning or regret. India loses, yet again in those circumstances when he has done just about everything right.
He does not cry. Does not show any emotion. Just keeps his head down and leaves the field. He has seen these failures for 22 years now. And not just his class, relatives, friends but the whole world has seen these failures. We are too immature to even imagine what goes on in that mind and heart of his. That’s why I would never want to be Sachin.

True, he has single handedly lifted to moods of this entire nation umpteen number of times. He has been an inspiration to rise above our mediocrity. Nobody who has ever lifted the willow even comes close to this man’s genius. His dedication and metal strength is unparallel. This is specially for those people who would have made fun of him again last night when India lost. They are people who are mediocre in their own lives. Who just scoff at others to create cheap fun. Who have lived in a small hole throughout their lives and thought they have seen the oceans.

Think about the man himself. He is 37 years of age. He has been playing almost non stop for 22 years. The way he was running and diving around the field last night would have put 22 year olds to shame. The way he played the best opening quickies in the world was breathtaking. He just keeps getting better which is by the way humanly impossible. Its not for nothing that people call him GOD.
But still I don’t want to be in those shoes. We struggle in keeping our monotonous lives straight, lives which affect a limited number of people. Imagine what would be the magnitude of the inner struggle for him, pain both mental and physical, tears that have frozen with time, knees and ankles and every other joint in the body that is either bandaged or needs to be attended to every night, eyes that don’t sleep before a big game, bats that have scored 99 international tons and still see expectations from a billion people.

And he just converts those expectations into reality. We watch in awe, feel privileged.
Well I think its time that his team realizes that enough is enough. They have an obligation, not towards their country alone but towards sachin. They need to win this one for him. Stay assured that he himself will still deliver and leave no stone unturned to make sure India wins this cup.
This is not just a game, and he is not just a sportsman. Its much more than this. Words fail here.....

-- Anonymous

(This post is not written by Harsha Bhogle even though the source page said it was)

Setting and running Hadoop 0.20.2

2011-02-24T16:37:00.001-05:00

Step 1: Download and extract hadoop code
wget http://mirror.cloudera.com/apache/hadoop/core/hadoop-0.20.2/hadoop-0.20.2.tar.gz
Extract the files and go into that directory

Step 2: Configure Hadoop
vim ~/.bash_profile
export JAVA_HOME=/usr/local/java/vms/java
export HADOOP_HOME=/home/oa/hadoop-asterix/hadoop-0.20.2

vim ${HADOOP_HOME}/conf/masters
asterix-master

vim ${HADOOP_HOME}/conf/slaves
asterix-001
asterix-002
asterix-003

vim ${HADOOP_HOME}/conf/core-site.xml
<property>
<name>fs.default.name</name>
<value>hdfs://10.122.198.195:54310</value>
<description>The name of the default file system. A URI whose
scheme and authority determine the FileSystem implementation. The
uri's scheme determines the config property (fs.SCHEME.impl) naming
the FileSystem implementation class. The uri's authority is used to
determine the host, port, etc. for a filesystem.</description>
</property>

vim ${HADOOP_HOME}/conf/mapred-site.xml
<property>
<name>mapred.job.tracker</name>
<value>10.122.198.195:54311</value>
<description>The host and port that the MapReduce job tracker runs
at. If "local", then jobs are run in-process as a single map
and reduce task.
</description>
</property>

vim ${HADOOP_HOME}/conf/hdfs-site.xml
<property>
<name>dfs.replication</name>
<value>2</value>
<description>Default block replication.
The actual number of replications can be specified when the file is created.
The default is used if replication is not specified in create time.
</description>
</property>
<property>
<name>dfs.name.dir</name>
<value>/mnt/hdfs/name_dir/</value>
</property>
<property>
<name>dfs.data.dir</name>
<value>/mnt/hdfs/data_dir/</value>
</property>
<property>
<name>dfs.datanode.address</name>
<value>0.0.0.0:54325</value>
</property>
<property>
<name>dfs.datanode.http.address</name>
<value>0.0.0.0:54326</value>
</property>

vim ${HADOOP_HOME}/conf/hadoop-env.sh
export JAVA_HOME=/usr/local/java/vms/java

Make sure the name and data directory are properly setup using following script. This also confirms that you can do passwordless ssh from master to slave machines.
vim ${HADOOP_HOME}/commands.sh
cd /mnt
sudo mkdir hdfs
cd hdfs/
sudo mkdir name_dir
sudo mkdir data_dir
sudo chmod 777 -R /mnt/hdfs

# Sync this file
parallel-rsync -p 6 -r -h ${HADOOP_HOME}/conf/slaves ${HADOOP_HOME} ${HADOOP_HOME}

Then, run the above command.sh for every slave
user_name="ubuntu"
command="sh ${HADOOP_HOME}/commands.sh"
for slaves_ip in $(cat ${HADOOP_HOME}/conf/slaves)
do
ssh ${user_name}@${slaves_ip} ${command}
done

Step 3: Compile hadoop and sync slaves
# Compile source code
${ANT_HOME}/bin/ant
${ANT_HOME}/bin/ant jar
${ANT_HOME}/bin/ant examples

# Sync slaves (see EC2 point 3 for installing parallel ssh)
parallel-rsync -p 6 -r -h ${HADOOP_HOME}/conf/slaves ${HADOOP_HOME} ${HADOOP_HOME}

Step 4: Run hadoop
${HADOOP_HOME}/bin/hadoop namenode -format
${HADOOP_HOME}/bin/stop-all.sh
${HADOOP_HOME}/bin/start-all.sh

Check logs/ datanode namenode. Also see if the nodes are up, by using (any normal browser or) links http://master-ip:50070
If you get "incompatible namespace error" in datanodes log, let me try deleting hdfs dir and restarting hdfs

Step 4: Loading the HDFS
If you are loading from:
1. Local filesystem of master, use: either copyFromLocal or put
bin/hadoop dfs -copyFromLocal /mnt/wikipedia_input/wikistats/pagecounts/pagecounts* wikipedia_input

2. Some other hdfs, use put

3. Files on some other machine accessible via scp
# Configure following variables. Keep space between parenthesis of array and each item (no comma).
# If this script gives error like '4: Syntax error: "(" unexpected', try bash <script-name>
# If that gives permission denied error, put name of directories instead of ${directories1[@]}
user_name="ubuntu"
machine_name="my_machine_name_or_ip"
file_prefix="pagecounts*"
hdfs_dir="wikipedia_input"
directories1=( "/mnt/data/sdb/space/oa/wikidata/dammit.lt/wikistats/archive/2010/09" "/mnt/data/sdc/space/oa/wikidata/dammit.lt/wikistats/archive/2010/10" "/mnt/data/sdd/space/oa/wikidata/dammit.lt/wikistats/archive/2010/11" )
for dir1 in ${directories1[@]}
do
echo "--------------------------------------------"
cmd="ssh ${user_name}@${machine_name} 'ls ${dir1}/$file_prefix'"
echo "Reading files using: " $cmd
for file1 in `eval $cmd`
do
file_name1=${file1##*/}
echo -n $file_name1 " "
scp oa@asterix-001:$file1 .
bin/hadoop dfs -copyFromLocal $file_name1 $hdfs_dir
rm $file_name1
done
done

Step 5: Run your mapreduce program
${HADOOP_HOME}/bin/hadoop jar ${HADOOP_HOME}/build/hadoop-hop-0.2-examples.jar wordcount tpch_input tpch_output

Some tips for amazon EC2:
1. Lot of times due to resource allocation policies, EC2 shutdowns your virtual machine (hence the assigned network) and master/slaves/namenodes/datanodes goes into fault tolerance mode and restart the jobs. You can set infinite time for heartbeat to tackle this error (This works because EC2 restarts you virtual machine after some time and there is no "real" failure, just temporary lags) by setting following into ${HADOOP_HOME}/conf/hdfs-site.xml
<property>
<name>dfs.heartbeat.interval</name>
<value>6000</value>
<description>Determines datanode heartbeat interval in seconds.</description>
</property>
<property>
<name>dfs.heartbeat.recheck.interval</name>
<value>6000</value>
<description>Determines datanode heartbeat interval in seconds.</description>
</property>
<property>
<name>heartbeat.recheck.interval</name>
<value>6000</value>
<description>If dfs... doesnot work</description>
</property>
<property>
<name>dfs.socket.timeout</name>
<value>180000</value>
<description>dfs socket timeout</description>
</property>

2. Login into EC2 machine:
EC2_KEYPAIR_DIR="/home/np6/EC2"
echo "\nEnter Public DNS of Master"
read AMAZON_PUBLIC_DNS
echo "If this doesnot work try, (exec ssh-agent bash) and then this command again"
ssh-agent
ssh-add ${EC2_KEYPAIR_DIR}/ec2-keypair.pem
ssh ubuntu@$AMAZON_PUBLIC_DNS

3. Setting up java and other programs on slaves from master
# First install parallel ssh
user_name="ubuntu"
command="sudo apt-get install pssh"
for slaves_ip in $(cat ${HADOOP_HOME}/conf/slaves)
do
ssh ${user_name}@${slaves_ip} ${command}
done

# Then install java (if you dont prefer openjdk)
vim ${HADOOP_HOME}/commands.sh
sudo add-apt-repository "deb http://archive.canonical.com/ lucid partner"
sudo apt-get update
sudo apt-get install sun-java6-jdk
sudo update-java-alternatives -s java-6-sun
echo "export JAVA_HOME=/usr/lib/jvm/java-6-sun" >> ~/.bashrc
echo "export HADOOP_HOME=/home/ubuntu/hadoop" >> ~/.bashrc
source ~/.bashrc
echo "Check if the version of java is correct:"
java -version

# Sync this file
parallel-rsync -p 6 -r -h ${HADOOP_HOME}/conf/slaves ${HADOOP_HOME} ${HADOOP_HOME}

Then, run the above command.sh for every slave
user_name="ubuntu"
command="sh ${HADOOP_HOME}/commands.sh"
for slaves_ip in $(cat ${HADOOP_HOME}/conf/slaves)
do
ssh ${user_name}@${slaves_ip} ${command}
done

4. Setting up hadoop master and slaves for lazy person (I would recommend you follow above steps instead)
cd ${HADOOP_HOME}/conf
echo "\nEnter Public DNS of Master"
read AMAZON_PUBLIC_DNS
sed -e "s/<name>mapred.job.tracker<\/name> <value>[-[:graph:]./]\{1,\}<\/value>/<name>mapred.job.tracker<\/name> <value>${AMAZON_PUBLIC_DNS}<\/value>/" hadoop-site.xml > a1.txt
sed -e "s/<name>fs.default.name<\/name> <value>[-[:graph:]./]\{1,\}<\/value>/<name>fs.default.name<\/name> <value>hdfs:\/\/${AMAZON_PUBLIC_DNS}:9001<\/value>/" a1.txt > hadoop-site.xml
echo ${AMAZON_PUBLIC_DNS} > masters
echo "\nEnter Slave string seperated with space (eg: domU-12-31-39-09-A0-84.compute-1.internal domU-12-31-39-0F-7E-61.compute-1.internal)"
read SLAVE_STR
echo $SLAVE_STR | sed -e "s/ /\n/" > slaves

Some other neat tricks:
1. Replace default java temp directory:
export JAVA_OPTS="-Djava.io.tmpdir=/mnt/java_tmp"

2. Setting number of open file limit to 99999
sudo vi /etc/security/limits.conf
ubuntu soft nofile 99999
ubuntu hard nofile 99999
* soft nofile 99999
* hard nofile 99999
sudo sysctl -p
ulimit -Hn

3. Checking the machines on the network
cat /etc/hosts

or naming machines as masters and slaves: vim /etc/hosts
10.1.0.1 asterix-master
127.0.0.1 localhost
10.0.0.1 asterix-001
10.0.0.2 asterix-002

Checking machines ip address
/sbin/ifconfig

4. Configuring password-less ssh of master to slaves
slave_user_name="ubuntu"
for slaves_ip in $(cat ${HADOOP_HOME}/conf/slaves)
do
ssh-copy-id -i $HOME/.ssh/id_rsa.pub ${slave_user_name}@${slaves_ip}
done

For more detailed step by step example, see
http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-multi-node-cluster/

Life's wonderful and unexpected moments (in no particular order)

2011-01-29T00:18:00.001-05:00

1. Life changing speech from Dad or anyone you respect.
2. Laughing so hard your face hurts.
3. Helping someone when they need you the most.
4. Falling in love.
5. Hearing your favorite song on radio while driving and singing it unmelodiously.
6. Lying in bed listening to the rain outside, sometimes even waking up to see it with hot cup of coffee.
7. Mom's hot tea, birda, chicken, ... well almost anything she makes.
8. A good conversation.
9. Watching sunset/sunrise on the beach.
10. Laughing at yourself.
11. Laughing for absolutely no reason at all.
12. Laughing at an inside joke.
13. Being sincerely happy for someone.
14. Midnight phone calls that last for hours.
15. Having someone tell you that you're handsome/sexy/intelligent.
16. Accidentally overhearing someone say something nice about you.
17. Waking up and realizing you still have a few hours left to sleep.
18. Your first kiss.
19. Making new friends or spending time with old ones.
20. Playing with a new puppy.
21. Acting like teens once in a while.
22. Having someone play with your hair.
23. Having a wonderful dream.
24. Road trips with friends.
25. Nice swedish massage.
26. Watching a really good movie cuddled up on a couch.
27. Going to a really good concert.
28. Going to a (football/cricket) game and shouting/dancing/cheering the whole time.
29. Getting butterflies in your stomach every time you see that one person.
30. Making eye contact with a cute stranger.
31. Winning a really competitive game.
32. Running into an old friend and realizing that some things (good or bad) never change.
33. A long distance phone call.
34. Taking a drive on a pretty road.
35. Feeling that you get just before you think you are going to get into trouble and especially the one after you escaped it narrowly.
36. Playing "pretend games" with kids.
37. Visiting a temple/church/mosque or any place of worship.
38. Hugging the person you love.
39. Getting a creative idea which keeps you awake all night.
40. Boating/Kayaking/Canoeing
41. Camping/Trekking in nature park/beach.
42. Having sex.
43. Laying on grass and watching sky through leaves.
44. Laying on beach and trying to count the stars.
45. Watersports: Para-sailing, snorkelling, jet-skiing, scuba-diving.
46. Swimming in the sea or lake (especially if you are not a good swimmer).
47. Browsing through books in library or bookstores especially the fields other than your research/work.
48. Reading a thought-provoking quote/paragraph.
49. Learning and appreciating a new word.
50. Learning a new language.
51. Trying something for the first time.
52. Going through the pain barrier in the gym.
53. A hot shower.
54. Trying new food/restaurants.
55. Travelling to new places.
56. Getting drunk or handling a drunk friend.
57. Donating your blood/time/food/money/organ.
58. Pursue any one topic till you attain excellence in it.
59. Doing something against rationality and totally from the guts, especially people around don't believe in you.
60. Teach a child something new.
61. Forgiving someone.
62. Buying something you always wanted for several years.
63. Dancing senselessly in a party/marriage/procession.
64. Realizing you are being loved and respected by few very important people in your life.
65. Jogging outdoors while listening to your favorite music in a nice weather.
66. Playing with colors during Holi.
67. Be a part of human pyramid during Dahi-Handi.
68. Burning fire-crackers during Diwali.
69. Sitting/Standing by the door in the train.
70. Riding a horse.
71. Learning to play a musical instruments.
72. Being thanked for a nice gesture.
73. Being heartbroken.
74. Running through sprinklers or walking in the rain.
75. Playing with the snow.
76. Feeling of calm in solitude or while meditating.
77. Blood-rush to the brain while doing yoga.
78. Dressing funny for a costume party.
79. Feeling of levitation while jumping or catching a frishbee.
80. Take-off and landing of an airplane.
81. Sitting in the cockpit of Boeing 777.
82. Buying your first car/house.
83. Sailing on a yatch.
84. Being married to an amazing person.
85. Attending a major sporting event: the World Cup (Cricket/Soccer), Super Bowl, the Olympics, the U.S. Open.
86. Throwing a huge party and inviting every one of your friends.
87. Going to Disneyland/Seaworld and other them parks.
88. Skydiving/Bungee jumping.
89. Having your portrait/caricature painted.
90. Watching the launch of the space shuttle.
91. Spending a whole day eating junk food without feeling guilty.
92. Performing in front of large crowd.
93. Telling someone the story of your life, sparing no details.
94. Rollerblading/Skating/Ice-skating/Paintball/shooting-range/go-karting
95. Fishing in the sea.
96. Being someone's mentor.
97. Shower in a waterfall.
98. Painting the walls of your own house.
99. Being proud of someone else's achievement.
100. Getting a lapdance from the cutest girl you have seen.
101. Having an uncontrollable giggling fit at the worst possible moment.

Video on remembering periodic table

2010-12-16T15:39:00.002-05:00

The intent of above video is to demonstrate the power of mnemonics.

For more details: see http://niketanblog.blogspot.com/2006/07/remembering-periodic-table.html

Moshe Vardi's talk on P v/s NP

2010-12-07T18:53:00.001-05:00

Just attended a very interesting talk by Moshe Vardi on P v/s NP. Thought of summarizing it:
- He introduced the concept P (solvable in polynomial time) v/s NP (verifiable in polynomial time) and then compared them to "discovering v/s checking" a proof and which is easier. Say for some reason, P = NP, it would be as easy to discover the proof for a given problem than to read/check the proof given in textbook (as said by Scott Aaronson, everyone would be Gauss). Also gave some examples of P v/s NP problems (hamiltonian/eulerian cycles) and some history.
- Then introduced some basic concepts of finite-model theory, first order logic and k-SAT problem. Then discussed nomenclature of 'phase transition' wrt statistical physics, random k-SAT and XOR-objection on Deolalikar's paper.
- If you don't intend to read Deolalikar's paper, here is what he is trying to say: "9-SAT cannot be in P" (in which he uses Immerman's theorem and random k-SAT), which clearly is not the case if we replace disjunction by XORs (which can be solved by Gauss elimination ... still have to think about this). For more details read Lipton's blog.
- Then Vardi discusses the importance of P v/s NP:
1. If we prove P = NP, still there can be problems of size (10n)^10000 which are in P but take way too long to solve.
2. If we prove P != NP, again there can be NP problems of size n^(log log log n), which then becomes a way faster solution.
- On his closing note, Vardi cites the industry SAT solvers. Though the industry SAT solvers are capable to solve SAT instances with million variables, there are some SAT instances with few hundred variables which are extremely difficult to solve. According to Vardi, identifying those difficult cases is way more important than proving SAT is P (or not in P).

Now, let me quote few of his comments:
=> The argument is using induction to prove set of natural numbers is finite ... set of zero elements is finite, add a natural number to it and it will be finite, then add another and so on ... hence QED.
=> Are they same in theory and practice, well it depends ... in theory they are same, but in practice they are different.
=> Finite model theory ... number of variables ... arbitrary long, but STILL finite.

An Attempt to understand Machine Learning (Part 1)

2010-11-03T18:58:00.003-04:00

I still remember the excitement when I took "Theory of Automata" course in my undergrad and was introduced to Turing machine. Few days after digging a little, I read Church-Turing thesis which stated "Every algorithms can be expressed in terms of Turing machine". This was like saying ... well you have framework for understand everything you will eventually learn in your Masters or PhD. However, mapping everything to Turing machine kept on becoming difficult as I started doing research and particularly when I took Machine Learning course. Most people come up with different perception when they take Machine Learning or Artificial Intelligence course.

Before I begin let me make you aware that Machine "Learning" is not same as human "learning". Humans learn something is a way that is not fully understood by scientific community. Let's say two persons X and Y see a mango tree. X has never seen a mango tree before so he will create a mental picture of it as a medium sized tree with green leaves. Y on other hand will create a mental image of tree and associate it with a mental image of mango or may be even with other senses like "it taste like mango shake". Any further discussion between X and Y will be based on their mental images and not reality. Note: information in mental images is less than information in reality and the reasons for this information loss are:
- We cannot store or process all the information in the world (due to lack of 'infinite' focus)
- Everyone filters information from reality according to their past experiences or beliefs.

Hence, since it is virtually impossible to have two person with exactly same experiences, it is impossible to have two people with exactly same mental images or information. If we treat the mental image as an output or even intermediate variable that we use to spit out an output, there is no "common" theory/algorithm that will generate a common output for all humans for same problem. Hence, this huge diversity (which makes life interesting) makes humans difficult to understand.

Most scientists (at least the neurologist/psychiatrist/psychologist) use abstraction (i.e. weed out details and rely on central theme i.e. "tree") to specify a theory/algorithm that applies to all. Yet there is another problem with human learning, humans don't learn or process with objects but with patterns. Furthermore, humans use association (and not exhaustive search through all the patterns) to interpret a situation. This process of association is somewhat random or at least extremely diverse (i.e. every person associates object A to object B using different sets of patterns and these patterns change over a period of time). Hence, it is extremely difficult to play around with such diversity using a single unifying theory. So, machine learning is not about building a machine that will always pass the "Turing test" for all the humans and in all the situations (though that is the ultimate goal of Machine Learning). (Btw, if you don't know about Turing test, read http://en.wikipedia.org/wiki/Turing_test.)

Having said that, it is also very important not to be too humble while defining what Machine Learning is, especially if you compare every machine learning situation to Turing machine. Remember, assumptions for Turing machine are (that are not necessarily applicable to all Machine Learning problems):
- Entire input is available at the beginning of computation.
- No state is maintained between execution of two (same or different) programs.
Especially interesting case where it is very difficult to define the problem in terms of Turing machine is Reinforcement Learning that we will study later. Also paper by Leeuwen and Wiedermann that discusses Turing machine in comparison to contemporary computing would be a nice read.

By now I made two key points (or mental images :)):
1. Machine Learning != Human Learning
2. Machine Learning != Turing machine

References:
1. The Turing Machine Paradigm in Contemporary Computing - Leeuwen and Wiedermann.

The Last Lecture

2010-07-22T12:20:00.003-04:00

Carnegie Mellon Professor Randy Pausch (Oct. 23, 1960 - July 25, 2008) gave his last lecture at the university Sept. 18, 2007, before a packed McConomy Auditorium. In his moving presentation, "Really Achieving Your Childhood Dreams," Pausch talked about his lessons learned and gave advice to students on how to achieve their own career and personal goals.

If you haven't seen the video, I highly recommend it: http://www.youtube.com/watch?v=ji5_MqicxSo

These are some of the points that I found enlightening:
- We don't beat the reaper by living longer, but by living well, and living fully — for the reaper will come for all of us. The question is: what do we do between the time we're born and the time he shows up.
- It is not the things we do in life that we regret on our death bed. It is the things we do not. Find your passion and follow it.
- The brick walls are there for a reason. The brick walls are not there to keep us out; the brick walls are there to give us a chance to show how badly we want something.
- Experience is what you get when you didn't get what you wanted.
- When you see yourself doing something badly and nobody's bothering to tell you anymore, that's a very bad place to be. Your critics are the ones telling you they still love you and care.
- When you are pissed off at somebody, and you're angry at them, you just haven't given them enough time. Just give them a little more time — and they'll almost always impress you.
- Never lose the child-like wonder. It's just too important. It's what drives us.
- Don't complain; just work harder.
- Show gratitude.
- It's not about how to achieve your dreams. It's about how to lead your life. If you lead your life the right way, the karma will take care of itself. The dreams will come to you.
- If I could only give three words of advice, they would be, "tell the truth." If I got three more words, I'd add: "All the time."
- Do not tell people how to live their lives. Just tell them stories. And they will figure out how those stories apply to them.

May GOD rest his soul and bless his family.

Preparing a new Windows machine

2010-07-21T14:42:00.002-04:00

I am writing this mail to serve as backup in case I have to create a fresh installation.

I recently purchased a new laptop: Lenovo U350 for following reasons:
cheap ($600 + tax because of a coupon), extremely light (around 4 pound), no CD/DVD drive (which makes it light. Also, I have rarely used it on my previous laptops and it seemed to be dead weight), 13" laptop (another reason why it's light, also 13" is almost about the right size between netbook and 15" laptop), 8 cell battery (with netbook like power-saving circuit, which makes the battery last "really" long), core 2 duo + 320 GB HDD + 4GB RAM (for my programming needs), VGA output (to connect to projector for presentations), other useful accessories (HDMI (to connect to my home TV), 3USB slots, kensington lock slot, webcam, mic/headphone slot, card reader)

I have an iPhone 3Gs + a ubuntu machine (another reason I did not want a CD/DVD drive on my laptop) in office. So, I have installed following "free" softwares on new Windows 7 machine:
1. Java: JDK, Netbeans, Eclipse
2. Reader / Writer: Openoffice (for doc), Latex (Miktex, Texnicenter), Adobe Reader (for reading pdfs), PDF X-Change Viewer (for marking/highlighting pdfs), CutePDF (for creating PDF), GSView (for PS), DJVU Viewer
3. Educational: Mendeley (for maintaining my bibliography), Sciplore (for mindmaps -> Using PDF X-Change I can create a printable version of my mindmap)
4. Synchronization: Evernote (for notes), Dropbox + TortoiseSVN (for documents), Firefox + Xmarks (for bookmarks)
5. Fun: VLC, Divx, Real player, Adobe Flash, iTunes
6. Communication: GTalk, Zimbra (for managing my Personal + Rice mails) ... Since I don't chat much I didnot install Yahoo Messenger and Skype.
7. Protection: AVG Antivirus, Zone Alarm Firewall, Also created a restore point using Lenovo's once click software
8. Others: R, WinSCP, Putty (Also will install Magic Disc in case I have to work with CD/DVD image)

I also use Toodledo (for my TODO list) and Eternity (for time logging) on my iPhone.

Long term research goals

2010-06-12T13:49:00.003-04:00

My previous post discussed why I decided to do PhD ? This post discusses what I want to do after my PhD. During Sigmod, I was thinking about a question that was troubling me last year: "Whether to apply for faculty position or industry job"

Somehow "academia" seems more sense for me. So, I started asking people what are skills required to get a faculty position. Here is a summarized version of collective advices from my advisor and colleagues.

I had a discussion with one of my friend in which I made a really important point. If you want to understand any major events (political, personal, social, ...), ask yourself a simple question: "How does this relate to money ?". This principle applies in academic hiring position as well. Whether or not you will be hired as a faculty or not will solely be decided by one fundamental question: "Can you get funding during and after your tenure ?"

If the answer is "may be", then and then only the hiring committee will look into teaching skills and managerial/mentoring skills.

Let's revisit the funding question. Your chances of funding will be significantly decided by three questions:
1. Is your research worth funding ?
2. How well can you present your research ?
3. How many people know about you and your research ?

The people who are involved in your hiring process will try to extrapolate the answers to these questions based on following indicators:
a. They already know you or your advisor or have at least heard about you.
b. You can give an interesting 1 hour presentation on your central research idea.
c. You have good number of first author papers.
d. You have recommendation letters from well known researchers from your field.

Here is list of things I believe a PhD student can to to improve these indicators.

Find as soon as possible the topic you want to expertise in and publish as many first author papers as possible in that field.
Give as many (paper, poster, demo) presentations as possible in well known conferences.
Collaborate and also go for research internship. Your mentors will be the ones who will write you the recommendations. It is necessary to have strong recommendation letters from people other than your advisor.
Be a (dummy) reviewer for conferences and also learn skills necessary for writing proposals.
Work as hard as you can and think about your research all the time.

The corollary to above points are:
1. Number of first author papers are more important than publication count.
2. Bad papers may haunt you during hiring process.
3. Know the list of current hot topics --> also what "good" researchers are working on (Indexing)
4. Nobody cares about your GPA, courses you took or your extra-curricular activities.
5. You can give an interesting 1 hour presentation only if you have one research theme rather than papers scattered all over the field.

Of course there are exceptions to all above rules. So, don't be hard on yourself :)

Pragmatism to Perspective

2010-03-27T01:41:00.001-04:00

Work hard(???) at what others are doing
Then tried to do it better
Then tried to do something that many ppl were not doing
However, road less travelled doesnot always make a difference.

Doing something different might also not work
Invested or may be wasted time on pointless, but different things
Convinced myself that what I am doing is what I really want
Then realized I didnot know what I really want.

Dreams turned out to be too ambitious
Or may be reality turned out to be too harsh
Running away from truth seemed simpler choice
Since rationality has hit a road-block.

Answer hopefully is mixture of all:
Cup of pragmatism and hardwork,
a spoon of perspective and a entire jar of passion
Also, bulk load of unknown spices from life.

GTD Workflow

2010-01-29T20:37:00.003-05:00

My updated GTD Workflow for academic research in pdf format for printing can be found at my trac repository.

Here is the jpeg version of the same:

Note:
1. Most GTD systems have feedback loop for Delegated tasks. I do not maintain that because most of my tasks (research/coursework) do not involve lot of people interactions / delegations.

God does not play dice

2009-11-19T02:43:00.002-05:00

The title of this blog post is a famous quote by Einstein. This post is not on GOD or religion, but on the concept of probability. This post is also based on the concept of determinism and hidden variable theory.

First let's differentiate between an experiment and an event. An event simply occurs, whereas in experiment, we observe the event. Let's call this process of observing to note the outcome of the event as information retrieval process i.e we are trying to get information about the event when it occurs. Some of the information retrieval processes are seeing, hearing, or using any other sensory organs, taking a picture, video/audio recording, etc.

Note that information retrieval process may in someway disturb the event itself. See Heisenberg uncertainty principle. But for sake of this thought experiment, imagine we have some special information retrieval process that gets information about the event or experiment, without in any way disturbing the experiment. (Note, quantum mechanics says this is not possible. But I say this is not possible with currently available information retrieval mechanism. May be in future we may have sophisticated information retrieval mechanism where it might be possible).

Consider a experiment of rolling a dice. Do you think it is deterministic or probabilistic/stochastic ?

The deterministic point of view says that if we knew weight of dice, envirnomental factors (wind direction/strength, humidity), surface friction, density of dice, exact hand movements (angle of release, force during release), and many many other factors, then we can predict the exact outcome of the dice.

Since we don't know many of this factors (i.e hidden variables), we cannot predict the exact outcome of the dice. To model these variables, so that we can get very close to the outcome and in some way make the experiment useful, we use the concept of probability.

Presentation on Map Reduce Merge

2009-11-10T12:18:00.002-05:00

I gave a presentation yesterday (here is the powerpoint slides) and I am writing this blog to just jot down things I have learnt.:

I need to improve my grammar. The best thing to do is give a practice talk before your presentation.
It is very important to add all the references in your presentation.
If the paper is about a system, always add big picture describing the modules and their interactions.
If possible try to prepare for a demo to get people excited about the topic.
Always be sure of what you tell in the presentation. If you don't know something, say that "I don't know or I am not sure of it".

In the flow of talk, I said "As a database researcher" when I meant to say "As a database person". It seemed pompous at that time and somehow I preferred not to correct it at that time. But in retrospective as I think about it, I am a database researcher, may be not a good one and definitely not an established one. But still, I spent considerable time of my daily time doing research and I believe that qualifies me to be a "researcher".

SACHIN TENDULKAR - The Greatest (Video Collection)

2009-11-05T15:59:00.004-05:00

What is your motivation ?
Its the passion. I care about playing for India. Its being a dream and I am absolutely honored to do that for last 20 years. - Sachin Tendulkar.

First some of his great innings:

Second, his interviews:

Third, Documentaries:

Fourth, Best Quotes on Sachin:

And lastly, his bowling:

How to set up Trac + SVN on Ubuntu

2009-10-02T16:55:00.002-04:00

sudo apt-get install trac
sudo apt-get install libapache2-mod-python libapache2-mod-python-doc libapache2-svn

# Create a directory where all your Trac projects will live
sudo mkdir /var/lib/trac
sudo mkdir /var/lib/svn

# Usernames
sudo htpasswd -cm /etc/svnauth urname
sudo htpasswd -cm /etc/svnauth nextuserrname

# Add following to /etc/svnaccess
sudo vim /etc/svnaccess
##################From here#########################

[groups]
developers = yourusername, nextusername
[ / ]
@developers = rw
* = r

##################Till here#########################

# Add following to /etc/apache2/sites-available/default
sudo vim /etc/apache2/sites-available/default
##################From here#########################

DAV svn
SVNParentPath /var/lib/svn

AuthType Basic
AuthName "Subversion Repository"
AuthUserFile /etc/svnauth
Require valid-user

AuthzSVNAccessFile /etc/svnaccess

SetHandler mod_python
PythonHandler trac.web.modpython_frontend
PythonOption TracEnvParentDir /var/lib/svn
PythonOption TracUriRoot /trac

AuthType Basic
AuthName "Trac"
AuthUserFile /etc/svnauth
Require valid-user

##################Till here#########################

# Statically set the users in envvars
sudo vim /etc/apache2/envvars
export APACHE_RUN_USER=www-data
export APACHE_RUN_GROUP=www-data

# Reload the configuration
sudo /etc/init.d/apache2 reload

# Say ur project name is PhDProject
sudo svnadmin create /var/lib/svn/PhDProject

# Assign permissions
sudo chown www-data:www-data -R /var/lib/trac
sudo chown www-data:www-data -R /var/lib/svn

# Create Trac with SVN
sudo trac-admin /var/lib/trac/PhDProject/ initenv 'PhDProject' 'sqlite:db/trac.db' 'svn' '/var/lib/svn/PhDProject'

# Add urself to developers group
sudo trac-admin /var/lib/trac/PhDProject/ permission add urusername developers

# Optional: Some cool plugin
sudo easy_install http://trac-hacks.org/svn/accountmanagerplugin/trunk

# Re-assign permission
sudo chown www-data:www-data -R /var/lib/trac
sudo chown www-data:www-data -R /var/lib/svn

# Reload the configuration and restart
sudo /etc/init.d/apache2 reload
sudo /etc/init.d/apache2 restart

References:
http://trac.edgewall.org/wiki/TracUbuntuMultipleProjects
http://anantgarg.com/2009/03/25/subversion-trac-multiple-projects/

Meta-PhD

2009-09-23T02:08:00.004-04:00

Why did I decide to do a PhD ?
When Chris asked me to do PhD, I was dead sure about one thing: I want to be in US for at least next 4-5 years of my life. So, I had two choices in front of me: either accept the SDE job offer from Microsoft SQL Server Data Mining team or accept Chris' PhD offer. Somewhere in back of my mind, I wanted to do a PhD after 3-4 years of my job. Also, Microsoft SQL Server Data Mining team was a dream job at that time. However, I decided to go for PhD for following reasons (ranked in the order of importance):
1. Why PhD?: For rest of my life, (except the daily chores and some personal issues), I want to THINK and DO certain work. I believe PhD sharpens (if not develops) the unbiased factual decision making process. It also helps you identify and enumerate some choices which you probably would not had thought of. (To be brutally honest, you don't need to do PhD for this, you just need to spent some time regularly acquiring this skills. PhD is one of the well-known an hopefully the simplest way to acquire them.)
2. Why Chris?:
a. I don't think I would find a better advisor than Chris (for "me"). There are two reasons for it. First, I am very comfortable communicating my ideas with him (both technical as well as non-technical). Second, Chris is an "awesome" researcher and I will learn a lot (and not just Database Research topics) from him.
3. Why PhD then and not afterwards?: If I jumped into job, I don't think I would ever return to PhD. (May be I think once I am settled down with good income, I would not have the motivation to start studying).

Though I have talked about skills that I would like to acquire in general, I would like to break it into my so-called mini-goals. The list below is a result of an hour long discussion with Ravi Jampani.

Mini-Goals for PhD (ranked in the order of importance):
1. Problem Identification Skills: Before I complete my PhD, this is the most important skill that I would like to acquire. For example, I should be able to identify potential problems in a given area after doing critical literature study.
2. Critical Literature Study or Building your base: This includes accumulation, simplification, contextual categorization (eg: Mindmap with Mnemonics) of the knowledge in my research field. This skill should also facilitate a way of frequently revisiting this knowledge base and also doing periodic "Lateral thinking" on it.
3. Multi-domain expertise: This means iterating skill 2 for multiple fields. It will also help for skill 1. The fields that I am interested in are Database, Data Mining & Machine Learning, Algorithms(with emphasis on Approximation and Randomization) and Mathematics (with emphasis on Statistics).
4. Indexing: Finding out who are good researchers in your field and always knowing what they are working on (kind of like fan-following).
5. Improve my communication skills and then writing skills. As of now, I ramble a lot and am almost never articulate in any discussion (though I believe that I am very persistent and continue the discussion atleast until I have communicated my ideas).
6. Collaboration of research with other people: This is least important skill as of now.

Useful advice from different researchers for new graduate students:
1. Chris:
- Indexing skill (i.e skill 4)
- Do not do exactly what the good researchers are doing.
2. Steven Weinberg:
- Start doing research (instead of writing this blog post ;) ), and pick up what you needed to know as you went along.
- Forgive yourself for wasting time. As you will never be sure which are the right problems to work on, most of the time that you spend at your desk will be wasted.
3. Richard Hamming:
- What are the most important problems in your field?, Are you working on one of them? and Why not?
- 'Knowledge and productivity are like compound interest.' Given two people of approximately the same ability and one person who works ten percent more than the other, the latter will more than twice outproduce the former. The more you know, the more you learn it is very much like compound interest.
- Luck favours the prepared mind (originally for Louis Pasteur). This essentially means that acquire skill 2 and 3 and you will soon find an opportunity to identify a 'good' potential problem and may be even solve it.
3. Others:
- There is not substitute for hard work. (Most important of all the advices)
- Be Persistent: "I have not failed. I've just found 10,000 ways that won't work" - Thomas A. Edison
- Explore as many areas as you can find. Read papers from different areas, not just your area.
4. Self:
- Be modest. The ego destroys the process of learning. Never disregard anyone who does not agree with you. Hear what he/she has to say and then try to think it through.
- Be committed to your problem. even if you think its not important. Finish it first and then start working on what you think is important.
- Think clearly, write clearly and talk clearly. Always talk with right amount of abstraction.

Mistakes you can make in your first job

2009-07-23T18:29:00.003-04:00

1. Not taking time to study the fundamentals.
Eg: If you are expected to write C++ program, first learn C++. Take time to understand classes, inheritance, composition, etc. By understand, I mean you not only need to know the syntax, but also imagine the scenarios in which they are useful (an which they are not). If you don't know STL or smart pointers, believe me you would be re-inventing some of its code inefficiently :) and your code might be prone to bugs.

2. Google search before you ask your team lead or team members. This protects you from asking stupid questions or worse committing stupid mistakes.

3. Under-estimating the importance of "requirement gathering" and "design" phase aka Start coding immediately. A good programmer always takes time to understand the problem and create a big picture of the project in his/her head.

4. Trying too hard to present what you are not. It is extremely difficult to live a lie. Remember honesty should be coupled with extreme desire to improve yourself and also hard-work.

5. Blaming others to improve your chances of staying in the job. Believe me nobody likes a snitch. If you commit a mistake, be brave and accept the responsibility. Be proactive and ask the mentor for what you can do to improve your chances instead.

6. Disregarding "Murphy's law" and not clearing your expectations with team members.
If you think there is slightest possiblity of any team member to commit certain mistake or make certain wrong assumption, clarify it.

7. Delving into details without getting the big picture (kind of re-statement of point 3). But this is so common that I need to mention it again.

8. While using new software library, not differentiating the interface part and core problem part of the project.

9. Ignoring the coding standards of company. If you company does not have one, try to follow the coding standards given in the book C++ Coding Standards: 101 Rules, Guidelines, and Best Practices.

10. Reinventing the wheel in your design aka not knowing what are design patterns. If you don't know what design pattern mean read Head First Design Pattern. If you have already taken course in design patterns, then revising Gang of Four book won't hurt.

11. Not using a version control. Chances are that you would break the working code when you are trying to add new functionality. If you are using a version control, then remember to add messages like "Working version 1.4", etc. and learn how to revert back to certain version. If you are not allowed to use version control, make copies whenever you implement and test new functionality.

12. Not discussing your design with others aka school-children syndrome. Think of it this way rather than sharing your trade-secrets; by explaining or helping others, you improve your knowledge base.

13. Not respecting chain of command. Always give credits to your mentors, even if you think they have not helped you in it. It is even worse, if you complain against your mentors to their managers. Remember habit 4 (Think Win-win) of 7 habits of highly effective people.

Two books you must read and re-read before joining the job,
1. 7 habits of highly successful people by Stephen Covey. (Summary)
2. Getting things done by David Allen. (Summary)

Why are Indians targetted ?

2009-07-05T10:32:00.002-04:00

I am writing this article in response to the article of same name in "Times Life" (a section in the news paper Times of India) dated July 5th 2009. Most of the ideas are borrowed from this article.

Let us first enumerate what could be the major reasons why Indians are targeted:

Racism and jealousy
Cultural and Behavioral habits (the "Herd" mentality)

I would like to ignore the first reason and want to focus on the second reason only. Here are the points that support my assumption:

Serenity Prayer
My experience in Gainesville, Florida suggests that most people are comfortable with working in a multi-cultural society. Some people may not like some sect of people, but it is usually due to personal preference rather than racism (It is important to note there is a difference. Just because I am from different race or ethinicity doesnot mean the other person has to like me. It is only when the other person starts humiliating you, it is racism).
Whenever there is a inter-relationship problem, it is better to start identifying the problem in yourself first and try to improve it rather than finding problems in others and blaming them for the situation.

Statistically speaking, I have seen most Indians hanging out with only Indians. There are several reasons for that:

We do not want to put extra effort to understand the cultural diversity and to come up with a harmony of both Indian cultural system and the host cultural system. For example, most jokes we share with our "Indian" friends might not be funny when we share it with people from different race.
Fear of rejection/intrusion: We do not take up the initiative to talk to a "non-Indian" colleague and bond with him/her. By bonding, I mean come up with a level of comfortableness, where both you and him/her can enjoy daily discussions (say sports, politics, family, etc ..). Usually, people take this initiative only when both parties have to spend a lot of time with each other as colleagues.
And many more ...

The bottom line is this ... Assume non-racist environment and ignore few "racist" wise-a**. It is very important to understand and respect the host culture. Put effort to find out common trivia regarding politics, sports, etc which might be a topic of daily discussions among peers. Participate in some (host-cultural) social events, such as going to a bar, bbq, etc. Always respect the host law. And be a good guest (i.e. make the host comfortable around you) !!!

This article does not in any way suggest changing your value system. I am proud to be an Indian, and I will never change by values (eg. respecting elders, praying, helping others, etc ..). But it doesnot mean only the Indian value system is the best and all others are inferior. I think I could learn a lot from US and it is necessary to put effort to learn the host culture.

Shuffle functions

2009-06-21T15:22:00.003-04:00

Very frequency asked question is "Write a program to shuffle a set of cards". There are many approaches to solve this problem.

Almost all of them treat the set of cards as a list and write the program to shuffle the list.

One approach is to emulate the human shuffling:
Hindu Shuffle; Riffle shuffle

Other techniques are discussed in more details in wikipedia

Here is an interesting but not optimal way(O(n lgn)) to shuffle a list:
In Ocaml:

let shuffle l1 =
let sortComparator x y =
(
match (Random.int 3) with
0 -> 0
| 1 -> -1
| 2 -> 1
| _ -> failwith "Error in shuffle"
)
in
List.sort sortComparator l1
;;

C++ Code:

template < class T >
bool sortComparator(T x, T y){
if(rand % 2 == 0)
true;
else
false
}

template < class T >
vector < t > shuffle(vector < t > cards) {
sort(cards.begin(), cards.end(), sortComparator);
return cards;
}

Kindle DX review

2009-06-19T19:03:00.002-04:00

1. PDF capability:

For pdf documents, treat Kindle DX as a READING device and nothing else.

Does not Support: Note-taking, highlighting, zooming(both the document and font ) capability and has bad searching capability. Also there is no dictionary for PDFs

But it serves the purpose of READING - Resolution is good, it does not strain your eyes, and landscape view is good enough for most of my documents. Also, I prefer to take active notes rather than just higlight, it's not a big deal for me.

Transferring PDF - very easy ... just connect to USB and copy your PDFs to Kindle.

Steve Bain has more critical review on it.

2. Weight:

Extremely light atleast for me.

3. Durability:

Though material looks good, please don't expect it to be extremely sturdy. Hence I recommend using cover(either leather or neophryne) while traveling.

4. Battery life:

Extremely good. I haven't tested it very much but just turn off whispernet and you should expect 4 weeks of battery life

5. Choices of Books:

Amazon is undoubtedly the best choice.

6. Awesome feature:

Wikipedia is free .... anywhere in US !!!

7. Cost:

If you think $359 is OK for Kindle 2, Kindle DX is definitely worth $489.

If you donot like to read research papers on computer, you will save on great deal of printing and "trees" :)

As an engineering student, you will save a huge amount of money and space on printed books if you chose to buy Kindle DX.

Bottom line:

If you cannot live without highlighting and note-taking, DON'T BUY KINDLE DX ... go for Sony PRS-700(if you like text notes) or iRex Iliad(if you absolutely cannot live without handwritten notes)

If you think iRex is too costly (apart from the fact it has no support in US, you have to ship iRex to Germany) and it you want to READ pdfs without straining you eyes, definetely go for Kindle DX.

Swine Flu

2009-06-18T14:57:00.002-04:00

CDC has announced H1N1 flu as pandemic disease and my parents (back in India) were worried. Here are the few facts(as of June 12, 2009) that might ease their concern:
1. Respiratory mask are advised only to people with high risk of influenza (See table 1 at http://www.cdc.gov/h1n1flu/masks.htm)
Most of young college graduates do not fall into this category (unless you are studying health care or related fields). See http://www.cdc.gov/h1n1flu/masks.htm#footnote3

2. Number of confirmed or probable cases: 17,855
Number of Deaths: 44

Well, if you are an Indian, I guess you are pretty much immune to it (See Statistics of Malaria for India)

number of deaths | 9352 deaths per year
cause of death probability | 1 in 1110 ~~ 0.090%
rate of death | 1 death per 100000 persons per year
DAILY | 843 738 life years lost per year
DAILY rate | 80 life years per 100000 persons per year

For US, Statistics for Malaria are:

number of deaths | 3 deaths per year
cause of death probability | 1 in 768898 ~~ 0.00013%
rate of death | 0.0011 deaths per 100000 persons per year
DALY | 57 life years lost per year

Well, you can see statistically if you were not paranoid about fever or malaria or cold/cough in India (or US), you need not be worried about Swine flu either.

However, here are prescribed precautions by CDC for Swine flu:

Cover your nose and mouth with a tissue when you cough or sneeze. Throw the tissue in the trash after you use it.
Wash your hands often with soap and water, especially after you cough or sneeze. Alcohol-based hand cleaners are also effective.
Avoid touching your eyes, nose or mouth. Germs spread this way.
Try to avoid close contact with sick people.
If you are sick with a flu-like illness, stay home for 7 days after your symptoms begin or until you have been symptom-free for 24 hours, whichever is longer. This is to keep from infecting others and spreading the virus further.
Follow public health advice regarding school closures, avoiding crowds and other social distancing measures.

Reference: Statistics are gathered from Wolfram Alpha and CDC

Research Notebook

2009-05-30T13:14:00.003-04:00

After experimenting a bit with Evernote, I decided to move to OneNote for following reasons:
1. Evernote has no drawing tools. I like to draw and scribble a lot.
2. I get free subscription of OneNote as a student, whereas I need to pay for Evernote for some additional features like image recognition etc ... Though I don't need them right now, it would be handy to have them.
3. Onenote allows you to integrate audio and video notes, whereas Evernote is simply text based.
4. Onenote allows your notes to be arranged in hierachical folders, whereas Evernote is huge collections of notes with tags. Though I like the tagging feature (which Onenote also has), I don't think it is enough to organize my notes.

Though I think Synchronize feature in Evernote is awesome, I use Webexport + Publish as PDF feature in OneNote may be once a week. However, webediting feature in Evernote has no counterpart for OneNote, I will have to live with it until Office 2010. (I donot think LiveMesh solves this problem as I use Ubuntu on my lab machines)

I have used OneNote Web Exporter plugin to export my Research Notes for webview.

For now (until UF doesnot close my CISE account), I will maintain my notes at:
http://www.cise.ufl.edu/~npansare/webview.html and PDF at http://www.cise.ufl.edu/~npansare/ResearchNotebook.pdf

If you are using Firefox, you need to have Mozilla Archive Format add-on (since it is in MHT format). However, it still doesnot display properly. I recommend IE for webview or if you are a linux user, view the PDF.

My bookmarks, research papers, books

2009-04-26T12:00:00.002-04:00

I use xmarks to synchronize my bookmarks since I have both Windows and Ubuntu machines: http://share.xmarks.com/folder/bookmarks/W6kXue0nMH

I am experimenting with Zotero: https://www.zotero.org/niketanpansare/21978/items

If you have missed by previous post:
I am using citeseer for managing the papers I read: http://www.citeulike.org/user/niketan

Here is a list of books I would like to read: http://spreadsheets.google.com/pub?key=pRiihxKnNDBmNK4-OrOY0ZA

You and Your Research by Richard Hamming

2009-04-20T12:33:00.005-04:00

After doing a little bit of Google search, I found following links:

Transcript: http://www.cs.virginia.edu/~robins/YouAndYourResearch.html

10 Simple Rules from above transcript

Video1 :

Richard Hamming Talk - part 1

Video 2:

Richard Hamming Talk - part 2

Video 3:

Richard Hamming Talk - part 3

Enjoy !!!

Here is another good video series on Science:
Richard Dawkins - Breaking the Science Barrier

Time Management tips by Randy Pausch

2009-04-13T03:37:00.001-04:00

1. Create a list of 100 things you want to do in life.

2. Ask yourself each time you are doing a thing --> why am I doing this ? Use the list for reference.

3. Also make sure you focus on critical few, rather than trivial many.

4. If you can dream it, you can do it.

5. Plan each day, each week, each semester. You can change your plan but you need to have one to change it.

6. TODO List - Break things down into little steps. Do the ugliest thing first.

7. Covey's four quadrant TODO:

	Due Soon	Not Due Soon
Imp	1	2
Not Imp	3	4

8. Clean up the desk. Focus on one thing at a time.

9. Touch one piece of paper at a time. Your inbox is not your TODO list.

10. Recommended - Atleast 2 screens, Speaker phone, Desk space to work, Desk near window

11. Write - Thank you notes. Because it is rare. Gratitude is extremely helpful. (One Minute manager: Killer Whale Eg.)

12. Post-IT Notes

13. Say NO graciously. I will do it if you don't find anyone else.

14. Find your creative time and defend it ruthlessly. Spend it alone.

15. Find your dead time and schedule meetings, phone call during that time.

16. Buy a earphone piece for Iphone.

17. Keep a box for the person, then when the box is full, interrupt the person and tell him/her the things you have for them.

18. Voicemail: "... I encourage you to send me a mail @ ..".

19. Time journal. Update it every 1/2 hours. Monitor yourself after 3 days and 2 weeks.

20. Make a fake class - Take a book and go to library.

21. Doing things at last moment or Thinking Work expands to fill time, hence do it at end ---> Stress + Expensive (Work Hard). Better Approach: Make a fake deadline.

22. Treat the people well. (Do dirty work yourself).

23. If you want someone to get things done: Give them a specific thing to do, a specific date/time and specific reward or penalty.

24. Send a mail after a conversation so that there is no confusion.

25. Ask people to find out their agenda before meeting. One person is assigned who writes down decision made in the meeting and mail it to everyone.

26. Do not delete the email. Save them for later reference.

27. If a person has not responded in 48 hours, its OK to nag them.

28. When you are on vacation, keep a vacation responder. Note: Its not a vacation, if you read email.

29. Kill the television. Average person watches the TV for 28 hours a week.

30. Exchange money for time. Get other people to do trivial work for you. Eg: mowing the lawn, ...

31. You always have time for eating, sleeping and exercise. Never take time out of those.

32. Never break a promise; Call and renegotiate the deadline if you think you cannot finish it by deadline.

33. Feedbacks Loops: Ask in confidence.

34. Get a PDA if you don't have it and use it wisely.

I donot have brain to spare for things computers can do for me - todo list, calendars

Recommended Books:

1. One minute manager

2. 7 habits of highly successful people.

Creating flash cards using Latex

2009-03-17T17:49:00.005-04:00

Installation (in Ubuntu):

1. Install Kile

2. apt-get latex texlive and texlive-latex-extra packages

3. Modify the /usr/share/texmf-texlive/tex/latex/flashcards/flashcards.cls to new flashcards.cls

4. Print them in pdf format for reading

My future Pet project:

1. Create a java viewer (since I use both linux and windows) for latex or use some open source java library that renders latex (I didnot find a good C# library that does it either).

2. Use the flashcard package.

3. Use supermemo algorithm or Leitner system to enhance learning experience.

References:

Guide to using flashcard document class: Alexander Budge's document

Installation:

1. http://underdown.wordpress.com/2009/01/26/creating-printable-pdf-flash-cards-using-latex/

2. http://feferraz.net/en/P/Flashcards_in_LaTeX

Collections of good flash cards: http://www.physics.utah.edu/~jasonu/flash-cards/

How to access the machine in CISE labs @ UF

2009-03-06T20:00:00.003-05:00

Here is CISE's official webpage for accessing CISE public machines: http://www.cise.ufl.edu/help/access/index.shtml

Here is quick summary:

To access linux or solaris cise machines, you can

SSH using "Putty" on thunder.cise.ufl.edu (or sand, rain, bay, shine, storm, ...)

or SCP using "WinSCP"

To access Windows machine, you can remote desktop (or rdesktop) to new-mercury.cise.ufl.edu

If you have an office in CISE labs, you can access you machine using following steps:

Note: You will need a CISE account and password to the local machine. :)

You can replace 10.227.170.147 using your IP address.

To be done once: install vnc server and openssh in you session and vnc client on you home machine

Start vnc server on the machine (in CISE Lab)

1. Locally using command: vnc4server :n (where n is some number say eg. :2)

or on remote machine - these are steps

1. open putty

2. ssh to rain

3. ssh to 10.227.170.147 from rain

4. vnc4server :n (where n is some number say eg. :2)

1. open putty

2. Go to Connections > SSH > Tunnels

Source port: 5901

Destination: 10.227.170.147:5901

3. Connect to rain.cise.ufl.edu n leave the session as it is

4. Open VNC client and connect to 127.0.0.1:1

5. Enter password in the small dialog box

6. gnome-session (if you get a terminal, you can skip this step by configuring the vnc server settings)

Books I intend to read

2009-02-15T13:36:00.002-05:00

I will keep updating this excel sheet. Here is the initial version:

http://spreadsheets.google.com/pub?key=pRiihxKnNDBmNK4-OrOY0ZA

They are categorized according to topics(field the book belongs to), authors and priorities (Priority doesnot imply the "goodness" of the book. I use that column for scheduling purposes).

I use citeulike for keeping track of research papers I read. Here is the link:

http://www.citeulike.org/user/niketan

Memorizing pi to 70 decimal places

2009-01-30T18:16:00.001-05:00

First 8 digits can be memorized using 2 different ways:

First, Counting number of letters of words:

How I wish I could recollect pi easily today

3. 1 4 1 5 9 2 6 5

Second, Major System (see below):

3. Turtle bench lao

3. 1 4 1 5 9 2 6 5

Mnemonic for the remaining decimal places is using major system only:

(Disclaimer: This is not to hurt any person and do not in anyways express my opinion. It is only meant to be humorous, so that I could remember the mnemonic easily)

Homo love pic of Obama’s enemy for change = army mafia man

3 5 8 9 7 9 3 2 3 84 6 2 6 4 3 3 8 3 2

Iqbal Singh favorite pocket shop maybe in Obama gully

7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5

Note: there is no zero until now

Diesel fans, beggar, borrower help enemy seek hafta jar

1 0 5 8 2 9 7 4 9 4 4 59 2 3 0 7 81 6 4

Done !!! So therefore pi is

3.1415926535897932384626433832795028841971693993751058209749445923078164…

Major System (Refine this list):

0	s, z, soft c	"z" is the first letter of zero. The others have a similar sound
1	d, t	d, t have one downstroke and sound similar(some variants include th)
2	N	n has two downstrokes
3	M	three downstrokes , also "m" looks like a "3" on its side
4	R	last letter of four, also 4 and R are almost mirror images of each other
5	L	L is the Roman Numeral for 50
6	j, sh, soft ch, dg, zh, soft g	a script j has a lower loop / g is almost a 6 flipped over
7	k, hard c, hard g, q, qu	capital K contains two sevens
8	f, v	script f resembles a figure-8. V sounds similar. (some variants include th)
9	b, p	p is a mirror-image 9. b sounds similar and resembles a 9 rolled around
Unassigned	Vowel sounds, w,h,y	These can be used anywhere without changing a word's number value

Note: When there are two same adjacent letters, consider only 1. Eg: mapped mean 391, not 3991. Also sound is important, not the letters, eg: Michael stands for 375. Also, g (hard) is 7, not 8. Also, nympho is 238 not 239.

You can also download pdf version of above blog entry: MemorizingValueOfPi.pdf

Mumbai terror attack

2008-12-06T23:50:00.000-05:00

I have been itching from past few days to write a blog entry, but was busy with assignments and project. Here is quick update from my side:

I will finish my application process tomorrow for PhD program at Rice University. Florida has won SEC championship game, and hopefully will win National championship also. My best wishes are with coach Urban Meyer and his team. I followed Florida games throughout this season and am really impressed by Tim Tebow’s dedication. For those who don’t know, Tim Tebow is University of Florida quarterback, Heisman Trophy winner with a GPA of 3.7!!! And yes, he visited Philippines for missionary work in his spring break rather than going to Daytona or Miami beach.

I intend to address issues that came to my mind after November 2008 Mumbai attack. Interesting thing is I have to write date along the topic name, suggests “There have been more”. There have been 5 bombing incidents within a period of 8 months (Dec 6 2008, Jan 27 2003, July 28 2003, August 25 2003). Then there is July 11 2006 Mumbai train bombing. In fact, I was outside the Malad station, returning from Java class when these bombing incidents occurred. I had to walk from Malad to my place, since trains and bus services were stopped to prevent further attacks. Here is listing of all the terrorist attacks that took place in India: http://en.wikipedia.org/wiki/Chronology_of_terrorist_incidents_in_India

My heart fills with pain when I read and hear about this. As human being, I have extreme desire to end these kinds of attacks and bring peace in the world, and as a science student, I see it as a problem that it yet to be solved. I will try to address these emotions separately and hopefully, at end of this blog entry, I am able to put down thoughts that have been revolving in my mind (this is literal translation of an Hindi expression J ).

First, let me offer my prayers and condolences for those who have lost their lives. There was a candle light event at University of Florida campus. I was overwhelmed to see people from various countries (including Pakistan) share the same sentiments.

Now let’s address the issues rationally and methodically:

1. Is India prepared to handle terrorist attacks?

I believe Indian defense forces (which include Police) are capable to counter any kind of attack. But I must say we are not ready to predict such attacks. India does not have a centralized counter-terrorist plan (which should include local law enforcement agencies to RAW, navy and army). Efforts should be made to formulate such plan. It will require considerable investment in developing this infrastructure.

2. “Blame game” (as Mr Musharraf puts it) post-attack

I believe that both countries India and Pakistan cannot afford a war. Even if they could, they shouldn’t go for it. There is significant portion of people on both sides which hate other country and believe in war propaganda. These people were either victims of partition or war or probably are “brainwashed”. I use this term to generalize any kind of thought processes which is built up based on environment and which relies totally on emotions rather than logical and rational thinking. Both Pakistan and India have to make sure that such people are not the elected representative of people or into law enforcement.

I am sure that Pakistani government did not authorize this attack, but it is also confirmed that this attack was masterminded in Pakistan and Pakistani nationals were involved in this attack (See: http://broadband.indiatimes.com/toishowvideo/3800626.cms). Also, I disagree with the fact that it is just India’s internal problem. If there is a citizen of your country, who promotes terrorist activities, it is responsibility of the government to act against such person (even if he is from your intelligence services). I think Pakistan government should investigate into this and ban any terror camps.

Again, I want to summarize by saying, I do not believe in war, but I think Pakistan should make considerable efforts to eliminate terrorist camps in their region. Also, I think peace talks with Pakistan should be continued and efforts should be made by Indian government to coordinate with Pakistan government to take action against people involved in this attack.

3. Islam and terrorism

I respect Islam and think it has something wonderful to offer to world, eg: “Zakat” (alms-giving). But, I feel sad for people who misinterpret Quran and believe in killing other people in name of Jihad (See http://www.youtube.com/watch?v=Bxk5AAA5FbI). I am sure God will not absolve them of such sins. I have many Muslim friends who are very nice people. It is unfortunate that they are categorized because of these terrorist. I would like to point out the fact that Indian Muslims condemned this terrorist attack and even refused to bury the terrorists in Mumbai. Hanif Nalkhande, a spokesman for the Muslim Jama Masjid Trust, said: "People who committed this heinous crime cannot be called Muslim. Islam does not permit this sort of barbaric crime." (See http://www.timesonline.co.uk/tol/news/world/asia/article5267860.ece)

I believe any religion (including Hinduism) should not tolerate harming other people in its name. I am against anyone who is involved in Mumbai and Gujarat riots.

4. Responsibility of media

I think media should not abuse the freedom of speech and should be discreet in case of such emergency. I hate to point out that terrorist were watching the television which displayed all the movements of India defense forces, which may have delayed the operation and cause further casualties. (See http://news.bbc.co.uk/2/hi/south_asia/7760754.stm).

5. Assessment of manpower and equipments of Indian police is necessary (See http://news.bbc.co.uk/2/hi/south_asia/7760460.stm). I understand it is not a step function, but steps should be taken to ensure gradual progress of Indian forces.

These are my personal opinion, and do not intend to harm anyone or any sect. I also do not intend to finger point at any country. If you feel I have hurt your feelings or am being unfair or incorrect, please write back to me and I will modify or probably delete this blog.

I would like to conclude with two sayings:

“Eye for an eye would make the whole world blind” – Mahatma Gandhi.

“All that is necessary for the triumph of evil is that good men do nothing” – Edmund Burke.

Microsoft Internship

2008-09-15T17:16:00.000-04:00

My interview experience with Microsoft:

Here are some more pictures:

I also visited couple of other places during internship:

Overall the experience was awesome. I got an offer at end of internship, but had to refuse it to pursue PhD. My team lead was Bogdan Crivat and my manager was Raman Iyer. Both of them are amazing guys and it was a great learning experience. I contributed a "little" in development of Table Analysis Tool for Cloud. In all, I think it is amazing product. If you haven't tried it, I encourage you to do so (atleast the online version).

GatorMemo version 3.0 is ready !!!

2008-09-14T15:40:00.001-04:00

After I decided to do PhD, I always wanted to improve my study process (especially my notes management system). After several discussions with my internship manager Raman Iyer, my friends Raja Nadar and Kishore Malani, I decided to go ahead with GatorMemo. It is build on principles of SuperMemo (spaced learning) and Mindmaps.

It started out as Windows Form application which resulted in version 2.0. I feel the user interface is too complicated for normal user, so decided to build it again from scratch using WPF instead of WinForms. Functionally, there is no difference between these two versions (except WPF doesnt have facility to play audio/video files. I might add them as soon as I get time to work on it).

Suggestions:
1. Read a book, research paper, or go through lectures/podcast/videos, etc ...
2. Then, create a mindmap after completing understanding the topic. I usually refer to 3 or more books and then organize my thoughts into mindmap. I strongly suggest to put huge amount of efforts to create a good mindmap.
3. Now, create card for each node. Front side of card can be a question about the node or simply node name and Back side can be the answer or description about the topic that the node represents.
4. I recommend adding mnemonics and bibliography to mindmap and cards. Mnemonic will help you recollect the subject matter and Bibliography will be extremely useful if you are planning to write a research paper.
5. Periodically, revise the card by using the Autolearn under Action tab (This software uses SuperMemo algorithm developed by Piotr Woznaik).
6. I also suggest using Lateral Thinking especially if you are planning to write a research papers.

Here is link to setup version 3.0: (I encourage you to to use this version)
http://niketan2.googlepages.com/GatorMemoSetup.msi

You can import following file (see Action tab):
http://niketan2.googlepages.com/OSMindMap.zip to see how s/w works :)

It is still in Beta phase, so expect bugs / exceptions :) ... (Infact I am so busy with my studies/assignments, that I did not time to any kind of corner case testing). Please mail me if you find bugs and help me improve the software.

If you are interested in improving the software, go ahead and download the code and modify it.

My new wiki

2008-08-29T16:44:00.000-04:00

http://niketanpansare.wikidot.com/

Invictus by William Ernest Henley

2008-06-20T02:30:00.000-04:00

Out of the night that covers me,
Black as the Pit from pole to pole,
I thank whatever gods may be
For my unconquerable soul.

In the fell clutch of Circumstance
I have not winced nor cried aloud.
Under the bludgeonings of Chance
My head is bloody, but unbowed.

Beyond this place of wrath and tears
Looms but the Horror of the shade,
And yet the menace of the years
Finds, and shall find me, unafraid.

It matters not how strait the gate,
How charged with punishments the scroll,
I am the master of my fate:
I am the captain of my soul.

Random Quotes

2008-06-19T18:21:00.001-04:00

If

If you can keep your head when all about you
Are losing theirs and blaming it on you;
If you can trust yourself when all men doubt you,
But make allowance for their doubting too;
If you can wait and not be tired by waiting,
Or, being lied about, don't deal in lies,
Or, being hated, don't give way to hating,
And yet don't look too good, nor talk too wise;

If you can dream - and not make dreams your master;
If you can think - and not make thoughts your aim;
If you can meet with triumph and disaster
And treat those two imposters just the same;
If you can bear to hear the truth you've spoken
Twisted by knaves to make a trap for fools,
Or watch the things you gave your life to broken,
And stoop and build 'em up with wornout tools;

If you can make one heap of all your winnings
And risk it on one turn of pitch-and-toss,
And lose, and start again at your beginnings
And never breath a word about your loss;
If you can force your heart and nerve and sinew
To serve your turn long after they are gone,
And so hold on when there is nothing in you
Except the Will which says to them: "Hold on";

If you can talk with crowds and keep your virtue,
Or walk with kings - nor lose the common touch;
If neither foes nor loving friends can hurt you;
If all men count with you, but none too much;
If you can fill the unforgiving minute
With sixty seconds' worth of distance run -
Yours is the Earth and everything that's in it,
And - which is more - you'll be a Man my son
- Rudyard Kipling

Nothing in the world can take the place of persistence.
Talent will not; nothing is more common than unsuccessful men with talent.
Genius will not; unrewarded genius is almost a proverb.
8Education will not; the world is full of educated derelicts.
Persistence and determination alone are omnipotent.
The slogan "Press On!" has solved and always will solve the problems of the human race
- Calvin Coolidge

When I do good, I feel good. When I do bad, I feel bad. That's my religion.
- Abraham Lincoln

All that I have seen teaches me to trust the Creator for all I have not seen.
- Ralph Waldo Emerson

Our deepest fear is not that we are inadequate. Our deepest fear is that we are powerful beyond measure.
- Marianne Williamson

Developers are born brave :)

2008-06-06T17:41:00.000-04:00

P versus NP

2008-05-09T17:54:00.003-04:00

Never heard about it ?

Its an unsolved problem in computer Science. Infact, if you could find a solution to it, you will get a million dollars. Well, I am not kidding (http://www.claymath.org/millennium/).
Now aren't you curious ?

Here is the official problem description: http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

I will try to explain it to you in more simpler way. It is extremely titillating problem because it is very simple to understand it and first time when you hear it, it seems that you can crack it witihin a day or two.

I will assume few things:You know what an algorithm is and what is worst, average and best case complexities (asymtotic notations) are. You may want to refer to Chapter 1,2 and 3 in Introduction to Algorithm by Cormen

Section 1: Lower bound
Say you are given a problem and you find an algorithm that solves that problem in O(n^2) time. What is the lower bound of your algorithm (or should I say the problem -- Hmmm, I will use algorithm and the problem interchangeably) ?
If your answer is O(n^2), you may want to read this section further, else you can skip this and go to the next section.

Lower bound is not about a particular algorithm, but about all possible algorithms for solving that problem.

I know 2 ways to find lower bound of the algorithms:

1. Decision tree based approach:
Eg: Lower bound of Comparison based Sorting (See this: http://www.ics.uci.edu/~eppstein/161/960116.html)

In short, comparison sort can be mapped to a decision tree (binary tree with yes and no). Longest path in binary tree with k leaves = log k.Since we know a number can be arranged in n! ways => n! leaves of decision trees.There, number of comparisions = log(n!) = n log(n) - O(n) .... using Stirling's formula.

2. Reduction:
Reduce an algorithm whose lower bound you already know to your algorithm (Thats right ... not the other way round).
Eg. Say you somehow prove that Sorting <= (O(n)) Ur algorithm, ie. Sorting is reducible to your algorithm in polynomial timeThen you can state that lower bound of your algorithm is nlogn.This in essense means that your algorithm is atleast as difficult as sorting. So, how to prove this ? Prove that by some crazy way, "Sorting can be done by your algorithm"

Section 2: Definitions
Decision problems: Problem with output either "YES" or "NO", depending on values of some input parameters

P: Class of decision problems that are "solvable" in polynomial time.

NP: Class of the decision problem that can be "verified" in polynomial time.
Eg: Sorting is NP since given a list, we can verify that it is sorted or not in polynomial time.Also, Sorting is P since it is solvable in polynomial time (O(nlogn)).
Infact, Every P problem is NP (ie to verify a P problem, we can simply solve it in polynomial time and compare the input with the output). i.e P belongsto NPWhether there exists any NP problem that is not P is yet unproven.
Trivial Solution - Every NP problem can be solved in 2^n, ie simply enumerating all cases.

NP-hard: For all problems L in NP, if L is reducible to L1 in polynomial time, then L1 is NP-hard.
NP-Complete: A problem is NP-Complete iff it is both NP and NP-hard.

See this Venn diagram for big picture.

co-NP: If complement of your problem is in NP, then your problem is in co-NP.
Eg: NP - Given a graph, is there a path of length less than k from some source node s to destination node t.co-NP - Given a graph, are all path of length greater than k
Again, whether NP = co-NP is unknown ?

Oracle: Consider Oracle to be GOD who knows everything and whom you can trust (So, computer scientist believe in GOD ... may be not in way as religion, but maybe yes to some extent)

We "pray" to GOD to give guidance. Similarly, we ask Oracle to help us with the problem.

GOD give us omens. Oracle gives us a certificate (an input sequence that will probably reveal the "TRUTH"). So you try to verify the certificate by your polynomial time verification algorithm (assuming it is NP).

Now here is a trick:

If the answer to that certificate is "YES" ... cool ... you have solved the problem !!!
If the answer is "NO" .... you ask for a new certificate from the Oracle.

(You could argue that since we trust Oracle, we should output "NO". But, we don't do that because Oracle gives a random certificate for undecidable problems. This makes it indeterministic, hence NP => nondeterministic polynomial).

Section 3: The real stuff
The biggest breakthrough in this area: Stephen Cook proved that Boolean Satisfiability problem (SAT) is NP-Complete.

So, if you could prove one of this things, you probably don't have to work any more for your thesis or field's medal:
1. SAT has polynomial time algorithm
2. Give non-polynomial time lower bound argument for SAT

If you prove 1 => you have proven P = NP
If you prove 2 => you have proven P != NP

OK. Let me makes things a little easy for you. Instead of SAT, you can do above things on any one of these problems

And yippee .... you will be more popular than Donald Knuth in Computer Science field.

I would encourage you to read "Computers and Intractability: A Guide to the Theory of NP-Completeness" or atleast a chapter in "Introduction to Algorithms - by Cormen, Rivest" to see how reduction actually works. Some of them are really cool and mind boggling techniques.

Random C++ tricks - GDB, Valgrind and Makefile

2008-04-07T15:32:00.003-04:00

1. Perfect programming is hard - even the best programmers make mistakes.
2. A line of code that you haven't tested is a line of code with a bug.

Cardinal rule for debugging: If you are using gcc or g++, compile your program with -g option.
(Btw, to link a library with gcc, you use -l option. Eg: to link math library, use:
gcc filename -o outputfile -lm)

Segmentation Faults:

Any access outside that area (memory area assigned to the program) will cause a segmentation fault.

Common mistakes of segmentation faults:
1. Deferencing
a. NULL
b. an uninitialized pointer
c. a pointer that has been freed (or deleted, in C++) or that has gone out of scope (in the case of arrays declared in functions)
2. writing off the end of an array
3. Calling a recursive function that uses all of the stack space (On some systems, this will cause a "stack overflow" report)

Attacking segfaults:

1.a Deferencing NULL

$gdb myPgm core
The core file contains all the information needed by GDB to reconstruct the state of execution when the invalid operation caused a segmentation fault.

It will o/p:

Some copyright info
Core was generated by `myPgm'.
Program terminated with signal 11, Segmentation fault.
Some information about loading symbols
#0 0x0804838c in foo() () at myPgm.cpp:4
4 *x = 3;

This tells us that the execution stopped inside the function called foo() on line 4, which happened to be the assignment of the number 3 to the location pointed to by x.

(gdb) list
1 void foo()
2 {
3 char *x = 0;
4 *x = 3;
5 }
6
7 int main()
8 {
9 foo();
10 return 0;
(gdb) print x
$1 = 0x0

A little complicated eg: execution crashing inside a system call or library function (perhaps because we passed an uninitialized pointer)

#0 0x40194f93 in strcat () from /lib/tls/libc.so.6
(gdb) bt
#0 0x40194f93 in strcat () from /lib/tls/libc.so.6
#1 0x080483c9 in foo() () at t.cpp:6
#2 0x080483e3 in main () at t.cpp:11

so now we are in strcat stack but we want to see variable that was passed to strcat:

(gdb) up
#1 0x080483c9 in foo() () at t.cpp:6
6 strcat(x, "end");
(gdb) print x
$1 = 0x0

A common mistake is to not check the return from malloc to make sure that the system isn't out of memory. Another common mistake is to assume that a function that calls malloc doesn't return NULL even though it returns the result of malloc. Note that in C++, when you call new, it will throw an exception, bad_alloc, if sufficient memory cannot be allocated. Your code should be prepared to handle this situation cleanly, and if you choose to catch the exception and return NULL inside a function that ordinarily returns a new'ed pointer, this advice still holds.

1.b Deferencing an uninitialized pointer
Figuring out whether or not a pointer has been initialized is a bit harder than figuring out whether a pointer is NULL. The best way to avoid using an uninitialized pointer is to set your pointers to NULL when you declare them (or immediately initialize them).

You might need to figure out if 0x4025e800 is valid memory. One way you can get a sense of this in GDB is by printing out the addresses stored in other pointers you've allocated. If they're fairly close together, you've probably correctly allocated memory. Of course, there's no guarantee that this rule of thumb will hold on all systems.

In some cases, your debugger can tell you that an address is invalid based on the value stored in the pointer.

(gdb) print x
$1 = 0x1e <out of bounds>
(gdb) print *x
Cannot access memory at address 0x1e

1.c Dereferencing Freed Memory
This is another tricky bug to find because you're working with memory addresses that look valid. The best way to handle such a situation is again preventative: set your pointer to point to NULL as soon as you've freed it.

Another form of this bug is the problem of dealing with memory that has gone out of scope.

char *return_buffer()
{
char x[10];
strncpy(x, "a string", sizeof(x));
return x;
}

This is a really tricky bug to find because once again the memory address will look valid when you print it out in GDB.

If that pointer is causing you trouble, check the function and look for whether the pointer is pointing to a local variable in the function. Note that it is perfectly fine to return a pointer to memory allocated in the function using new or malloc, but not to return a pointer to a statically declared array (e.g., char x[10]).

2. writing off the end of an array
Valgrind will help you catch this bug on dynamically allocated arrays. See point 2 below.

Trick:
If notice that some of your variable values are changing periodically and unexpectedly. This is a tough bug to crack; one option is to set up your debugger to watch a variable for changes and run your program until the variable's value changes. Your debugger will break on that instruction, and you can poke around to figure out if that behavior is unexpected.

(gdb) watch [variable name]
Hardware watchpoint 1: [variable name]
(gdb) continue
...
Hardware watchpoint 1: [variable name]

Old value = [value1]
New value = [value2]

This approach can get tricky when you're dealing with a lot of dynamically allocated memory and it's not entirely clear what you should watch.

3. Stack overflow:
To diagnose a stack overflow in GDB, typically you just need to do a backtrace. If you find a single function call piling up an awfully large number of times, this is a good indication of a stack overflow.

(gdb) backtrace
#0 foo() () at t.cpp:5
#1 0x08048404 in foo() () at t.cpp:5
#2 0x08048404 in foo() () at t.cpp:5
#3 0x08048404 in foo() () at t.cpp:5
[...]
#20 0x08048404 in foo() () at t.cpp:5
#21 0x08048404 in foo() () at t.cpp:5
#22 0x08048404 in foo() () at t.cpp:5
---Type to continue, or q to quit---

Typically, you need to analyze your recursive function to make sure that all the base cases (the cases in which the function should not call itself) are covered correctly.

Other cool tricks with gdb:
We discussed bt, p (print), list, up

To set a breakpoint, type break <line number>
<line number> can be <sourcefile>:<line number>

Use n (or next) to progress through the loop one line at a time, r to run the program and c to continue.

There is also another set of commands, although they are not very commonly used; these commands actually modify the program as it is running. The call command, for example, will call a particular function; the set variable command will set a variable in the program to a particular value, for example, set variable i = 0. Return will make the current function return to the caller.

Using valgrind:

1. Finding memory leaks:
Compile your program with -g option.

$valgrind --tool=memcheck program_name

If number of allocs and the number of frees will differ in o/p, the try

$valgrind --tool=memcheck --leak-check=yes --show-reachable=yes program_name

O/p is somewhat like:

==pid== 100 bytes in 1 blocks are definitely lost in loss record 1 of 1
==pid== at 0x1B900DD0: malloc (vg_replace_malloc.c:131)
==pid== by 0x804840F: main (myPgm.c:5)

This means that there is a memory leak at line 5 in myPgm.c

2. Finding invalid pointers:
Warning of form:
'Invalid read of size X'or 'Invalid write of size X'
where X is the amount of memory we try to read.

Eg: if you allocate an array with malloc or new and then try to access a location past the end of the array:

int main()
{
char *x = malloc(10);
x[10] = 'a';
return 0;
}

$valgrind --tool=memcheck --leak-check=yes --show-reachable=yes program_name

This will give o/p:

==pid== Invalid write of size 1
==pid== at 0x804841E: main (myPgm2.c:6)
==pid== Address 0x1BA3607A is 0 bytes after a block of size 10 alloc'd
==pid== at 0x1B900DD0: malloc (vg_replace_malloc.c:131)
==pid== by 0x804840F: main (myPgm2.c:5)

3. Detecting the use of uninitialized variables:
Warning: 'uninitialised' value(s)

Eg:

int foo(int x)
{
if(x < 10)
{
printf("x is less than 10\n");
}
}

int main()
{
int y;
foo(y);
}

o/p:

==pid== Conditional jump or move depends on uninitialised value(s)
==pid== at 0x8048366: foo (myPgm3.c:5)
==pid== by 0x8048394: main (myPgm3.c:14)

4. Other improper use of memory:

4.a: If you call free twice on the same pointer value, Valgrind will detect this for you; you'll get an error:

Invalid free()

This is also called "double free attack":

free(x);
/* code */
free(x);

The easiest way to avoid it is simply to set your pointer to point to NULL once you've freed it:

free(x); x = NULL;
/* code */
free(x);

4.b: free should be matched with corresponding malloc. Similarly, delete with new and delete[] with new[].
If you do mismatch, you will get following error:

Mismatched free() / delete / delete []

What won't Valgrind find?
Valgrind doesn't perform bounds checking on static arrays (allocated on the stack).
Eg:

int main()
{
char x[10];
x[11] = 'a';
}

Valgrind won't alert you!

Also, if you don't test for buffer overflows by using long input strings, Valgrind won't tell you that your code is capable of writing over memory that it shouldn't be touching.

------------------------

Some common bugs in C/C++:
1. Uninitialized variables
2. Using a single equal sign to check equality:
while(x='Y') { ....}
3. Extra Semicolons:

int x;
for(x=0; x<100; x++);
Do something with x;

4. Overstepping array boundaries (especially if it static array):

int array[10];
//...
for(int x=1; x<=10; x++) do something with array[x];

-------------------------
Make file: Simple eg:

CC = gcc
FILES = in_one.c in_two.c
OUT_EXE = out_executable

build: $(FILES)
$(CC) -o $(OUT_EXE) $(FILES)

clean:
rm -f *.o core

rebuild: clean build

Advanced eg:
1. $@ is the name of the target.

client: client.c
$(CC) client.c -o $@

server: server.c
$(CC) server.c -o $@

List of dependents
$? - more recent than the target(i.e., those that have changed since the last time make was invoked for the given target)
$^ - all dependencies, regardless of whether they are more recent than the target, but removes duplicate names
$+ - like $^, but it keeps duplicates
$> - first dependency

Wildcard Matching in Targets (percent sign, %)
When a % appears in the dependencies list, it replaces the same string of text throughout the command in makefile target. If you wish to use the matched text in the target itself, use the special variable $*.
Eg:

%.c:
gcc -o $* $*.c

Implicit Targets

.c:
$(CC) -o $@ $@.c

This rule says that for any target that corresponds to a .c file, make should compile it using the name of the implicit target as the output, and the name plus the .c extension as the file to compile.

Replacing Text
To specify that OBJ is equivalent to SRC, except with the .c extension replaced with a .o extension:

OBJ = $(SRC:.c=.o)

Visit CProgramming.com for more details

Poem: The Road Not Taken by Robert Frost

2008-02-09T11:14:00.000-05:00

Poem:

TWO roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.
I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and
I took the one less traveled by,
And that has made all the difference.

Explanation and interpretation:
1. One possible interpretation of this poem can be summarized by Keating's quote from "Dead Poet Society" (movie) :
"We all are driven by conformity; difficulty in maintaining our own belief. We all have great need for acceptance, but you must trust that your belief are unique, even though others may think they are odd or unpopular."

2. The Road Not Taken seems to illustrate that once one takes a certain road, there's no turning back, although one might change paths later on, they still can't change the past.

Remembering names of Indian states

2008-01-31T21:51:00.000-05:00

If someone asked us, how many states is India divided into ? Probably most of us won't be able to answer that. Even worse, what if we are asked to enumerate them.

Here is a simple way to remember all the states:

Btw, India is divided into 28 states and six union territories (Andaman-Nicobar, Daman-Diu, Chandigarh, Delhi, Dadara-Nagar Haveli, Lakshadeep and Pondicherry)

I have 3 mnemonics (Also see mnemonic for Periodic table)

(Ignore vowels)
1. JK par game kar ke Tao West Bengal gaye
(Jammu Kashmir, Punjab Rajasthan, Gujarat Maharashtra, Karnataka Kerala, Tamil Nadu Andra Pradesh Orissa, West Bengal)

Goa is below Maharashtra :)

2. HP hara MAC jhab UP UK gaye
(Himachal Pradesh, Harayana, Madhya Pradesh Chattisgarh, Jharkhand Bihar,Uttar Pradesh, UttarKhand)

Sikkim separates 1,2 from 3

3. Arun & Megha Assam trip mi nagmani ko dekha
(Arunachal Pradesh, Meghalaya, Tripura, Mizoram, Nagaland Manipur)

Computer Problem Solving

2008-01-22T17:37:00.000-05:00

I found this interesting pic about "How to be Computer Genius". Funny and sarcastic :)

Microsoft Interview

2008-01-13T15:54:00.000-05:00

I had an interview for internship at Microsoft. I was interviewed by SQL Server Analysis Services and SQL Server Reporting Services (I got offer from both :) ).

I was briefed by my recruitment coordinator at building 19. I had my interviews in building 34 and 35.

My interview questions were pretty easy. Here are some of them:
1. Write a program to create a balanced binary tree from a sorted array of integer.
>> Find the middle element. Make it root. recursively call the function for left and right subarray with root->left and root->right respectively.

2. Write a program to find angle between clock's minute and hour hand
>> assert(h >= 0 && m >=0)
return ( abs( 0.5*((h%12)*60 + m%60) - 6*(m%60)));

3. Consider there are 2 types of characters:
1byte character - has value less than 128
2 byte character - whose first byte has value >= 128
Given a random pointer in a byte array find the previous character

I was asked to solve the simpler version of the problem: i.e I was given the pointer to beginning of array.
>> Start from beginning of array till pointer (also keep track of prev character), if value <> 1 byte character. Goto next byte.
If value >= 128, => 2 byte character, move 2 bytes.

Lets assume if I was not given the begin pointer:
>> Assuming turing tape: the problem has atleast 1 non halting solution. Consider, tape filled with 128. :)

4. Given a string, reverse first n characters in each word of the string.
Eg: if string is "abcd ef"
and n =2 => o/p: "badc fe"
and if n =3 => o/p: "cbad ef" (if less than n characters, donot reverse)

5. Some probability based questions: 3 types of ball in bag with equal probability. Some of the atleast, atmax kind of questions. I am sure almost everyone has solved these type of questions in their undergrad.

6. Problem with Concurrent Reader, Exclusive Writer (CREW):
A writer may wait forever.
How to solve it?
Assign reader_priority = writer_priority = normal
When number of readers exceeds a threshold, --reader_priority
When writer writes and if reader_priority < normal, ++reader_priority

If reader_priority < norm, and if a reader comes, it will wait if there is writer waiting in the queue.

My suggestions:
Be confident. Revise Data Structures and Algorithms. Write few programs for practice.
Also talk to interviewer, clarify assumptions and state your algorithm before starting to write on the white board. Always check for boundary conditions (this is where most candidates get filtered).

Why it is impossible to find miss perfect ?

2007-11-20T16:45:00.000-05:00

Lets define miss perfect to be X

Number of people in World = 6,602,236,753

Number of females in World = 3,278,621,042 (I am straight)

Lets say we would expect X to be between 20-24 age
Number of females in World between 20-24 = 2,79,407,178

Demographic probability (This is my personal view - I am an Indian)
X from Indian = 0.6
X from US = 0.3
X from other places = 0.1 (since US and India are only places I have been, hence this is low probability)

Population of females between 20-24 age:
India = 48,812,664
US = 10,240,823
Other = 220,353,691

Therefore, eligible females = 0.6 * 48,812,664 + 0.3 * 10,240,823 + 0.1 * 2,20,353,691 = 54,395,214

I also want X to be beautiful (physical characteristics - I wont go into details) and intelligent.

Lets consider normal distribution with variance = 1 and mean = 0.

Females having "really" perfect physical attributes can be estimated to be 2 deviations above norm. Hence 2.275%
But lets say, this is not a stringent factor and increase this to 20%

Intelligence - I dont expect X to be very very intelligent, lets say 1 deviation above norm. Hence, 84,135%

Also, X should not be already committed and also must like me.

X not already committed = 50% (Since we are considering females in age 20-24)
X who also likes me = 15.86% (Since she is beautiful, and I am not very fun kind of guy - why do u think I am still writing this post ?? :))

Therefore, eligible females = 54,395,214 * 0.2 * 0.84135 * 0.5 * 0.1586 = 7,25,840

Assuming if I go to blind date with new girl every week (I am quite conservative and shy - So probabilty of this happening is 0.1. But for sake of argument, lets assign it probability 1), it would take me 7,25,840 weeks

1 year = 52.177 weeks

Therefore, number of years to find X is 7,25,840 / 52.177 = 13,911 years

Life expectancy in US is 77.8 years (I highly doubt that ;-) )

Therefore, either I or her will be dead before we fall in love. Hence, it is impossible to find "Miss Perfect".

(Please note: I have considered females with age 20-24, but as I grow older, i might want to go with females of similar age. However, this makes problem more difficult. Hence, I assumed age bracket 20-24)

(All above data is as per 20th November. Almost all data is collected from http://www.census.gov/

This post is based on paper by Tristan Miller, German Center of AI)

BEING IN TWENTIES - SOMETHING

2007-10-22T22:53:00.000-04:00

I got this interesting forward from one of my friend:

It is when you stop going along with the crowd and start realizing that there are many things about yourself that you didn't know and may not like. You start feeling insecure and wonder where you will be in a year or two, but then get scared because you barely know where you are now. You start realizing that people are selfish and that, maybe, those friends that you thought you were so close to aren't exactly the greatest people you have ever met, and the people you have lost touch with are some of the most important ones. What you don't recognize is that they are realizing that too, and aren't really cold, catty, mean or insincere, but that they are as confused as you. You look at your job... and it is not even close to what you thought you would be doing, or maybe you are looking for a job and realizing that you are going to have to start at the bottom and that scares you. Your opinions have gotten stronger. You see what others are doing and find yourself judging more than usual because suddenly you realize that you have certain boundaries in your life and are constantly adding things to your list of what is acceptable and what isn't. One minute, you are insecure and then the next, secure. You laugh and cry with the greatest force of your life. You feel alone and scared and confused. Suddenly, change is the enemy and you try and cling on to the past with dear life, but soon realize that the past is drifting further and further away, and there is nothing to do but stay where you are or move forward. You get your heart broken and wonder how someone you loved could do such damage to you. Or you lie in bed and wonder why you can't meet anyone decent enough that you want to get to know better. Or maybe you love someone but love someone else too and cannot figure out why you're doing this because you know that you aren't a bad person. One night stands and random hook ups start to look cheap. Getting wasted and acting like an idiot starts to look pathetic. You go through the same emotions and questions over and over, and talk with your friends about the same topics because you cannot seem to make a decision. You worry about loans, money, the future and making a life for yourself... and while winning the race would be great, right now you'd just like to be a contender! What you may not realize is that every one reading this relates to it. We are in our best of times and our worst of times, trying as hard as we can to figure this whole thing out... We call it the "Quarter-life Crisis."

FATE DETERMINES WHO COMES INTO OUR LIVES.....HEART DETERMINES WHO STAYS

Mixing DOS and Unix

2007-09-19T00:19:00.000-04:00

I wrote a java program using Notepad in Windows and when I opened it in vi editor on unix machine, I got ^M character at end of each line.

Eg:
import java.io.*;^M
^M
/**^M
*^M
*This class is used to manage the o/p stream of the application.^M
* ^M
*@author Niketan Pansare^M
*@version 1.0 ^M
* ^M
*/^M
public class OutputManager^M
{^M
OutputStream outputStream; ^M
^M
/**^M
* This constructor uses standard i/o as default stream.^M
*/^M

and so on ...

You can replace all the extra ^M in vi editor by:
1. Go in command mode (Press Esc - If you already are in command mode, you will hear a beep)
2. Then type
:%s/^M$//g
Don't copy and paste above lines. To add ^M, press (CTRL+V) + (CTRL+M) ie ^V+^M

What does above command mean:
For substitution you use following command
:[range]s/[pattern]/[string]/[options]

's' here mean substitute a pattern with a string.

range can be
{number} an absolute line number
. the current line
$ the last line in the file
% equal to 1,$ (the entire file)

You can also use # instead of / as seperator.

Technically you can define pattern as:
The definition of a pattern: *search_pattern*

Patterns may contain special characters, depending on the setting of the
'magic' option.

*/bar* */\bar*
1. A pattern is one or more branches, separated by "\|". It matches anything
that matches one of the branches. Example: "foo\|beep" matches "foo" and
"beep".

2. A branch is one or more pieces, concatenated. It matches a match for the
first, followed by a match for the second, etc. Example: "foo[0-9]beep",
first match "foo", then a digit and then "beep".

3. A piece is an atom, possibly followed by:
magic nomagic
*/star* */\star*
* \* matches 0 or more of the preceding atom
*/\+*
\+ \+ matches 1 or more of the preceding atom {not in Vi}
*/\=*
\= \= matches 0 or 1 of the preceding atom {not in Vi}

Examples:
.* .\* matches anything, also empty string
^.\+$ ^.\+$ matches any non-empty line
foo\= foo\= matches "fo" and "foo"

4. An atom can be:
- One of these five:
magic nomagic
^ ^ at beginning of pattern, matches start of line */^*
$ $ at end of pattern or in front of "\|", */$*
matches end of line
. \. matches any single character */.* */\.*
\< \<> \> matches the end of a word */\>*
\i \i matches any identifier character (see */\i*
'isident' option) {not in Vi}
\I \I like "\i", but excluding digits {not in Vi} */\I*
\k \k matches any keyword character (see */\k*
'iskeyword' option) {not in Vi}
\K \K like "\k", but excluding digits {not in Vi} */\K*
\f \f matches any file name character (see */\f*
'isfname' option) {not in Vi}
\F \F like "\f", but excluding digits {not in Vi} */\F*
\p \p matches any printable character (see */\p*
'isprint' option) {not in Vi}
\P \P like "\p", but excluding digits {not in Vi} */\P*
\e \e */\e*
\t \t */\t*
\r \r */\r*
\b \b */\b*
~ \~ matches the last given substitute string */~* */\~*
  A pattern enclosed by escaped parentheses */*
(e.g., "$^a$") matches that pattern
x x A single character, with no special meaning,
matches itself
\x \x A backslash followed by a single character, */\*
with no special meaning, matches the single
character
[] \[] A range. This is a sequence of characters */[]*
enclosed in "[]" or "\[]". It matches any */\[]*
single character from the sequence. If the
sequence begins with "^", it matches any
single character NOT in the sequence. If two
characters in the sequence are separated by '-', this
is shorthand for the full list of ASCII characters
between them. E.g., "[0-9]" matches any decimal
digit. To include a literal "]" in the sequence, make
it the first character (following a possible "^").
E.g., "[]xyz]" or "[^]xyz]". To include a literal
'-', make it the first or last character.

If the 'ignorecase' option is on, the case of letters is ignored.

It is impossible to have a pattern that contains a line break.

Examples:
^beep( Probably the start of the C function "beep".

[a-zA-Z]$ Any alphabetic character at the end of a line.

\<\I\i or $^\|[^a-zA-Z0-9_]$[a-zA-Z_]\+[a-zA-Z0-9_]* A C identifier (will stop in front of it). $\.$\|\. $ A period followed by end-of-line or a space. Note that "$\. \|\.$$" does not do the same, because '$' is not end-of-line in front of '\)'. This was done to remain Vi-compatible. [.!?][])"']*$$\|[ ]$ A search pattern that finds the end of a sentence, with almost the same definition as the ")" command. Technical detail: characters in the file are stored as in memory. In the display they are shown as "^@". The translation is done when reading and writing files. To match a with a search pattern you can just enter CTRL-@ or "CTRL-V 000". This is probably just what you expect. Internally the character is replaced with a in the search pattern. What is unusual is that typing CTRL-V CTRL-J also inserts a , thus also searches for a in the file. {Vi cannot handle characters in the file at all}

Seems complex ??
Let us stick to our example for time being.

$ mean end of line
Therefore, ^M$ mean any ^M character at end of line.
It is supposed to be replaced by nothing (since in our example, string is empty).

g at end mean "global"

Good Interviews

2007-08-17T21:53:00.000-04:00

Here is a blogger who wrote emails to some "good" programmers, and posted their humble replies:
http://www.stifflog.com/2006/10/16/stiff-asks-great-programmers-answer/

There is another interview worth mentioning (with Denis Ritchie, Bjarne Stroustrup and James Gosling): http://www.gotw.ca/publications/c_family_interview.htm

First Week @ Gainesville

2007-08-13T20:40:00.000-04:00

I landed in US on 6th August, 2007 at JFK New York Airport. Since I had next flight to Atlanta in about half an hour, I had to actually run with my checking bag. Fortunately, I caught my flight on time. I had to wait for few hours at Atlanta.

Atlanta to Gainesville was exciting experience. Only plane going to Gainesville had big rotator, and some of the passengers had to go and sit in the front of the plane to maintain the balance of the plane. After flying in Boeing 777 from India to Atlanta and then asked to catch this plane, I was really annoyed, and probably a bit scared (plane oscillated in air :-) )

People in Gainesville are really very nice and polite. If you ask for direction and if the person doesn't know, he/she actually apologizes !!!

Another strange thing I noticed is the way people drive around here. Distance between cars is huge (I can actually park my car in that :) ). Also pedestrian are allowed to pass before at the turn.

Florida is quite hot. But still i love it !!!

Tech Savvy way of organizing ur notes

2007-07-29T15:18:00.000-04:00

If u have Microsoft Office Enterprise 2007 and a Tablet PC, you have brand new way of organizing your notes.

In One Note ( which comes along with Microsoft Office Enterprise 2007), you can record audio/video, make notes using stylus (u can use diff colours - hence can make a mindmap)

If you still prefer to study on paper, you can always take a printout

Positive points of this approach:
1. Organized in one place - hence very useful while commuting (if u r used to ebooks, its like carrying ur entire library, colour pens and notes along with u to college/home/office).
2. Can make easy backups (even store them permanently on Internet).
3. Can easily be integrated with Outlook (hence managing contacts/to do list/emails - very easy).
4. Writing on it ~ to writing on book (since stylus is magnetic, therefore placing ur hand over screen wont create a problem, but it may take some time to adjust)

Negative points:
1. Tablet PC - quite costly - (Price of Laptop with same config + 10 to 20k extra).
2. (If u like to study on paper), printer will add to ur cost.
3. What if ur tablet PC crashes and u dont have backup ???
4. Everything is not integrated (ie email, calendar, notes, etc...)

What I plan to do -
1. I already have a Laptop (hence buying tablet would be waste of money) which I will use for ebooks. I will prepare my mindmaps on papers and take pics using DigiCam or will use scanner. (therefore it will allow me to take backups of my mind maps easily (See: http://niketanpansare.googlepages.com/mindmaps)).
2. Taking printouts is very costly for Student and I prefer my mindmaps on paper rather than on PC.
3. Once I start working / earning, I will prefer this option as I will rarely use my mindmaps for more than half hour (I have worked as Software Developer and I know that u dont get time to revise ur mindmaps, nor can u carry them to ur office. Other than time, there is another factor - Uncertainty - u wont know for sure which Mindmap will u need today (unlike exams in college days))

Change of the blog title

2007-05-14T10:50:00.000-04:00

I have changed the title of the blog from "Let's Educate the literate" to "Gyanam Paramam Dhyeyam (Knowledge is the Ultimate Goal)".

"Gyanam Paramam Dhyeyam" is IIT Bombay's motto.

Here is their logo:

Please note: "I am not an IITian".

But I like their motto, that is why I choosed it (I don't think they have copyright over this motto and if they do, I hope they don't sue me :-)).

Wave Particle Duality - Animated video

2007-05-09T14:47:00.000-04:00

Double Slit Experiment:

An animated video explaining Wave-Particle duality principle.

Quantum Flatland

According to String theory, "There are 11 dimensions". Though it cannot be demonstrated, it can explain many phenomena (quantum events, but I suppose people can use it to explain "time travel" and unproven experiences like after-death experience, GOD and ghosts) using mathematical equations. Should we dismiss them as hoax or should we accept them without experiencing them?

It is my personal opinion that "human time-travel" is not possible. (I think it is difficult for human body to sustain huge acceleration required for time travel).

Scheme and Factorials

2007-04-10T11:34:00.000-04:00

I am currently working of Scheme. I decided to try out few programs on factorial and factorial like products.

If you have a mathematical definition, you can easily write its Scheme equivalent procedure (I cannot prove this statement).

--------------------------------------

(define (factorial n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (* (factorial (- n 1)) n))
)
)

---------------------------------------

Multifactorial

(define (multifactorial n k)
(cond ((and (<= 0 n) (< k =" 2)"> n 0)) n)
((= n 0) 1)
(else (* (multiplelevelfactorial (- n 1) m) (multiplelevelfactorial n (- m 1))))
)
)

To test:
Superfactorial (k = 2) of 4 is 288
Superduperfactorial (k = 3) of 4 is 6912

---------------------------------------

(define (power a b)
(cond ((= b 1) a)
(else (* a (power a (- b 1))))
)
)

(define (hyperfactorial n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (* (power n n) (hyperfactorial (- n 1))))
)
)

To test:
Hyperfactorial of 4 is 27648

---------------------------------------

All above procedures are recursive.

Linear iteration for calculating factorial would result into faster results.

(define (factorial n)
(fact-iter 1 1 n)
)

(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product) (+ counter 1) max-count)
)
)

If n is very large number and you can use Stirling's approximation to get much faster results.

Planning for Sabbatical

2007-03-30T03:59:00.000-04:00

I am currently working for MAQSoftware and will be taking a sabbatical from next month for concentrated (hopefully J) study before my M.S. in Computer Science. Before leaving my company, I wanted to do have a concrete plan about what I am going to do for next couple of months. People around me were skeptical about this step as I was doing great at my job (I recently got a big raise and was placed on good project). So I decided to jot down the purpose and plan for the sabbatical.

Duration: 3 months

Purpose:

1. To improve my vocabulary.

2. To prepare myself for research.

3. To improve my programming skills.

4. To improve my health.

5. To enjoy life …

Plan:

Purpose number	My plan
1	1. Listen to audio of wordlist whenever I take rest (daily). 2. Give test – Big Book (daily). 3. Read my mind map book of words (weekly).
2	1. Read computer science topics and research papers and prepare mind maps. 2. Brainstorm the mind maps, use lateral thinking (ask questions – Why, How. Don’t neglect seemingly illogical conclusions). 3. Document every crazy ideas and reserve some time every month to think about them. 4. Watch technical videos and create mind maps. 5. Maintain a bibliography and document every reference (use notations) in your mind map.
3	1. Create a mind map (one for each programming language you know) that encapsulates every language constructs. 2. Maintain an online programming cookbook (best practices, code snippets, coding styles, design patterns, components, etc). 3. Also, create mind maps for standard library for each language and try to correlate them.
4	1. Yoga, Meditation (daily – 1 hour (morning)). 2. Exercise (daily – 1 hour (evening)).
5	1. Movie or hangout with friends (weekly). 2. One Trip (Goa – 10-15 days). 3. Spend more time with family.

Some important points:

1. “Preparing for research”?

2. What to do when I am bored?

· Watch technical videos.

· Go for a walk.

· Listen to music.

· Have a constructive discussion with someone (Use yahoo or telephone if the person stays far away).

· Go for a movie.

3. Work hard and follow strict discipline. I may not be the smartest or the most hard-working person, but I know one thing about myself – “I don’t give up regardless of what other people say”. I will keep on trying until I succeed. I will be defined by my work and not by my resume. It doesn’t matter if I am in the best college or if I am in the worst college.

4. We all have what Einstein had during his time - access to all patents (www.google.com/patents), 24 hours a day and a human brain. In fact, we have much more information available and also better tools to organize it than what he had. So, ideally if we all organize our information more efficiently and think more clearly and more constructively, we can better even Einstein.

What is difference between span and div tag?

2007-03-26T06:18:00.000-04:00

Recently, when I was asked to take interview, I asked a simple question that none could answer :-(
"What is difference between span and div tag?"

This prompted me to write this post.

<span> and <div> tags both allow a Web designer to style text and add other formatting attributes to their Web page.

The <span> and <div> tags are very useful when dealing with Cascading Style Sheets.

Because the <center> tag has been deprecated in HTML 4.0, it is a good idea to start using
<div style="text-align: center;">
to center the content inside your div.

<div> tags are block elements. This means they can "hold" other HTML elements, and they can be positioned anywhere on the screen. For this reason, <div> tags can be used for replacing table-based Web designs.

Unlike <div> tags, <span> tags cannot hold other HTML tags. They should only be used for inline styling of text. Consider the following code:

<span >

<p>This is some text sized at 14 pixels.</p>

</span>

This code will probably render OK in most browsers, but it is actually incorrect. Remember, since the <span> tag is not a block-level element, it cannot contain other HTML tags. The correct way to write this code would be:

<p><span >

This is some text sized at 14 pixels.

</span></p>

Since <div> tags are block elements, they create line breaks. This is the same effect as a <p> tag. <span> tags do not create line breaks, which makes them perfect for styling text in the middle of a sentence.

There are far more possible values for the display property than block and inline — in fact, the CSS 2.1 specification lists 17 different possible values. Ten of these values are related to tables and correspond to the way the various HTML table elements act.

However, IE 6/7 doesnot support "display: table"

So, simple code to display a table is rendered differently in IE and Firefox
<html>

<body>

<div style="display:table">

<div style="display:table-row ;">

<div style="display:table-cell;background: #ccc;">

Cell 1

</div>

<div style="display:table-cell;background: #aaa;">

Cell 2

</div>

</div>

<div style="display:table-row;">

<div style="display:table-cell;background: #ccc;">

Cell 3

</div>

<div style="display:table-cell;background: #aaa;">

Cell 4

</div>

</div>

</div>

</body>

</html>

IE 7 renders it as:

Firefox renders it as:

Your browser will display above code as:

Cell 1

Cell 2

Cell 3

Cell 4

(Refer
Decloak.com for comparison between <table> and <div>tags for displaying tabular data

and Quirksmode.org for compatibility of browsers for display property).

Issues with javascript:void(0)

2007-03-14T00:52:00.001-04:00

There are plenty of occasions when coding JavaScript events where you simply need to call a function, for which an entire event registration model is too lengthy. The most commonly used method is to bind your event to an anchor link. The user clicks and the onclick event is fired, calling a reference to a function.

Because the user isn’t actually visiting a URL, something has to be done with the href attribute.
There are 2 options:

Use href="#"

Not finding a name (anchor link) after the pound, the browser “kicks” the user to the top of the current page, losing the location in the document.

Use href="javascript:void(0);"

Lets go with second option:

<a onclick="someMethod('userControlName')" href="javascript:void(0);">Click Here</a>

I tried to load user control in someMethod('userControlName'). It was working in IE7 and Firefox but not on IE6.

After investing into it a little bit, I found out a simple solution:

><a onclick="someMethod('userControlName'); return false;" href="javascript:void(0);">Click Here</a>

“return false” stops any other action after the person has finished the onClick action. This prevented event bubbling action (For excellent article on Event bubbling, see quirksmode.org )

Find and Replace Dialog in Visual Studio

2007-02-06T06:29:00.001-05:00

Recently, I was working with a prototype of web application. Since I was building a prototype, I simply used table utility in Word 2007 to create table and used its formatting to create nice looking tables.

I simply copy-pasted it in design view of Visual Studio in my ASP.NET web project.

This worked fine for small prototype. Problem is that this create internal stylesheets for each <td>, <tr>, <p>,...

When I was asked to convert this to external stylesheets, it created a lot of problems (since I had to remove all internal style="…" attribute from each tag and associate with similar class from external stylesheet).

I had to remove some 1500 style attribute in a particular page. Then regular expression feature of Find Replace Dialog in Visual Studio came to my rescue.

Also, I faced a strange problem. After replacing style=:q with empty string, I still had some 1000 style attributes that were not replaced. The problem was attributes like

style="font-size: 12pt; color: black; font-family: 'Cambria','serif'; mso-ascii-theme-font: major-latin;

mso-fareast-font-family: 'Times New Roman'; mso-fareast-theme-font: major-fareast;

mso-hansi-theme-font: major-latin; mso-bidi-font-family: 'Times New Roman'; mso-bidi-theme-font: major-bidi;

mso-themecolor: text1"

was not replaced since they were multi-line. I had regular expression style=("([^"]\n)*") to replace these attributes.

Lessons learnt:

Regular Expression make Find Replace dialog very powerful.
Never use Word 2007 (though it allows you to rapidly develop professional looking tables) in your ASP application

What is Research?

2007-01-31T00:57:00.001-05:00

READING:

Books are not scrolls.

Scrolls must be read like the Torah from one end to the other.

Books are random access -- a great innovation over scrolls.

Make use of this innovation! Do NOT feel obliged to read a book from beginning to end.

Permit yourself to open a book and start reading from anywhere.

In the case of mathematics or physics or anything especially hard, try to find something anything that you can understand.

Read what you can.

Write in the margins. (You know how useful that can be.)

Next time you come back to that book, you'll be able to read more.

You can gradually learn extraordinarily hard things this way.

Consider writing what you read as you read it.

This is especially true if you're intent on reading something hard.

I remember a professor of Mathematics at MIT,

name of BERTRAM KOSTANT,

who would keep his door open whenever he was in his office, and he would always be at his desk writing.

Writing. Always writing.

Was he writing up his research? Maybe.

Writing up his ideas? Maybe.

I personally think he was reading, and writing what he was reading.

At least for me, writing what I read is one of the most enjoyable and profitable ways to learn hard material.

STUDYING:

You are all computer scientists.

You know what FINITE AUTOMATA can do.

You know what TURING MACHINES can do.

For example, Finite Automata can add but not multiply.

Turing Machines can compute any computable function.

Turing machines are incredibly more powerful than Finite Automata.

Yet the only difference between a FA and a TM is that

the TM, unlike the FA, has paper and pencil.

Think about it.

It tells you something about the power of writing.

Without writing, you are reduced to a finite automaton.

With writing you have the extraordinary power of a Turing machine.

THINKING:

CLAUDE SHANNON once told me that as a kid, he remembered being stuck on a jigsaw puzzle.

His brother, who was passing by, said to him:

"You know: I could tell you something."

That's all his brother said.

Yet that was enough hint to help Claude solve the puzzle.

The great thing about this hint... is that you can always give it to yourself !!!

I advise you, when you're stuck on a hard problem,

to imagine a little birdie or an older version of yourself whispering

"... I could tell you something..."

I once asked UMESH VAZIRANI how he was able,

as an undergraduate at MIT,

to take 6 courses each and every semester.

He said that he knew he didn't have the time to work out his answers the hard way.

He had to find a shortcut.

You see, Umesh understood that problems often have short clever solutions.

There will come a time when you work on a problem long and hard but UNsuccessfully :(

And then you learn that someone else found a solution.

See this as the GREAT opportunity it is to learn something important.

Don't let it pass you by.

Ask yourself: "How SHOULD I have been thinking to solve that problem?"

I have found that doing so is a powerful exercise.

Danny Sleator tells me that BOB FLOYD independently recommended exactly this exercise to his students.

He would lead them into asking themselves:

"How COULD I have led myself to that answer?"

Take the time to think it through.

It's worth it.

There will come a time when you work on a problem long and hard and SUCCESSFULLY :)

And then you learn that someone else already published. :(

Hard as that may be for you to take, you must view this too as a great opportunity.

Don't turn off. Read what got published.

You will be surprised how often the published paper turns out to be different in some significant way. Roughly

50% of the time, it is NOT at all the same as what you did.

25% of the time, it is the same but not as good.

25% of the time it is better.

This means that 50% of the time or more, you can still publish.

And what about the 25% time that what got published is better than your own?

In that case, you have a great opportunity to learn.

Ask yourself: "How SHOULD I have been thinking to solve the problem in this fine way?"

This is how I discovered, as a young engineer, that I should learn something enormously powerful called "Modern Algebra."

It's one reason I switched from Electrical Engineering as an undergraduate major to Mathematics as a Graduate major.

Of course, this was before there existed anything called Computer Science.

Still on THINKING...

The importance of PARADOX and CONTRADICTION.

When you can prove that a statement S is true,

and you can prove that the same statement S is false,

then you KNOW that that you're on to something:

Something is wrong somewhere.

Never underestimate the power of a contradiction.

It is one of our most potent sources of knowledge.

Examples include the Liar Paradox "This statement is false." with its applications to Set Theory and our understanding of language.

There are the seeming paradoxes of countability and uncountability,

In CS, there is the apparent paradox that leads to The Halting Problem.

Physics has lots of paradoxical material:

Quantum Theory. The Einstein-Rosen-Podulsky Paradox.

The relativistically speeding Twins.

The wave and particle nature of matter.

Here's an ASIDE on my current work, also based on paradox:

I am personally interested in the Paradox of consciousness. Compare the following two views:

1. the view that the human is a MECHANISM, an automaton

with substantial but finite internal memory, programmed like

any computer to do whatever it does, and/or

2. the view that the human is a thoughtful observant

creature with a God-like free will; that it is a CONSCIOUS

ENTITY at the controls of a highly complex highly capable

mechanism, choosing what to do from among options served up

by/from its vast unconscious below.

In my view, both these views are correct. How can that be?

In his "Life of Johnson," James Boswell quotes Samuel Johnson

as saying:

"All theory is against the freedom of the will; all experience

is for it."

Johnson was 18 years old when Newton (age 85) was buried.

Johnson knew that F=MA implied that humans are mechanisms.

"All theory is against the freedom of the will; all experience

is for it."

This ends my ASIDE.

Make a list for yourself of good ways to pursue a problem.

My own favorite is to try small examples. By comparison,

DAVID GRIES's favorite is to put himself in the middle

of a (presumed) solution. An example is his coffee can problem:

Given a can of black and white coffee beans, do the following: Pull out two beans: if both are the same color, replace them with a white bean. If the two are different, replace them with a black bean. What color is the last bean?

Or try out the two methods on the Hershey Bar problem

[Give an optimal algorithm to break an mxn Hershey bar into

1x1 pieces. At each step, you can choose a single rectangle

of chocolate and crack it along one of its vertical or

horizontal lines. A single crack counts one step. You are to

make the fewest number of cracks]

Brains are muscles.

They grow strong with exercise.

And even if they're strong, they grow weak without it.

In the months before Kasparov lost to Deep Blue,

his mother came after him.

She was worried that he wasn't spending enough time

exercising himself (on chess).

Her worries proved well-founded.

THE PhD: GETTING STARTED

I remember a great summer job I once had at IVIC

(Instituto Venezolano de Investigaciones Cientificos).

A top neurophysiologist, name of Svaetichin, gave me a splendid problem... one that I unfortunately could not solve.

The problem was to find a way to focus light on a single cell

of a goldfish retina so that the light would not spill over

onto any of the adjacent cells.

Svaetichin had tried making a pinhole in a sheet of black tin,

and shining his light thru the hole. This worked for moderate size holes, but failed for really small holes, which caused the light to diverge, to form diffraction patterns.

Since Svaetichin couldn't solve the problem, I decided I couldn't. Or perhaps it's that I thought his problem physically unsolvable. In retrospect, I should have taken out books on physics, especially optics, read as much as I could, talked to others and kept on talking to him.

Svaetichin would have helped me if I had shown him I was reading thinking working.

Don't expect your thesis advisor to give you a problem that he or she can answer. Of course, she might.

* She might give you a problem to which she already knows an answer.

* She might give you a problem that she thinks is answerable,

but that she hasn't actually answered.

* She might give you a problem that is deadly hard.

* If the problem she gives you is hard enough,

I suggest you look for a NONSTANDARD answer.

More on this later after I get done cooking the thesis advisor.

Your thesis advisor may encourage you to work in an area

that she feels completely comfortable in... in which case you can rely on her for sage advice and sound guidance.

Or she may encourage you to work on something she knows little or nothing about, in which case it will be up to you to inform and teach her.

In the latter case, you will have to learn all you can for yourself...

You will have to learn from other faculty, from courses, from books, from journals. from peers.

Both kinds of advisors can work out for you.

I don't know that one is necessarily better than the other.

But you should know which you got.

Whatever you do, you got to like doing it....

You got to like it so much that you're willing to think about it, work on it, long after everyone else has moved on.

THE PhD: DEEP IN THE MIDDLE OF IT.

There's a wonderful quote from ANATOLE FRANCE:

"A University Student"

-- and this is especially true for a PhD Student --

"should know something about everything

and everything about something."

You know the jokes about PhD's...

A PhD knows more and more about less and less

until he knows everything about nothing.

When working on a PhD, you must focus on a topic so narrow that you can understand it completely.

It will seem at first that you're working on the proverbial needle, a tiny fragment of the world, a minute crystal,

beautiful but in the scheme of things, microscopic.

Work with it. And the more you work with it, the more you penetrate it, the more you will come to see that your work, your subject, encompasses the world.

In time, you will come to see the world in your grain of sand.

To see a world in a grain of sand

Or a heaven in a wild flower,

Hold infinity in the palm of your hand

And eternity in an hour.

WILLIAM BLAKE (1757-1827)

This gorgeous quartet is followed by a large number of sometimes deep sometimes questionable aphorisms, which I see much like the occasionally grinding work of a PhD thesis.

There's all kinds of research you can do.

There's research to prove what you know to be true.

There's research -- maybe better called SEARCH -- to figure out what is true.

Some of the best such search succeeds in DISPROVING

what you initially believed to most certainly be true.

For example, Sir Fred Hoyle is said to have coined the phrase "Big Bang" at a time when he was looking to disprove it.

For a relatively minor but personal example:

When I was working on the MEDIAN problem,

my goal was to prove that any deterministic algorithm to find the MEDIAN of n integers must necessarily make roughly as many comparisons as it takes to sort n integers, i.e. n log n comparisons.

I was shocked to discover that the median of n integers can be found with just O(n) comparisons.

When working on proving some statement S true,

you should spend at least some time trying to prove it false.

Even if it's true, trying to prove it false can give insight.

And in any case, too often, our intuition is dead wrong.

There is yet another sense in which, when working on a hard problem, you may find that the answer is NOT what you expected.

You may be looking for a YES or a NO; it may be something else.

Some years ago, JOHN HOPCROFT gave one of his PhD students the problem of deciding the Equivalence of Free Boolean Forms.

The specifics don't matter.

The problem appeared as an open problem in Garey and Johnson.

The question was: Is the Equivalence problem NP-complete?

Or is it solvable in poly time?

Chandra, Wegman and I found a randomizing algorithm for this problelm. At the time this seemed to beg the question entirely. Only after writing it up did we really understand that we had given an efficient albeit randomizing algorithm to solve it, This shows, by the way, that the problem is not NP-complete if NP <> RP (Randomizing Poly-time), as seems likely.

Of course, this brings up the question whether P = NP.

The question of our time: Are NP-complete problems solvable in poly time?

Could anything I have said today be useful for so hard a problem as that?

Probably not. Nevertheless...

LEONID LEVIN believes as I do that whatever the answer to the P=NP? problem, it won't be like anything you think it should be. And he has given some wonderful examples.

For one, he has given a FACTORING ALGORITHM that is proVably optimal, up to a multiplicative constant.

He proves that if his algorithm is exponential,

then every algorithm for FACTORING is exponential.

Equivalently, if any algorithm for factoring is poly-time,

then his algorithm is poly-time.

But we haven't been able to tell the running time of his algorithm because, in a strong sense, it's running time is unanalyzable.

Maybe as STEVEN RUDICH suggests, the P=NP? problem is undecidable in the standard formalization of Mathematics.

The point is that the answer may not lie where you expect it. Here's a poem I wrote when I wondered at the fact that we must sometimes be dragged kicking and screaming in the right direction.

It's a comparison to the blind spot in our eyes,

which isn't really blind but makes things up for us.

It questions whether there might not be other things in this world that our brains, our minds, by their very nature, make up for us:

Blind Spots mb 15-MAY-96

All men have Blind Spots in their eyes,

That manufacture visions of their vale.

And shape that void where light's unregistered,

With bold-faced unrepentant tales.

What other blind spots shape our minds and thoughts?

What other tales do won'dring minds unfurl

To woo us unbeguiled we would believe

To strange and nonexistent worlds?

ABOUT WRITING:

Here is the one quote that I have found most helpful and wise:

"First have something to say,

Second say it,

Third stop when you have said it,

and

Finally give it an accurate title."

JOHN SHAW BILLINGS [1838-1913]

MY ADVICE TO YOU:

Don't expect your thesis advisor to read your thesis. Some thesis advisors can and do give good feedback, but not all.

Still, make sure that SOMEBODY reads your thesis...

I especially recommend that you ask your peers.

Here's another piece of advice that I have often had to give myself, and I here give you...

When you send a paper off to be published,

and it gets rejected...

Don't be turned off by the mindless cretinous feedback

that you get to your well-thought-out beautifully-written work!

Be a MENSCH. Use the feedback to improve your paper!

Make it better. And send it back.

Finally, it is my most earnest wish that you should know something that is honestly amazingly true of you... That you are each of you UNIQUE and SPECIAL in some glorious way.

I wrote a poem to capture this, which I now use to end my sermon. It's called "Fundamentals."

FUNDAMENTALS

mb 05-JUN-96

Bird must soar. Skunk must stink.

Cat must prowl. Man must think.

What sets man apart from beast is his engine of

thought. His mind. His

BRAIN

makes him unique

and gives him his greatest pleasure.

But fundamental as is thought for human beings,

there is stuff more basic still that underlies and

DRIVES

not only man

but all great beasts,

And that is nature's call to each of us... to be special.

To be distinguished in some way. To be

UNIQUE.

To BE something, to DO something, BETTER than everyone else.

Like the leather nosed chimpanzee,

dragging noisy cans and branches,

frightening peers into submission,

One does not have to be brilliant, a genius, to be special.

To do something better than anyone/everyone else. To be

UNMATCHED,

One has only to choose an END

any END

that MATTERS

that INSPIRES

YOU

And then DO IT.

By, Manuel Blum.

(http://www.cs.cmu.edu/~mblum/research/pdf/grad.html)

Manuel Blum (born 26 April 1938) is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking". Blum attended MIT, where he received his Bachelor's degree in 1959, his Master's degree in 1961, and his PhD in 1964. He worked as a professor of computer science at the University of California, Berkeley until 2000. He is currently the Bruce Nelson Professor of Computer Science at Carnegie Mellon University.

Code Obfuscator

2007-01-17T23:39:00.000-05:00

One of the key architectural features of Microsoft .NET is that all its languages compile to .NET assemblies containing CPU-independent instructions. These instructions, known as Microsoft Intermediate Language (MSIL), contrast with many other languages that generate CPU-specific instructions for the target CPU. .NET assemblies are comprised both of MSIL instructions and also metadata that describe types, members, and code references from other assemblies. At runtime, the MSIL instructions are converted to CPU-specific instructions by a just-in-time (JIT) compiler.

The use of this architecture has several huge benefits for the .NET developer. For instance, it makes possible easy interoperability for code written in differing languages, and it makes it easy for an assembly to specify exactly the version of another assembly with which it will work. But there is one major drawback for some developers as well: the MSIL and metadata in an assembly provide enough information to recover the original code. The .NET framework ships with a tool, ILDASM that can disassemble MSIL into assembly language and other utilities can carry the process even further, translating a .NET assembly back into a high-level language such as C# or Visual Basic .NET.

This is a drawback because it is very difficult to protect the intellectual property in an application if anyone can read the source code for the application. Developers, who have spent months or years coming up with complex algorithms or workarounds for bugs in the .NET Framework, or other components, often prefer to have their methods remain secret from their competitors.

This is where obfuscators come in. The purpose of an obfuscator is to apply one or more transformations to a .NET assembly without affecting the proper functioning of the assembly, but that make it difficult or impossible to understand any source code recovered from the assembly. As a simple example, every obfuscator offers some level of member renaming. Source code where all of the objects are named things like A, B, and C instead of Customer, ClientData, and ServiceUpdate, is substantially more difficult to understand.

How to obfuscate?
Simplest way – Use Macro preprocessors to create hard to read code by masking the standard language syntax and grammar from the main body of code.

Pitfalls:
Although obfuscation is a valuable technology in many circumstances, you do need to be aware of some potential pitfalls:
1. Obfuscation can break code that depends on reflection, serialization, or remoting.
2. Obfuscation can make diagnosing and debugging problems in your code more difficult.
3. Obfuscation adds another step and another potential error source to your build process.

Obfuscation in Visual Studio .NET:
If your obfuscation needs are minimal, and you're a Visual Studio .NET user you may not need to purchase a product at all. That's because Visual Studio .NET includes a copy of the Community Edition of Dotfuscator for .NET, an obfuscator from PreEmptive Solutions. This obfuscator is targeted at students and freeware authors, and supports basic entity renaming and removal of unused metadata, but no advanced obfuscation features.

Recreational obfuscation:
Code is sometimes obfuscated deliberately for recreational purposes. There are programming contests which reward the most creatively obfuscated code: the International Obfuscated C Code Contest, Obfuscated Perl Contest, International Obfuscated Ruby Code Contest and Obfuscated PostScript Contest.
There are many varieties of interesting obfuscations ranging from simple keyword substitution, use/non-use of whitespace to create artistic effects, clever self-generating or heavily compressed programs, or programs that are valid and operate similarly in multiple programming languages.

Points to note:
No obfuscator known today provides any guarantees on the difficulty of reverse engineering: See http://www.math.ias.edu/~boaz/Papers/obf_informal.html
Hackers can use this technique to foil anti-virus programs that rely upon a virus having a static signature. The technique also allows spammers to hide their intentions. See: http://www.itbusiness.ca/it/client/en/Home/News.asp?id=41807&bSearch=True

ClickOnce Deployment

2007-01-09T07:13:00.000-05:00

Visual Studio provides two different strategies for deploying Windows-based applications: publishing an application using ClickOnce technology, or deploying it with a traditional Setup using Windows Installer technology. With ClickOnce deployment, you publish the application to a centralized location and the user installs or runs the application from that location. With Windows Installer deployment, you package the application in a setup.exe file and distribute that file to users, who run the Setup.exe file to install the application.

ClickOnce deployment greatly simplifies the process of installing and updating an application, but you do not get the power of Windows Installer deployment, which provides you with greater flexibility.

ClickOnce deployed applications are self-updating and are the best choice for applications that require frequent changes. Although ClickOnce applications can be initially installed by means of a CD-ROM, users must have network connectivity to take advantage of the update capabilities.

With Windows Installer, you add a Setup project to your solution to create a setup file that is distributed to users; the user runs the setup file and steps through a wizard to install the application.

Creating ClickOnce application:

Create normal windows or console application.
Then, right click on it and click on Publish.
This will prompt you to specify a Web site or network file share.
The user installs and launches the application directly from that location in a single step.

However, you don't have flexibility of custom install in ClickOnce application. This is crucial feature that I miss the most. However, updating functionality is great.

If your application does not require custom install actions and if you have hosting space, I will advise you to try this feature.