Review: Selected Papers on Computer Science

Book Info:

This is the most ac­ces­si­ble of Don Knuth’s books. Although it was pub­lished nearly twenty years ago, it re­mains a clas­sic in com­puter sci­ence. 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 is the ori­gins of com­puter sci­ence dur­ing a pe­riod when the dis­ci­pline was still find­ing its foot­ing. Throughout the chap­ters, we wit­ness the de­bates and strug­gles among sci­en­tists over whether com­puter sci­ence is truly a “science” rather than merely a branch of math­e­mat­ics [Chapters 1, 2, 3].

This par­al­lel makes me re­flect on the cur­rent state of Deep Learning. Perhaps five or ten years hence, Deep Learning will emerge as a dis­tinct dis­ci­pline, much as Computer Science sep­a­rated from math­e­mat­ics sev­eral decades ago.

Several chap­ters stand out as par­tic­u­larly com­pelling:

• Chapter 0: a sweep­ing overview of Computer Science.
• Chapter 1: Computer Science and its re­la­tion to math­e­mat­ics—ex­plor­ing the dif­fer­ence be­tween mod­ern math­e­mat­ics and com­puter sci­ence. The au­thor also dives into the analy­sis of that clas­sic al­go­rithm: hash­ing.
• Chapters 2 and 3: An overview of al­go­rithms and the au­thor’s ap­proach to solv­ing al­go­rith­mic prob­lems. Although pub­lished decades ago (1976 – 77), when such ideas may have been novel, these al­go­rithms—short­est paths, search­ing, and com­bi­na­to­r­ial op­ti­miza­tion—have since be­come foun­da­tional pil­lars of CS.
• Chapters 6 – 9: Theory and Practice—the essence of the en­tire book crys­tal­lizes in these chap­ters. His­toric texts il­lu­mi­nate the most im­por­tant as­pects of CS.
• Chapters 11 – 13: The his­tory of Computer Science—from an­cient civ­i­liza­tions em­ploy­ing al­go­rithms to solve prac­ti­cal prob­lems, all the way to John von Neu­man­n’s pi­o­neer­ing analy­sis of 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 few uni­ver­si­ties had opened Com­puter Science de­part­ments 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 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].