## Tuesday, November 20, 2007

### Why it is impossible to find miss perfect ?

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)

## Monday, October 22, 2007

### BEING IN TWENTIES - SOMETHING

I got this interesting forward from one of my friend:
FATE DETERMINES WHO COMES INTO OUR LIVES.....HEART DETERMINES WHO STAYS

## Wednesday, September 19, 2007

### Mixing DOS and Unix

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"

## Friday, August 17, 2007

### Good Interviews

Here is a blogger who wrote emails to some "good" programmers, and posted their humble replies:

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

## Monday, August 13, 2007

### First Week @ Gainesville

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 !!!

## Sunday, July 29, 2007

### Tech Savvy way of organizing ur notes

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

## Monday, May 14, 2007

### Change of the blog title

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

## Wednesday, May 09, 2007

### Wave Particle Duality - Animated video

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

## Tuesday, April 10, 2007

### Scheme and Factorials

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.

## Friday, March 30, 2007

### Planning for Sabbatical

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

## Monday, March 26, 2007

### What is difference between span and div tag?

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

## Wednesday, March 14, 2007

### Issues with javascript:void(0)

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:

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:

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

## Tuesday, February 06, 2007

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:

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

## Wednesday, January 31, 2007

### What is Research?

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.

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.

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.

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.

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,

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.

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

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:

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.

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

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?

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]

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.

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.

## Wednesday, January 17, 2007

### Code Obfuscator

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

## Tuesday, January 09, 2007

### ClickOnce Deployment

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:

1. Create normal windows or console application.
2. Then, right click on it and click on Publish.
3. This will prompt you to specify a Web site or network file share.
4. 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.

## Monday, January 08, 2007

### Some tips about creating an installer

I am working on custom installer for deploying DTSX packages. It also includes few custom actions like creating databases, populating data, attaching dtsConfig files, etc...

Few Golden rules:
1. “Uninstall/Remove/Delete all resources during uninstall and rollback, you install using custom action”.
2. Suppress all exceptions in Rollback.
3. Validate “ALL” parameters supplied by user.
4. Create a separate file that stores all strings used by Installer for user interaction.
5. Always have a log file.
6. Not recommended: You can use MessageBox to debug your installer.

How to implement:
1. Uninstall:
Create a text file “uninstall.log”. This should ideally have list of all resources that has been installed using custom install method. It should also have additional parameters (eg username, password) that will be useful for uninstalling or removing the resources.
Rollback:
Create a flag that states whether a resources has been deployed or not. Add all parameters required in state server:
Eg: stateSaver.Add("someParameter", ParameterValue); -- in Install method
if(savedState["someParameter"] != null) // Required
string someParameterInRollback = savedState["someParameter"].ToString(); -- in Rollback method

2. Keep a general try / catch loop. This will allow you to do maximum damage control J in rollback phase.

public override void Rollback(System.Collections.IDictionary savedState)
{
base.Rollback(savedState);
try
{
//
//Rollback Action
//
}
catch (Exception exception)
{
//Suppress all exceptions
}
}

3. Keep a separate method for this functionality say “private void ValidateUserParameters(System.Collections.IDictionary stateSaver)”. It should check:
a. Whether parameter is entered or not -Context.Parameters.ContainsKey("SOMEPARAMETER")
b. Whether entered parameter is null or empty - String.IsNullOrEmpty(Context.Parameters["SOMEPARAMETER"])
c. Whether entered parameter is in valid range
Always report “all” invalid parameters. i.e. have some flag that signifies invalid parameters and an errorMessage string that you can append when you get an invalid parameters and display at end.

4. This will helpful in change management. Eg:
public const string InstallerUsage = "Usage: msiexec /i UrMSI.msi SOMEPARAMETER=\"Some Paramter Name\" ";
5. Log file will help user know whether Installer was successful or not. Also, it can help him trace the action done by installer. You can have a text log file or you can log it in application log (use System.Diagnostics.EventLog.WriteEntry()).

6. Add reference to "System.Window.Forms” and you can use all windows based forms. But remember to remove the reference while Release.

### SqlConnection, SqlCommand -- using them efficiently

SqlConnection and SqlCommand implement IDisposable, which means they could have unmanaged resources to cleanup and it is our job, the developers, to make sure Dispose() gets called on these classes after we are finished with them.

To avoid all mess, use following C# syntax :

using (SqlConnection sqlConnection = new SqlConnection(connectionString))
{
using (SqlCommand sqlCommand = new SqlCommand(commandString, sqlConnection))
{
sqlConnection.Open();
sqlCommand.ExecuteNonQuery();
}
}

This is essentially equivalent to :

SqlConnection sqlConnection = null;
SqlCommand sqlCommand = null;
try
{
sqlConnection = new SqlConnection(connectionString);
sqlCommand = new SqlCommand(commandString, sqlConnection);
sqlConnection.Open();
sqlCommand.ExecuteNonQuery();
}
finally
{
if (null != sqlCommand);
sqlCommand.Dispose();
if (null != sqlConnection)
sqlConnection.Dispose();
}

If you don't use above code and if you forget to close connection, you cannot drop a database. It will throw an error saying that database is still in use.

However, there is a way out (though not advisable) for dropping the database:

USE MASTER
GO
ALTER DATABASE DBNAME
SET SINGLE_USER WITH ROLLBACK IMMEDIATE
DROP DATABASE DBNAME

Note: above code is used to force database to delete all connection (which might cause loss of data in multi-user environment).