Rob Pike wrote 30 lines of codes to realize a simple regular expression matcher in his book The practice of Programming. This piece of code is really cool. Let's take a look at the code.Meaning of different characters.CharacterMeaningcGeneral character.Match any single character^Match start of a string$Match end of a string*Match zero or many occurrences of a character/*match ：Test the regexp in text*/int match(char* regexp,char* text){    if(regexp[0] == '^')        return matchhere(regexp+1,text);     do{ /*Check the strin...

Discrete mathematical structures form the foundation of computer science.These structures are so universal that most research papers in the theory of computation, programming languages and formal methods present concepts in terms of discrete mathematics rather than code.The underlying assumption is that the reader will know how to translate these structures into a faithful implementation as a working program.A lack of material explaining this translation frustrates outsiders.What deepens that frustration is that each language paradigm encodes discrete structures in a distinct way.Many of the e...

Some friends asked this question: In secondary schools we participate in the NOI, in university we participate in ACM/ICPC, TopCoder.What's the significance of coding competition to actual work?I participated in the NOI from 1994 to 1996, ACM/ICPC from 1999 to 2000 and TopCoder in 2002 for six months. Later I paid little attention to coding competition, so I may not understand the changes in recent years and race mode .The capabilities we can get by participating the competition can be summarized below:1, Basic technical skills. People who participate in the competition and get good results sh...

This idea is a complete rip off an article that appeared in Wired a little while ago and it got me thinking what would my list for Computer Science look like?  Plus I thought it might be a fun post and unlike the Wired list this one goes to eleven.  So here they are in no particular order:Binomial CoefficientThe Binomial Coefficient equation generates Pascal’s Triangle and gives you the coefficients for the Binomial Theorem these ideas are often attributed to Pascal but in fact they have been known in part for over a millennia.As I mentioned that this list is no particular ord...

I love to profile applications, because I always learn something that surprises me.Initial Profiler Surprise: Client SideCase in point, I was recently profiling our Android application, the Famigo Sandbox. This app sends a lot of data back and forth with our API, as we try to determine which of the apps on your phone are safe for your kids. I always assumed that, if app performance suffered during some of the chattier features, it was probably due to slow cell reception.The profiler told me that I was wrong; the tran...

Math breakthroughs don't often capture the headlines--but MIT researchers have just made one that could lead to all sorts of amazing technological breakthroughs that in just a few years will touch every hour of your life. Last week at the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) a new way of calculating Fast Fourier Transforms was presented by a group of MIT researchers. It's possible that under certain situations it may be up to ten times faster than the current way we do these. At this point you are probably wo...

The Fourier transform is one of the most fundamental concepts in the information sciences. It’s a method for representing an irregular signal — such as the voltage fluctuations in the wire that connects an MP3 player to a loudspeaker — as a combination of pure frequencies. It’s universal in signal processing, but it can also be used to compress image and audio files, solve differential equations and price stock options, among other things.The reason the Fourier transform is so prevalent is an algorithm called the fast Fourier transform (FFT), devised in the mid-1960...

I like C, but I have to admit that, sometimes, “The Old Man of Programming” can be a bit of a killjoy. This is one of the most exciting eras in computer history, but lately, C’s acting like he doesn’t evenwant to have a good time. While the cool kids like Ruby and Haskell are living it up, C’s over in the corner obsessing over bits and bytes and memory alignment and pointers and the stack and machine architecture and unreachable allocations and multiple indirections…and it’s…kind of a buzzkill. You want to tell him, “Dude! Lighten ...