Simple explanation of P versus NP problems.

Hi mom! Okay, this is it! First, sit down, take a deep breath. Have some tea. This is gonna hit you hard. Okay, here goes.

People have found out that some problems are much easier to solve with a computer than others. They have given names to groups of problems depending on how hard or easy they are. Makes sense? Okay.

The first group of problems is called P. Problems in P can be solved by a computer in a reasonable amount of time. Example: sorting a list of names is not so much work for a computer. You can remember it like this: "Easy PEE-sy!" right?

Not much to say about those. They're the boring run of the mill problems. We are going to look at the interesting stuff.

The next group, called NP, contains problems for which a computer can quicklycheck a proposed solution. So all P problems are also NP problems: if you can solve it, you can check it, but not necessarily the other way around. So you can remember NP like this: "NOPE! Not so easy!" An example of an NP problem is: "Given this city map, is there a route of length X that visits all these addresses"? Given such a route, it's easy to check, but it's not easy to find one.

Okay mom, this was sort of reasonable, right? But now it gets a little weird. Because as it turns out, there are some problems that we don't know how to solve efficiently, but if we could, then we could use the solution to immediately solve all other problems in NP. This holy grail of computing is called the group of NP-hard problems. Finding a route of length X via a set of addresses is an example of an NP-hard problem: it would be extremely cool if someone were able to figure out how to do it efficiently (but don't hold your breath). If you figure out how to solve an NP-hard problem efficiently you will be a millionaire. Everyone will want to touch you. For real!

Some NP-hard problems are so hard, their solutions cannot even be checkedefficiently; so confusingly these problems are not always in NP themselves.  To rule those bad boys out, people call the group of NP-hard problems that are still easy to verify "NP-complete" problems.

Okay mom. Now I know you really want to run away and do something real. But you can't yet, because I still have to tell you about the biggest mystery in computer science, which is this: no-one knows if the picture I have just drawn for you is correct: no-one knows if there are NP-complete problems that are not also in P! Everyone is completely and utterly convinced that these exist, but no one has been able to prove it. Chew on that!
--
Steven de Rooij
https://www.quora.com/What-is-an-explanation-of-P-versus-NP-problems-and-other-related-terms-in-laymans-terms

Bill Gates says software bots will eventually take jobs away in 20 years. What do people think?

Disclaimer: this post is copy-pasted from Quora!

When is the last time you used a travel agent to book a flight?  Bots are already here.

I should also add that my profession is becoming automated. Newspapers like the LA Times are using bots to 'write' stories involving sports results and financial reports. They are virtually indistinguishable from similar reports written by bipeds. Fortunately they haven't invented a Snark Bot or I'd be out of a job.

Any job involving forms processing. As paper shuffling turns into pixel shuffling, there's less and less need for a human to be involved.

What's your credit score? That's determined by an algorithm. Back in the day, a human being had to decide if you were a worthy credit risk.

Life insurance rates? Once upon a time, insurers relied upon actuarial tables built by bipeds. Not anymore.

Also: Planes. Commercial airliners are flown almost entirely by robot, save for take off and landing (and even the latter is mostly automated).

Tl;dr: There are a ton of jobs being performed today by algorithms that used to be done by humans. More are coming. Hope yours isn't one of them.

Ref,

http://www.quora.com/Bill-Gates-says-software-bots-will-eventually-take-jobs-away-in-20-years-What-do-people-think

FUNctional Programming

What is functional programming? What is the difference between this new topic and other programming languages? Why the hell do we need to learn this functional programming? What is this logo talking about?

If this is the first time you hear this concept, you may have the above questions in your mind as I encountered for the first time I heard about "FUNctional Programming" (FP). As a rule of thumb, I don't want to go through the details of FP in this post, but I just want to attract your attention to this new term and answer the aforementioned questions briefly.

Here is the first answer! (without knowing what the question is).

So if you are still with me and would like to learn FP too, first look at the following taxonomy to see the classification of programming languages,

More likely, you never implemented any code in none of these languages, so determination of the type of your favourite programming language is more than welcome in the comments (this is subtle way to know if you read this post, if so you should be able to identify what the type of R is).

This is the first moral lesson we should learn from FP, "war is over", oops, I'm sorry! we have already been overwhelmed in many wars nowadays. Where were we? Aha, I just remember, FP says declaring var is over! But why? Why is it important to have this as the life motto of FP? This is what I will answer later. Let's first answer the vital question, so what on earth is FUNctional Programming? I think, it is better to be patient, if you know what FP is, then please move to the next post and if you have not known it yet, it means either you don't need to know it at all or read the rest of this post!

FP is a list of things you can't do. That's the most simple answer I have for you right now. In fact we can do many things, but we may never think what we can't do, now you can cry. At least this is more convincing for me to know what I can't do rather than knowing what I can. From the information theory point of view, this is more informative with the highest entropy so that facilitates my life. Just a moment, what that weird list could be? There you go,

• No Assignments (this is different from your homework!).
• No Varying Your Variables. (Immutable)
• No While/For Loops.
• No Control Over Order of Execution. 
• No Side Effects.
• No Mutating or changing state.

Characteristic	Imperative approach	Functional approach
Programmer focus	How to perform tasks (algorithms) and how to track changes in state.	What information is desired and what transformations are required.
State changes	Important.	Non-existent.
Order of execution	Important.	Low importance.
Primary flow control	Loops, conditionals, and function (method) calls.	Function calls, including recursion.
Primary manipulation unit	Instances of structures or classes.	Functions as first-class objects and data collections.

Looks cool! Sounds like I don't need to write any code in this fashion! But wait a moment,

Are You FUNing Kidding me? How Can Anyone Program like this ?

Good question! (this phrase reminds me someone)

"Functional Programming is so called because a program consists entirely of functions." 

- John Hughes , Why Functional Programming Matters

What a ridiculous quote! I thought a program consists of coffee :D

Now words of wisdom 

"The Language that does not affect the way you think about programming, is not worth knowing." 

- Alan Perlis

Hmmm, this one makes more sense! At least it saves my time not to learn a languRage (this is not typo! (Can anyone tell me how many exclamation mark did I use so far?!)).

But let's dive into an example,

Imperative

total = 0
i = 0
while i <= 10
  total += i
  i = i + 1
end
total

Functional

 total = (1..10).inject(:+)

I prefer to stop at this point, but I will continue this tutorial based on you feedbacks in comment section (I promise to write the next one with more appropriate syntax and semantic in a classy way), in addition to the answer of question that was raised in this post.

Have a FUNctional programming ;)

Crawling IMDB Website

Yesterday Farnoush asked me if I teach some web crawling with R in my graduate course.

Well! I thought I must do some web crawling myself first, then teach to the others. To start, you need to know some basic HTML or CSS language. These languages are somehow like Latex. HTML and CSS help to structure of a web page.

First we need some web crawling tools that reads web pages and put them in a proper R class. I suggest installing the rvest R library.

Now lets set our mission: we want to extract the rating of a movie from the IMDB website, for instance. I choose a well-known movie like “sepration” from Asghar Farhadi, an Oscar winning Iranian movie. The family name of the director matches Fanoush’s family name, a nice match, perhaps Farnoush and Asghar are relatives ;).

The IMDB webpage of the movie is here http://www.imdb.com/title/tt1832382/

> library("rvest")
> separation_movie <- html("http://www.imdb.com/title/tt1832382/") ; class(separation_movie)

## [1] "HTMLInternalDocument" "HTMLInternalDocument" "XMLInternalDocument" 
## [4] "XMLAbstractDocument"

Watch carefully! Now the object separation_movie is not only a text file downloaded from the web, it is an HTML object in R. Let’s see how we can find what we need in this HTML object. If you know some basic HTML language, you know that paragraphs are found by <p> and </p> tags. Let’s check the 15th paragraph in the HTML object:

> (separation_movie %>% html_nodes("p"))[15]

## [[1]]
## 

## A married couple are faced with a difficult decision - to improve the life of their child by moving to another country or to stay in Iran and look after a deteriorating parent who has Alzheimer's disease.
## 
## attr(,"class")
## [1] "XMLNodeSet"

Wow! the 15th paragraph of IMDB is the story of the movie. Now let’s extract the text from it

> (separation_movie %>% html_nodes("p"))[15]%>%html_text()

## [1] "\nA married couple are faced with a difficult decision - to improve the life of their child by moving to another country or to stay in Iran and look after a deteriorating parent who has Alzheimer's disease.

Well! Now let’s check if we can extract the rating of the movie from the html file. We just need to know how the movie rating is structured inside the html file. If you check the whole HTML object separation_movie you will find that span HTML tag is associated with the rating. Let’s try isolating the span then:

> separation_movie %>% html_nodes("strong span") 

## [[1]]
## 8.4 
## 
## attr(,"class")
## [1] "XMLNodeSet"

If you want to extract the rating, just isolate the text inside the HTML tag

separation_movie %>% html_nodes("strong span") %>% html_text() 

## [1] "8.4"

We can easily make a database of IMDB with stories, actors, actor photos, directors, number of ratings, and so on.

We just require to crawl the link to other movies, save their web page addresses and crawl all of our addresses to save the information of the movies.

Suggestion list

One of my hobbies is watching the cartoon! The world in which the rules are broken. also, I listen to different type of music. Approximately, perhaps: 80 % Classical, 10% Persian (classical, pop,…) and  10% the others. Sometimes I watch the movies on YouTube too.

Searching the mathematic subject on YouTube …: rarely!

What is the subject? 

Today I watched this cartoon: «iznogood» and when it finished, youtube surprised me with its suggestion list! I really confused. Statistically, how it could suggest me such an interesting subject. I loved it but I could not find any relation with the clips which I watched on youtube!

How should I start Big Data?

Many companies are apprehending the benefits of Big Data and are starting to use their data more effectively. With the benefits of Big Data, companies now have an opportunity to control the power of real-time information and use analytics to interact with their consumers in real time.

We know the advantages of Big Data: understanding your customer, improving customer loyalty and gaining competitive advantage.  I have recently started to learn Big Data. At the beginning I've asked this most popular question many times-“How should I start Big Data?”

Actually, this is a great question since there are numerous resources to learn about Big Data and it is so difficult to select one to start. Therefore I decided to write this post to share a summary of those I found.

So how do we start our journey to Big Data? Here are the five tips I recommend to help you get started.

1-Learning the tools and technologies: start with any tool that you can access to like Python, SAS, SPSS, SQL, R (which is available as open source) and try to learn it at a deep and practical level. Then you will have some knowledge and then you can search and study relevant topics as you now know a little to grow your knowledge. Remember that people with high level knowledge about one special tool are more preferable than who know a little bit about everything! So, it is strongly recommended to master one tool and a few techniques of the tool to have a better chance of getting the opportunities and accomplishing them. For example, you can try with Introduction to Data Science from University of Washington on Coursera website. Just remember to plan in right direction what tools and technologies you want to learn.

2-Learning the tricks: indeed a supplementary step to master a tools is learning the tricks of that tool from another experienced in your company or learn from professional courses. Notice that self-study courses and tutorials mostly will not provide you the key secrets and tricks which are very crucial for solving real life problems.

3-Look for an opportunity in your company to apply analytics in your organization. Mainly it is difficult to identify where to start. If you know the sources of data and where data is being collected (like some data repository) according to a certain business process then you have a good chance to use it in your first Big Data scenario. Start by generating simple insights from the data which is not presently captured in the business reports and create simple metrics which will add tremendous value to the businesses to show to the top management in your company interested in what you are doing. Remember that most organizations do not even do the most obvious understanding from a data analysis perspective.

4-Create a case study of your work and show your analytics to your superiors. If they don’t support you, devise a job search to extramural companies related to your new skills.

5-Read more and more: it is strongly recommended to join blogs and forums on Big Data, follow carefully companies in related domain and participate in the latest discussions and events in Big Data such as LinkedIn. This help you being aware of how Big Data is being applied in different business applications and functions and increase your knowledge.

Non-associative property of floating-point operations

As you may be motivated to know how come it is possible to have different values by prioritizing the addition operator according to my last post, I decided to write this post to show you the floating point operations does not necessarily have the associative property. Before dive into the details, let's start with an example,

a=0.1
b=0.2
c=0.3
M=(a+b)+c
N=a+(b+c)
print(M, digits=20)
print(N, digits=20)

More probably you will see the following results on your screen,

[1] 0.60000000000000008882
[1] 0.5999999999999999778

Surprisingly, not only the floating point operations does not necessarily have the associative property, but also the commutative property does not hold either! It is better to demonstrate this by the following example,

a=100
b=0.1
c=0.2
M=a*(b+c)
N=a*b+a*c
print(M, digits=20)
print(N, digits=20)

The following result was produced in R,
[1] 30.000000000000003553
[1] 30

In mathematics, the associative property is a property of some binary operations. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs.

Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value. 

--
Wikipedia definition

Despite, the addition operator should meet the associative property theoretically for all real numbers, floating-point operations, as defined in the IEEE-754 standard, are not associative numerically.

More specifically, on massively multi-threaded systems, the non-deterministic nature of how floating-point operations are performed inside the machine, such as the intermediate values that have to be rounded or truncated to fit in the available precision leads to non-deterministic numerical error propagation.

Floating point arithmetic is known to be non-associative since the limited precision of the representation requires intermediate values be rounded. The IEEE-754 provides uniform semantics for operations across a wide range of implementations. The standard de fines correct behavior for all operations, as well as any necessary rounding.

So if you want to implement your algorithm, or reimplement an existing algorithm and port it in another programming language, be careful about this issue.

Perpetual motion

   The idea to create a machine which don't consume any energy to work becomes from middle age centuries. As one of the most famous try we could mention the da vinci overbalanced wheel. Anyway, this idea has been rejected by thermodynamic rules, but the fans never stop neither the magician who earn money from their show!

   They use their creativity by adapting the main idea with the thermodynamic rules. Instead of using the term of "no energy" they decided to use an energy which they called it as “the vacuum energy”. my point is not if it is really work or not, I'm trying to show you their creativity! 

Logo de PolyStat

Bonjour à toutes et à tous,
Voici, ci-dessous, le logo de PolyStat:

Pour ceux qui n'étaient pas présents lors de la réunion où nous avons choisi ce logo, j'ajoute une petite description à propos de ce logo. Comme vous le voyez bien dans la figure, il représente des gens autour d'une table ronde disant que PolyStat est formé d'un groupe d'étudiants et de chercheurs qui se parlent de leurs idées et se réunissent afin de discuter sur leurs travaux de recherche. Les quatre couleurs du logo (rouge, verte, orange et bleue) sont celles que vous trouvez dans le logo de Polytechnique.
On s'est mis déjà d'accord sur le logo mais si vous avez d'autres suggestions pour la couleur grise dans le logo ou la police choisie pour PolyStat, n'hésitez pas à laisser des commentaires.

Simple question

Who does think that \(a+(b+c)\) is always equal to \((a+b)+c\)?
Your wrong/right answers are welcome in the comment.

Google App Inventor

I just learned that a group of researchers at MIT came up with App Inventor software for kids to write  mobile applications. At the first sight, it looks like Visual Studio.

Seems coding is getting revolutionized again, by moving from technical complicated commands, to visual and cognitive signs. I remember the time that MS Windows 3.1 pushed away MSDOS and UNIX with a similar idea. This time, the revolution is happening in the app developer level.
I was surprised with the functions that are available in the App Inventor. For instance speech recognition is a just a box! You can easily add it as a functionality to your app.

I would say that the difference between Java and the App Inventor is like R and RapidMiner.  

Une vitesse de plus de 50 km/s

Après la Lune, la prochaine destination est la planète Mars. Voyager vers Mars n’est plus un rêve ou une mission impossible. Grâce aux nouvelles technologies d’aujourd’hui, cette planète sera accessible bientôt pour l’homme.

La découverte d’un moyen de propulsion plus rapide qui pourrait changer la façon dont nous voyagerons dans l’espace est l’un des problèmes auxquels on fait face dans cette mission. Aux États-Unis les laboratoires privés se mettent à rivaliser avec la NASA et cherche à créer un moyen de propulsion plus rapide que celui des fusées d’aujourd’hui. La compagnie Ad Astra Rocket est en train de produire un moteur fusée révolutionnaire qui est entré dans sa phase finale d’évaluation. C’est une fusée magnéto-plasma à impulsion spécifique variable ou VASIMR en anglais. Son inventeur, Franklin Chang-Diaz, est un ancien astronaute avec plus de sept missions dans l’espace. Le moteur VASIMR est un nouveau dispositif qui nous permet de nous déplacer plus rapidement dans l’espace tout en consommant moins de carburants et donc de paver la voie à la conquête de tout le système solaire. 

Moteur magnéto-plasmique à impulsion spécifique variable

Lorsqu’on active le moteur, un gaz instable, l’argon, est envoyé vers la première chambre d’allumage tel qu’il est illustré dans la figure ci-dessus. Il est alors bombarder par de puissantes ondes radars qui arrachent les électrons de leurs atomes. L’argon se transforme alors en plasma, une soupe de particules dotée d’une énergie considérable. Ce plasma est ensuite canalisé vers la deuxième étape d’allumage où il atteint de millions de degrés. Là, un système d’aimant le propulse avec force vers l’extérieur à plus de 50 km/seconde. Tous les moteurs de la fusée fonctionnent de la même façon en utilisant le principe de l’action et de la réaction. Ce processus est repris mais en éliminant toute composante chimique. À la place de cette dernière, l’énergie électrique est utilisée pour chauffer l’argon à des températures extrêmes proches de celles du soleil. Donc, on ne parle pas de quelques milliers de degrés mais de plusieurs millions de degrés. Grâce à cette température, le VASIMR pourrait aller plus vite et plus loin avec beaucoup moins de carburants. À terme, ce prototype est estimé de permettre à l’homme d’atteindre la Planète Mars en moins de deux mois, soit trois fois plus vite qu’un moteur conventionnel utilisé actuellement dans les vaisseaux spatiaux. Mais ces températures incroyables sont aussi un obstacle. Le problème est que comment contenir quelque chose d’aussi chaud sans faire fondre ce qui l’entoure. Ce problème est résolu grâce à l’action de champs magnétiques très puissants. Mais une fois sortie du moteur, le plasma est un danger capable de faire fondre tout le laboratoire où le test se déroule. Pour éviter de cette catastrophe, le test ne dure que quelques minutes.  

Vaisseau spatial muni des moteurs magnéto-plasmiques à impulsion spécifique variable