Wow that was quite an experience, I have been looking at sites like Hacker News, Reddit and DZone for years but to see my own post go to #1 on Hacker News and rise high on Reddit and DZone was quite a thrill, with over 70K hits at the time of this writing. It has completely changed my life the phone is ringing off the hook with endorsement offers, it looks like I will only be wearing Nike for the next year.

The best part was the over 200 comments on my Blog, Hacker News, and Reddit, it spawned some spirited discussion on all three locations and many people added their own equations some that I was unfamiliar with and I learned a few new things, excellent! The various discussions for the most part were great and very enjoyable and I’d like to thank everyone who contributed. In the post I commented that I wondered how I would feel about the list in a year and I already think I would change the list by one equation. I was tempted to respond to the comments on all of the forums, I know I should at least respond on my own blog, I just figured I’d do it as a post that way I could hit a number of topics.

One thing that people objected to was the title, which induced some inferences in the tone of the title. One redditer summed it up as:

Someone presuming, yet again, to know what "every" Computer Scientist should know? A title like "my favourite computer science equations" might be better. This list contains a lot of ideas which are only relevant in very narrow domains.

Yes, probably on the title comment, but the title was an intentional "spoof" if you will of a title of an article on Wired, and if you read my post you would have gotten that. Actually I confess that you might even accuse me of "Hacker News Post Popularity Hacking" as I saw the Wired post rise up and figured that there was a high probability that a similar CS related post could achieve a similar placement, actually I think it exceeded my expectations and went even higher, it shot to #1 in under two hours of my submitting it and it stayed on the front page for almost a day. I felt the tone I was setting, by using the term "rip off" and the Spinal tap joke (This one goes to eleven) that I don’t think anyone got, was subtly light hearted, perhaps it was too subtle. I recall reading that the title is key to getting people to read posts, and clearly this title was somewhat controversial which probably helped it, actually most of my titles are fairly boring or references that make them less popular, but I generally title things the way want not for popularity, well with this one exception.

Another thing that people took umbrage with was the use of the equations, as I just explained since I had set my title accordingly my format was now set. One commenter, in two different comments on a thread on Hacker News added:

I think this is a pretty silly post, to be honest. CS covers so much, and everytime I see a list of "things you should know", I have to resist the urge to roll my eyes and ignore it. But then I read it, and inevitably roll my eyes anyway.

...

I disagree. Programming is math. Highly advanced math, in fact. It's just a different type of math. And the 11 equations in the OP's article just barely touches on what CS is about. There is far more to it than that.

I mostly agree with this commenter. I admit that the sentiment that this not really about the equations but the general domain knowledge is implied, again perhaps too subtle. At one point someone mentions memorizing these equations which again means you are missing the point. It’s about knowing what these equations mean and how to use them. I feel that the math domain knowledge for our field is growing and becoming more important. Do I use any of this for my day job? Well no, but I hope to one day. As to the broad domain I actually have a post "Math For Programmer TNG" that covers a very broad domain of math that I think is potentially relevant. Also not all areas of math are going to be used in every math related job.

As to the narrowness insinuated by the two comments above, the post touched on the following domains: Combinatorics, Logic, Boolean Algebra, Set Theory, Lattice Theory, Probability Theory, Statistics, Category Theory, Number Theory including Complex Numbers, Relational Algebra, Abstract Algebra, Linear Algebra, Shannon Information Theory, Algorithmic Information Theory, Kolmogorov complexity, Graph Theory, Formal Language Theory, Automata Theory, Combinatory Logic, Lambda Calculus, Machine Learning, Data Mining, Encryption, Limits, Topology, Fourier Analysis and The Simpsons. Not exactly narrow, or am I missing something here? In fact the list was picked in part for diversity.

The Pumping Lemma turned out to be fairly controversial, I do admit that the Pumping Lemma was perhaps a bit "contrived" as an Equation and as one person put it: "that's the most hideous formulation of the pumping lemma I have ever seen". That formulation came from Wikipedia. As I mentioned I really did want something from Formal Language Theory or Automata Theory and it’s not so much about determining which language is regular but knowing the difference between a Regular Language and a Context Free Language so that you are not the cargo cult coder who tries to parse html with regular expressions because you understand these distinctions. I think the following exchange summed up what I was going for:

(except the Pumping Lemma, WTF?)

Reply:"Seriously, you never learnt theoretical computer science? As in, theory of computation? Automata theory? Complexity theory? Nothing like that?"

There were a number of comments about the use of mathematical notation including the following:

"Shannon's Information Theory, Eigenvector, DeMorgan's Laws, etc. None of those names are meaningful or descriptive. And then the greek letters and made up symbols. Math could learn something from Computer Science:

"https://www.google.com/search?q=readable+code

This commenter seemed to have an issue with the actual names of things in math. I found this to be very narrow minded. Math is many things including being a domain of knowledge, that’s like complaining about the names: Ytterbium in Chemistry, Bose–Einstein Condensate in Physics, Borneo in world Geography, or Impressionism in art. Really!?!

Now the complaints about the notation are more understandable but still unreasonable in my opinion, math in some respects is a language, perhaps somewhere between a natural language and programming language, it has a notation and to really be able to understand it you need to learn this notation (language). Someone remarked that symbols were "unfriendly". Well I find Chinese, Arabic^{1}, etc. to consist of unfriendly symbols, but that’s because I don’t know them. Also like natural languages you have inconsistencies, and multiple meanings for symbols. One person complained about my notation for the Set version of De Morgan's laws, this may be a nonstandard notation, I saw it in some course notes on probability and set theory and I liked it and I just used it without thinking about it. I do think it’s more elegant. This makes a good point about math. If you learn it and read from diverse sources you will encounter notational differences. This has been my experience, in fact if you look on the Wikipedia page for De Morgan's laws you will find the following example from Modal Logic:

I am used to the notation used in Hughes and Cresswell:

That’s just how things work. You can get hung up on it and complain or you can accept it and move on. Don’t get me wrong it would be nice if there was a notational standard that every one followed for all math.

Like natural languages Math has its equivalences of "Homographs", for example the following symbols can have multiple context dependent meanings: |b| can mean absolute value of b if it is a number or cardinality of b if it is a set or length of b if it is string, ∂ can mean Partial Derivative or Topological Boundary, and as we saw ∧ and ∨ can mean meet and join or "logical and" and "logical or".

Just as Math has "Homographs", as in natural languages it also has its equivalences of "Polysemes", meaning that there are multiple ways to express the same ideas. For example set difference can be expressed as (S – T) or (S \ T), the Powerset notation can be either 2^{S} or P(S), and meet and join can be expressed as the either of the following sets of symbols:

The list of both math "Homographs" and "Polysemes" is much longer.

For De Morgan's laws, someone added the following generalization using the Existential and Universal Quantifiers, which is really interesting and also illustrates the duality:

It's not much of a generalization, but I prefer the predicate version of De Morgan's:

~∀x p(x) ≡∃x ~p(x)

~∃x p(x) ≡∀x ~p(x)

If you read the Wikipedia Article it includes this generalization as well:

The above equations do generalize De Morgan's laws within Logic and Set Theory respectively but my point was to further generalize them in terms of Lattices which is a different concept all together and gets at the deeper intuition about the interrelation of Logic and Set Theory, quoting from __Combinatorics the Rota way:__ by Rota and Kung, an amazing book I am trying to read, emphasis on the word trying:

"As John Von Neumann put it, the theory of Boolean Algebras is "pointless" set theory.

This set version would be written using the complement exponentiation notation as follows:

I really do prefer this notation, I originally encountered it in "Introduction to Probability Theory" by By Ali Ghodsi and Cosmin Arad, lecture 1(pdf). This notation is also used in __Combinatorics the Rota way__. So this notation is now the official notation of my blog, get used to it or hit the road. ;)

A commenter (who was also the demorgans notation complainer) responded with the following:

...

For the rest, they seem more likely to be used by someone doing something related to machine learning/AI/information theory than you run of the mill I-spend-all-day-parsing-user-input programmer.

Thank you for making me feel like I'm not a 'true' computer scientist. Next would you like to tell me about how I'm not a 'man' because I don't like to work on cars?

Well I hate to break it to you, but if this list makes you feel that way then chances are you are like me: a software developer with a CS Degree and that does not make you or me a Computer Scientist. This is from Wikipedia:

"The general public sometimes confuses computer scientists with other computer professionals having careers in information technology, or think that computer science relates to their own experience with computers, ...

Oh, and yes you are not a man if you do not at least know how to change your oil, including the filter. ;)

Also a number of people remarked that I did not explain the equations in enough detail and I did not provide code examples. It was meant as high level post, if I were to explain all of these equations the post would have been excessively long, maybe even a whole book. As to the code examples again it would be too long, if you want code examples that relate to math, I have posts for that, I recommend the following posts on my blog, some were linked in the original post: "O(log(n))", "Triangles, Triangular Numbers, and the Adjacency Matrix", "The Combinatorial and Other Math of the Java Collections API", "Math You Can Use : Refactoring If Statements with De Morgan's Laws", and "Monoid for the Masses".

Regrettably some people responded with the sentiment of: I’m not good at math or that math is too hard, I don’t think I can get a CS degree. Fortunately there were a number of comments of encouragement to counter these sentiments, my favorite was this one:

Don't let this be intimidating to you - instead of asking yourself "how come I don't know this?" ask yourself "how can I learn more about this?". This might sound cheesy and simplified but it's as simple as "nobody was born knowing this". I'm 31 and I wish I had the money to go back in education and learn all of this with the official way but for now I'm just picking resources on the web and who knows? It just might happen...

I have a post planned to talk about my experiences and thoughts about learning math, I will say if you are a programmer you are doing math in a sense. You just need to formalize your understanding of the underlying concepts. If it is any consolation I find Math to be very hard at times, I pretty much suck at it in the traditional sense, but it is so beautiful and when you grok a concept, at least for me, it is an incredible buzz. Every new concept that you learn changes how you see everything, I see so much math in programming and the world now it’s scary, I just wish I could figure out how to express it. Everything is math. Over the last few years my ability to understand things has greatly increased and continues to do so. Yes it’s hard but it is so worth it.

A number of commenters added their own equations to the discussion, and this was the best part, which included a few new things for me. In general my list was mostly directed at more pure math oriented equations that I felt were fairly central to a specific discipline and encapsulated certain principles. Here are a few recommendations and thoughts:

One person pointed out the absence of P=NP or P ≠ NP, to which I would respond "D’oh!" If I was doing this over I might even replace the Pumping Lemma with P=NP.

One poster recommended triangular numbers:

Here's a real simple and practical equation: 1+2+3+4 . . . N = N(N+1)/2

This equation represents the number ofedges on a complete graph with N+1 vertices or the number of possible pairings given N+1 objects. Useful whenestimating O(N) for certain algorithms that involve comparing an item to everyother item in a set.

I love Triangular Numbers and this is a great equation, I wrote a whole post "Triangles, Triangular Numbers, and the Adjacency Matrix" on exactly what he is mentioning, and considered that equation but rejected it because triangular numbers are sort of a special case of the Binomial Coefficient equation:

Here are some of the other equations and theorems that were suggested, I wouldn’t really consider these because they didn’t fit my theme and criteria but that doesn’t mean they aren’t interesting:

One commenter accused me of shoehorning in Euler’s Identity. This is partially true. He also accused me of "Name Dropping". That’s not true. A defender supplied the following course notes:

Analytic Combinatorics: A Primer

I followed up on that and found that you can download a copy of Analytic Combinatorics:

by Flajolet and Sedgewick. Warning: pretty advanced stuff.

As the popularity of my post was waning on Hacker News a math oriented post called "Fuzzy string search" was making its way up the ranks. It’s an interesting post and I think it helps illustrate a couple of points I have been making here, first of all it uses mathematical notation, which is not uncommon when writing about these types of topics. Additionally the post includes the equation for the Triangle Inequality:

An equation that crossed my mind when writing my equations post. It is not the equation itself, but the concept, if you become familiar with the idea of a Metric or Metric Spaces, you instantly recognize this equation concept without having to read the associated text, not that you shouldn’t read the associated text. Knowing these ideas gives you the ability to better understand more complex ideas that are based on these concepts. I think this is the case in all knowledge domains. Also I noticed that there was not one comment on that post complaining about math notation.

A lot of what went on is part of an ongoing conversation, I blogged about it in "The Math Debate" which links to other famous blogs of the same ilk. Ultimately the equations probably don’t apply to most programming jobs, the title contained as some commenters pointed out "Computer Science Geeks" not "Corporate Software Developers". A few people castigated the commenters who seemed to be advocating positions of ignorance, thanks, BTW. I personally find it tragic, the following comment sums this up:

"Someone with a CS degree who knows nothing of De Morgan's law should have their credit removed and be demoted to making websites or performing tech support tasks.

Reply: "There goes 98% of your CS graduates then. I wish I was joking, but alas.."

Of course it’s a bit I ironic that as I am wrapping this up, "A co-Relational Model of Data for Large Shared Data Banks" by Erik Meijer, Gavin Bierman just popped up on Hacker News, the relevant quote is:

Every programmer is familiar with the two dual forms of De Morgan’s laws

The writing quality of the post was criticized. I don't know what people will think of this post, I feel like I just wrote a clip show. I admit that previous post was not my best effort, while it was fun putting it together it was not easy, I had hoped to learn all of the equations in more detail, I did to some degree, I confess I still don’t fully get the Y-Combinator, but I will. I finally decided to just push it out and move on. This post, while being relevant to my mission of blogging about math was something of a social experiment in popularity, it was interesting but I will be returning to the true mission of my blog which is my journey through math and the pursuit of a real Software Engineering discipline.

Ultimately I am interested in the readers, like a young colleague of mine who was too busy to comment because he was following the links to learn new things he didn't know, not the complainers and naysayers. There were many positive comments and again, thanks. I did feel a needed to refute some of the negative comments. The bottom line is if you want to read about math, you need to get used to the notation, it probably won't help you to build CRUD Web apps but it will hopefully help you take your career to the next level.

^{1}Actually this is not true I find them to be quite beautiful, especially Arabic.

See also the discussion on Metafilter

ReplyDeleteResponding towards those of the notation will also bring about an idea of how you can follow out those of the guidelines that could certainly be more and more inspiring. Also the good logical points have been taken here. research papers writing

ReplyDelete