Review: Selected Papers on Computer Science

Book Info:

This is the most ac­ces­si­ble book from Don Knuth. Although it was pub­lished nearly 20 years ago, it still is a clas­sic com­puter sci­ence book. On Amazon, there is an in­ter­est­ing com­ment about the book from Peter Norvig (Director of Google Research). The ma­jor topic in the book is the orig­i­na­tion of com­puter sci­ence in the pe­riod in which the dis­ci­pline is a new thing. Through chapters, we can see there were many de­bates and strug­gles among sci­en­tists about whether com­puter sci­ence is truly a “science” and not a branch of math­e­mat­ics [Chapter 1, 2, 3].

This makes me think about the cur­rent state of Deep Learning. Maybe 5 or 10 years later, Deep Learning will be­come a sep­a­rate dis­ci­pline as Computer Science seg­re­gated from math­e­mat­ics sev­eral decades ago.

There are es­pe­cially in­ter­est­ing chap­ters in the book which I can de­scribe as be­low:

• Chapter 0: a gen­eral overview about Computer Science.
• Chapter 1: Computer Science and its re­la­tion to math­e­mat­ics: the dif­fer­ence be­tween mod­ern math­e­mat­ics and com­puter sci­ence. Besides, the au­thor also men­tioned the analy­sis of the clas­sic al­go­rithm: hash­ing.
• Chapter 2 and 3: The overview about al­go­rithms as well as the ap­proach by which the au­thor solves al­go­rith­mic prob­lems. Although the chap­ter is pub­lished long time ago (1976 – 77) which maybe quite new at that time, in my opin­ion these men­tioned al­go­rithm, namely the short­est paths, search­ing and com­bi­na­to­r­ial op­ti­miza­tions, be­come clas­sic re­search in CS nowa­days.
• Chapter 6 – 9: Theory and Practice: the whole book is dis­tilled into these chap­ters. His­toric text ac­tively dis­cuss the most im­por­tant as­pects in CS.
• Chapter 11 – 13: The his­tory of Computer Science: From an­cient civ­i­liza­tion uses al­go­rithms to solve prac­tice prob­lems to the very first analy­sis of John von Neu­mann about merge sort.

History of Computer Science and Deep Learning

While read­ing the book, I had the feel­ing that the pe­riod of 1950 – 1975 per­haps ex­ploded into com­puter sci­ence re­search, which is pretty much sim­i­lar to Deep Learning nowa­days. That was the time when there were few uni­ver­si­ties opened Com­puter Science de­part­ment and peo­ple still de­bated about the name of this sci­ence, whether its name is “Computer Science”, “Information Technology”, or “Information Processing”. That is also the time when peo­ple thought that the prob­lem which can only be solved on $\mathcal{O}(N^2)$ ac­tu­ally can be solved in $\mathcal{O}(N\lg N)$, the time when there were not any math­e­mat­i­cal tools for an­a­lyz­ing al­go­rithms.

How about Deep Learning?

Nowadays, peo­ple re­main skep­ti­cal about Deep Learning in many as­pects. Somebody compared it to alchemy be­cause of the lack of rig­or­ous analy­sis and math­e­mat­i­cal fun­da­men­tals. How­ever, ac­cord­ing to the cur­rent de­vel­op­ment of Deep Learning and avoid­ing the me­dia hype, I am con­fi­dent about the fu­ture of Deep Learning. At least, in my opin­ion, it will be­come an in­ter­dis­ci­pli­nary field and com­pletely trans­form into “chemistry”. In ret­ro­spect, per­haps Computer Science was com­pared to “alchemy” in the pe­riod of 1940 – 50 due to its lack of rigor.

Study about History of Computer Science

I was fas­ci­nated by the analy­ses in de­tail about “ancient” al­go­rithms as well as the elab­o­rate way to dis­cuss the draft of merge sort from John von Neumann. IMO, this re­ally is the way peo­ple should study about the his­tory of Computer Science. It is not about mem­o­riz­ing who and when al­go­rithms were cre­ated, it is about the mo­ti­va­tion and ap­proach which the in­ven­tor tack­led the prob­lem as well as an­a­lyz­ing the meth­ods in the cir­cum­stances in which the tech­nol­ogy is lim­ited. Through these in­sights, we will re­spect the con­tri­bu­tion from al­go­rithms and their au­thors. In ad­di­tion, we can gain more meth­ods, ap­proaches for other prob­lems.

Don Knuth is es­pe­cially in­ter­ested in this par­tic­u­lar sub­ject, there are many videos and doc­u­ments in which he dis­cussed ex­haus­tively:

• Let’s Not Dumb Down the History of Computer Science: it is worth every minute watch­ing. I love this com­ment from Youtube: “Discover how dis­cov­er­ies are dis­cov­ered”.
• History of pat­tern gen­er­a­tion al­go­rithms: [fasc4b]
• Hamiltonian path: [fasc8a].