Monday, September 4, 2017

Best Algorithms Books (Part 1)

To my fellow Texans, affected by the fury of Hurricane HarveyπŸŒ€ I dedicate this essay to you, with prayers, as we go about rebuilding our homes in our Lone Star State πŸ‡ΊπŸ‡Έ☁ ☂ 🌈 🌝 🌞 Here's how you can help people affected by Harvey πŸŽ―
An algorithm must be seen to be believed.
~ Donald Knuth
 
Despite all of our technological advances, content creation still requires time, inspiration, and a certain amount of sweat. There aren't any shortcuts. You can't write an algorithm for it. You can't predict it. You can't code it.
~ Shawn Amos
 
We live in a culture that's been hijacked by the management consultant ethos. We want everything boiled down to a Power Point slide. We want metrics and 'show me the numbers.' That runs counter to the immensely complex nature of so many social, economic and political problems. You cannot devise an algorithm to fix them.
~ Carl Honore
 
Nature doesn't feel compelled to stick to a mathematically precise algorithm; in fact, nature probably can't stick to an algorithm.
~ Margaret Wertheim
According to Greek myth, Theseus was sent into a maze to kill the minotaur. Guess what, Theseus came up with an algorithm—it involves a ball of thread—to help him find his way back out again, after, of course, slaying the beast πŸ‰

Before taking even a single step forward—should we choose to accompany our intrepid friend Theseus on his quest to devise an algorithm to save his life—I am compelled to revisit a much more sobering reality on ground here in Texas 😰 Yes, two words: Hurricane Harvey... Much as I noted atop this essay, which I'm dedicating to my fellow Texans affected by the wrath of Harvey, we go about rebuilding our homes in the Lone Star State of the United States—And we need all the help we can get, and I urge you to please consider pitching in to help our brothers, sisters, children, elderly, stranded pets, etc., who have been starkly affected by Harvey πŸš‘ πŸ’¦ πŸš’ πŸš“ πŸ’¨ πŸ’”

I have poured my heart out to make this my best essay ever, if only to get your precious attention on the stark reality that faces the countless thousands in Houston and other, surrounding areas in Texas; before I went on to earn my MS from Texas A&M University (College Station)yes I'm proud to be an AggieI was, and remain, a proud Houston Cougar as well. Wistfully thinking back now to my undergrad days when I was earning my BS in the presently inundated town. Yes, Houston, you were my warm home—at the same time though a decidedly drier and rather humid one at the same time, goodness—for four wonderful years πŸ™Œ

I never get this personal in my essays. But then again, as in these memorable words from Charlotte Bronte's literary masterpiece, the classic entitled Jane Eyre, and which I read ages ago as a high school student
They are, Miss Eyre, though they absolutely require a new statute: unheard-of combinations of circumstances demand unheard-of rules (italics mine)
So I came to the United States as an immigrant, and this country—my country now for nearly 30 years and to which I pledge my allegianceembraced me with unconditional warmth. I still recall a moment when I was standing outside the University of Houston Cullen College of Engineering with a friend, and we got to talking about the city of Houston in general. Unbeknownst to me—and I have to this day not been able to fathom why—some words that my friend said continue to remain etched in my memory:
You know what Akram, Houston is a city with a big heart; it's a town that is truly ghareeb purwur (an adjective phrase from my native language Urdu, and for which I offer an ad hoc translation: fostering and supportive the common man—and common woman, to be sure in a nurturing way).
Dear readers, I wish to pay a tribute to the city which embraced me as an immigrant; despite having moved back to another city (the neighboring city of Austin)by way of South Carolina and Minnesotathe city of Houston will always have a soft spot in my heart πŸ’

The fury of Harvey finally subsided and we heaved a sigh of relief here. Our yardsboth the front and the back—though are strewn with the wreckage of fallen tree limbs and stuff. But grateful to be safe and not flooded anymore.
Much as I noted above, I've poured my heart out into this essay to make it my best essay ever. In the process, I taught myself how to use an image editing tool to create a handful of pictures collage to share with you. Looks, I'm a computer scientist, engineer, and programmer who designs and crafts the back-end software that powers infrastructures for Big Data and Reactive Applications—I know zilch about these fancy shmancy image editing tools, but I felt compelled to roll up my sleeves and teach myself just enough to cobble together some pictures collage to share with you.

I'm a one-man shop when it comes to this blog; there isn't anyone editing my drafts, or helping me spiff up the formatting; so what you get on this blog is plain, straight up stuff from me 🐣 I will add, though, that it's been my great good fortune to benefit from the advice of my friend Antonio Cangiano who has just happens to have written the definitive book on the subject of technical bloggingover the years, I've leaned on, and benefited tremendously from, that advice πŸ“˜

You'll want to note in particular the pics below with raindrops that symbolize just how bedraggled our existence can become when exposed to the merciless elements of nature; yes, those raindrops signify the tracks of the tears that are being shed this second as the folks in Houston recover from Harvey, struggling to pick themselves up πŸŒ€

Reminds me of the haunting lyrics of the ethereal song Empty Garden by piano virtuoso Elton John who—along with Kishore Kumar and Mark Knopfler—is one of my all-time favorite singers. So in that angst ridden song Empty Garden, we hear Elton John soulfully and wistfully wondering as to
What happened here
As the New York sunset disappeared
I found an empty garden among the flagstones there
Who lived here
He must have been a gardener that cared a lot
Who weeded out the tears and grew a good crop
And now it all looks strange 🌘
And what's it for
This little empty garden by the brownstone door
And in the cracks along the sidewalk nothing grows no more
Who lived here
He must have been a gardener that cared a lot
Who weeded out the tears and grew a good crop
And we are so amazed we're crippled and we're dazed
A gardener like that one no one can replace 🌿
And through their tears
Some say he farmed his best in younger years
But he'd have said that roots grow stronger if only he could hear
Who lived there
He must have been a gardener that cared a lot
Who weeded out the tears and grew a good crop
Now we pray for rain, and with every drop that falls
We hear, we hear your name 🍁
Johnny can't you come out to play in your empty garden 🏠 
🌳 🌲 🌴 πŸƒ πŸ‚ 🍁
And speaking of the empty garden metaphor above, which we savored—in all its ascetic starknessby way of the lyrics of Empty Garden, it's not a random choice of images that you see here; I lavished much care on selecting each and every image, as well as their juxtaposition to achieve the desired effect. Take, for example, the collage below, where I have featured a pic I took in my own backyard—with a stowed-away pile of tree limbs that were severed from our precious live oak trees, as well as other wreckage wrought by the raging winds of Harvey. Again, though, I'm grateful to be safe and not flooded anymore. 

It's a bizarre situation that we've got on our hands; we can't pump gas into our cars, because there is no gas to be found anymore at the gas stations here in Austin. But this a mere annoyance, and utterly pales in comparison with the gut-wrenching catastrophe writ large at the moment in my dear former town: Houston 🌘

Anyone remember singer-songwriter, guitarist Mark Knopfler (of the British music group Dire Straits) singing the deeply symbolic, classic song Telegraph Road?
And my radio says tonight it's gonna freeze
People driving home from the factories
There's six lanes of traffic
Three lanes moving slow 
I used to like to go to work but they shut it down
I've got a right to go to work but there's no work here to be found
Yes, and they say we're gonna have to pay what's owed
We're gonna have to reap from some seed that's been sowed 
From all of these signs saying "sorry but we're closed"
All the way down the Telegraph Road
So I'm going to summon just enough discipline to write up the guts of the essay now—as I've noted elsewhere, I do pretty much all my writing over the weekends; it's all the more poignant that this weekend happens to be a Labor Day weekend πŸ’ͺ And speaking of Labor Day, does anyone remember Rosie the Riveter? She is, of course, the cultural icon of World War IIrepresenting the women who rolled up their sleeves and worked tirelessly in American factories and shipyards—and who rightly became a symbol of feminism and women's economic power.
But I digress a bit, as the author of the eponymous blog is wont to, from time to time 🐝

So before we dive into the guts of the essay proper, though, allow me to present a bouquet—an overture with which to invite you to help out those affected by Harvey, as much as for you to immerse yourself in my take on algorithms—by way of a collage of pics that I lovingly stitched together to remind us all that we're one global family 🌷 🌻 🌹 🌼

Please know that the care I've lavished on knitting together the pics into a unified thematic whole is at least as much as I would give to assembling the quotes and passages I select for me essays in general. The theme of a united humanity—helping one another out during our times of need and distress—as you may well have reckoned, will be a strong undercurrent to this essay. In the lyrics of a U2 song that I like a lot
One love
One blood 
One life 
You got to do what you should 
One life 
With each other 
Sisters 
Brothers 
One life 
But we're not the same 
We get to  
Carry each other 
Carry each other 
One...life 
One 
~ U2 (lyrics from One)

Again, we have here those selfsame raindrops running across across the face of my copy of the phenomenal book The Nature of Computation (Oxford University Press) by Cristopher Moore and Stephan Mertens; look for it in the third spot in the list of my favorite algorithms books that I'll shortly be regaling you with. Be prepared to possibly wince, because this is a decidedly opinionated take on the very best that algorithms have to offer 🎻

The (two) pics below with raindrops running across their face symbolize just how bedraggled our existence can become when exposed to the elemental power of nature 🏈 The careful reader will have noted that those (two) pics—the ones with streaks of raindrops—have none other than the stellar book The Nature of Computation featured in them, center square
Legend to the quadrant collage [#1] of the pics above, starting with the pic in the top-left spot, and going clock-wise from there:
  1. The stellar book entitled The Nature of Computation has raindrops running across its face. 
  2. Workers in paddy fields of rice, busily earning their livelihood through physical labor. 
  3. Another view of The Nature of Computation, bedraggled, yet undaunted like The Brave Tin Soldier
  4. A gutsy owl lifts and powers itself into a silent, stealthy flight of effortless grace.
And the legend to the quadrant collage [#2] of the pics above, starting with the pic in the top-left spot, and going clock-wise from there:
  1. A mechanical rendering of a Turing machine, an idealized computing device that laid the very foundational substrate—both conceptual and physical—for algorithms to run on. 
  2. A hedge maze, an outdoor garden labyrinth in which the walls between passages are made of hedges. 
  3. Wise owls, nestled in their jaunty perch, contemplating a breakthrough algorithm to solve some particularly knotty problem, or perhaps looking into blending seemingly unrelated paradigms of programming
  4. An aerial view of another hedge maze—this one of epic proportions—glistening in the radiance of the sun's warmth.
Next, moving to the legend to the quadrant collage [#3] of the pics above, starting with the pic in the top-left spot, and going clock-wise from there: 
  1. A sea of computers, powered by algorithms, and with their genesis of course in the brilliant mind of Alan Turing
  2. This pic of The Nature of Computation, too, has raindrops—or perhaps tears of mournful grieving ably complemented by defiant resignation—that rip across its face. 
  3. And then there is computer chess, the two-player strategy board game which encompasses both hardware and software, being capable of autonomous play without human guidance 
  4. Another view of The Nature of Computation, letting drops of water slide down its face in serene resignation.
Let's now bring closure to the memorable words which I had quoted at the beginning of this essay (from Charlotte Bronte's literary masterpiece entitled Jane Eyre). Here, I'll quote another passage from that classic, this one reminding us of the unpredictable and uncanny role that circumstances play in our lives. The heroine of the book—Jane Eyre—is engaged in a soliloquy, as she was wont to, and as we high schoolers kept discovering, much to our chagrin, way back when we were studying the prescribed book in all its undiluted glory; painfully enough, we did not have Cliffs Notes study guides back then—life-saving study aids that they are, having rightfully earned immortality in the hearts and minds of a grateful new generation of students 😭

At any rate, Jane Eyre is, in this passage, sharing a primordially elemental moment in the unraveling of the plot—or denouement as my English professor at the University of Houston was fond of saying—and we have the heroine telling us, in first person of course, how
I stopped: I could not trust myself to entertain, much less to express, the thought that rushed upon me—that embodied itself—that, in a second, stood out a strong, solid probability. Circumstances knit themselves, fitted themselves, shot into order the chain that had been lying hitherto a formless lump of links, was drawn out straight—every ring was perfect, the connection complete. I knew, by instinct, how the matter stood, before St. John had said another word: but I cannot expect the reader to have the same intuitive perception, so I must repeat his explanation (italics mine).
And finally the legend to to the quadrant collage [#4] of the pics above, starting with the pic in the top-left spot, and going clock-wise from there:
  1. Algorithms, more than anything else in the entire fabric of computer science, IMHO, evolve and thrive in the hotbed of creativity, and who better to illustrate this with than the true legend of KekulΓ©, who saw in a dream a snake eating its own tail, and which led Kekule—upon awaking from his dream—to the monumental discovery of the benzene molecule's structure. 
  2. Yet another view of The Nature of Computation, glistening in water drops, yet determined to let them slide away as if it's got quite the persona of the duck's feathers. 
  3. And here you have a digression: As much as symbolizing the uncannily significant role that symbols play in programming—unerringly guided as we should be, by the compass of crafting beautiful code—I'm taking this moment to honor the memory of my father, a dedicated chemical engineer who earned his training at the University of Louisville
  4. To round out our stroll through my kludgy collages, let's have ourselves one last look at another pic—which I also took in my Harvey-affected backyard—of The Nature of Computation, as bedraggled as the rest of its sibling pics, yet undeterred.
Brace yourself; we're diving now into the essay proper, as I thank you, with gratitude, for bearing with me, because I had a story that just had to be told 🐾

Algorithms are the stuff of seemingly ethereal technological magic πŸŽƒ Having permeated our collective consciousness—to the extent at least of having registered perceptibly in the minds of the general population—algorithms have irrevocably altered the way we live our lives. To remind us all of the centrality of algorithms to our society and culture, allow me to toss up some references here so we're on the same page. I invite you to look up a more detailed overview elsewhere. Interestingly enough, that overview begins with the Google Search algorithm—which happened to be my suggestion, just a breath away, when I had invited you to look up further details by searching online, should you, of course, wish to do so 🐱

Yep, the very stuff of magic. As the British science fiction writer Arthur C. Clarke famously said
Any sufficiently advanced technology is indistinguishable from magic
At any rate, should you wish to navigate to a (much) more detailed overview, elsewhere, on the stuff of algorithmic magic, you'll find a nice commentary there on—among other algorithms—these ones:
  • Google Search (There was a time not too long ago when search engines battled it out for Internet supremacy) πŸ“Œ 
  • Facebook's News Feed (As much as we may be loathe to admit it, the Facebook News Feed is where many of us love to waste our time) ⛱ 
  • NSA Data Collection, Interpretation, and Encryption (We are increasingly being watched not by people, but by algorithms) πŸ” 
  • High Frequency Stock Trading (The financial sector has long used algorithms to predict market fluctuations, but they're also being used in the burgeoning practice of high-frequency stock trading) πŸ“ˆ 
  • MP3 Compression (Algorithms that squeeze data are an indelible and crucial aspect of the digital world) πŸ”¬ 
  • And the list goes on and on and.... πŸ”­
Indeed, as J.R.R. Tolkien memorably observed in the classic book The Fellowship of the Ring
The Road goes ever on and on.
The question is: Will algorithms remain our servants, or will they overrun as like an out-of-control juggernaut? And should you need further convincing of the juggernaut that algorithms have become, I invite you to check out the superb article Why Software Is Eating the World by Marc Andreessen—yep, the same guy who co-created the highly influential Mosaic Internet browser and cofounded Netscape. The article was originally published in The Wall Street Journal on August 20, 2011. Andreessen was spot on when he presciently noted that πŸ“£
Today’s leading real-world retailer, Wal-Mart, uses software to power its logistics and distribution capabilities, which it has used to crush its competition. Likewise for FedEx, which is best thought of as a software network that happens to have trucks, planes and distribution hubs attached. And the success or failure of airlines today and in the future hinges on their ability to price tickets and optimize routes and yields correctly—with software.
And there is no subject in computer science—at least from a pragmatic and practitioner's point of view—more central than that of algorithms. My fascination with algorithms, and in particular their applicability to distributed programming, would have us travel back through the mists of time; OK, just kidding, so I'm not that old πŸ˜‚ I will, though, be casting a glance back at my ongoing and happily endless journey through the landscape of algorithms. As I do so, I'll be taking an opinionated look at the following books, in turn. With that, I present to you the books which have proved most helpful to me in grokking algorithms:
  1. Algorithms 4th Edition (Addison-Wesley) by Robert Sedgewick and Kevin Wayne πŸ†
  2. Data Structures and Algorithms in Java 6th Edition (Wiley) by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser πŸ””
  3. The Nature of Computation (Oxford University Press) by Cristopher Moore and Stephan Mertens πŸ”¦
  4. Essential Algorithms: A Practical Approach to Computer Algorithms (Wiley) by Rod Stephens πŸ“« 
  5. Algorithms to Live By: The Computer Science of Human Decisions (Henry Holt and Co.) by Brian Christian and Tom Griffiths πŸ”
For those impatiently trying to tell me, Hey Akram, give us the algorithms, and please make it snappy, I will oblige, and herewith submit an opinionated look at the outstanding books in the list above πŸ“˜ You have to remember, though, that I might at times be compelled to digress—may I gently remind the reader that this eponymous blog boldly proclaims the byname Programming Digressions somewhere in its title. Rest assured, thought, that those digressions won't appear until after we're done taking an up-close-and-personal look at these outstanding books πŸ˜‡

I mean, we got to have ourselves some fun along the ride, don't we? 🎈

Oh, and the careful reader will have noted the "(Part 1)", um, part in the title of this essay: "Best Algorithms Books (Part 1)". So it is that I plan on writing at least one more essay to do some justice to the finest of the abundant resources available on the subject of algorithms πŸ’

1. Algorithms 4th Edition (Addison-Wesley) by Robert Sedgewick and Kevin Wayne πŸ†


If you're looking to read only a single algorithms book, look no farther than the extraordinarily well done volume that is simply entitled Algorithms 4th Edition (Addison-Wesley) by Robert Sedgewick and Kevin Wayne. I've gone through a ton of book on the subject of algorithms, over many years, and this gem has emerged as the clear winner πŸ“£

Algorithms by Sedgewick and Wayne has so much that is so good, that I'll need to break down my assessment into easily digestible chunks πŸ”

This book simply can't be beat for comprehensiveness. Yes, there is CLRS out there—it's hoary with age and its dryness is right up there with a desiccated Saharan sand dune on an unbearably hot day—but you need to have the gumption of an archeologist to trudge across the pages of CLRS πŸ« I tossed the acronym (CLRS) out there blithely, but I might as well introduce it for newcomers to the field of algorithms: It just so happens that CLRS are the initials of this formidable book's authors (Cormen, Leiserson, Rivest, and Stein). The book is entitled Introduction to Algorithms 3rd Edition (MIT Press) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It does make for a good research book, for finding citations and that sort of thing—for that it's probably unbeatable—since it happens to be replete, to overflowing, with copious cross-references to the vast literature on algorithms. Given its intimidating style, though, I'm not convinced that it's a good introductory book on the subject.

But I hear you quizzically ask, Aren't we supposed to be talking about the Algorithms book by Sedgewick and Wayne? And right you are, except that I had to get CLRS—along with all its desiccated Saharan sand dune heft—off of my chest. So there πŸ˜‡

In my mind, Algorithms is to the world of algorithms what the Gang Of Four (GoF) book is to the world of software design patterns. Yes, the former is that good, and let me tell you why. For starters, this is an incredibly polished work, much in the tradition of the highly refined GoF book; I'll boldly venture out to say that Algorithms has set an even higher standard for what a technical book—or non-technical book for that matter—can offer to enhance the reading experience in an endearing and pleasing way. In a similar vein, you may wish to also take a peek at another awesome and incredibly well done book entitled Refactoring to Patterns (Addison-Wesley) by Joshua Kerievsky.

As you'll come to appreciate, Algorithms is lavishly illustrated, replete with (Java) code that is pleasingly annotated at just the right level of granularity. I've seen other books kill trees in the process of regurgitating code snippets that leave me hanging; not this book, no sir! The more time I've spent with Algorithms, the more I've come to appreciate it as a trusted and expert personal consultant—goodness, the authors seem to have anticipated just about every question that has popped into my head as I pored over this book's pages over the span of years.

Look, I'm a computer scientist who has been practicing the fine art of programming for over two decades. Nonetheless, we all need access to solid reference books to stay fresh and mindful of the basics. Here I find comfort in the wise words of Edward B. Burger (Southwestern University, Georgetown/Texas) and Michael Starbird (The University of Texas at Austin) who note in their slender yet rich book The 5 Elements of Effective Thinking (Princeton University Press) that
Understand simple things deeply. The most fundamental ideas in any subject can be understood with ever-increasing depth. Professional tennis players watch the ball; mathematicians understand a nuanced notion of number; successful students continue to improve their mastery of the concepts from previous chapters and courses as they move toward the more advanced material on the horizon; successful people regularly focus on the core purpose of their profession or life. True experts continually deepen their mastery of the basics (italics mine).
And Algorithms is a breath of fresh air; you can even read it for sheer aesthetic pleasure 🌹

Some of you may recall Sedgewick's Algorithms in C++. This book (Algorithms 4th Edition), though, uses Java and is, IMHO, a vast improvement over the old C++ book. It uses a sub-set of the Java object-orientation (OO) features, which actually makes the explanations flow more smoothly; in the process, this also tremendously helps in essentially side-stepping language complications that would surely have arisen had the authors chosen to go beyond using a sub-set of the Java OO features. And heaven forbid, you wouldn't want an introductory book on algorithms to go past even that, and start looking into blending two seemingly unrelated paradigms (OO and FP) of programming, which has, though, a rightful and important place of its own in advanced aspects of program design 🐚

In sum, the authors of Algorithms use beautifully elegant and thoughtfully illustrative code throughout the book, preferring clarity over verboseness. All in all, pretty much all the essential goods on algorithms are in here, presented richly, dense—in a good condensed way—and with great taste 😎

2. Data Structures and Algorithms in Java 6th Edition (Wiley) by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser πŸ””


If you're going to read one more book on algorithms, you'll want to make it this one: Data Structures and Algorithms in Java 6th Edition (Wiley) by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser.

For starters, the authors of Data Structures and Algorithms in Java succinctly round up the philosophy—in fact the very gist—of the book when they note how
The design and analysis of efficient data structures has long been recognized as a core subject in computing. We feel that the central role of data structure design and analysis in the curriculum is fully justified, given the importance of efficient data structures and algorithms in most software systems, including the Web, operating systems, databases, compilers, and scientific simulation systems. This book is designed for use in a beginning-level data structures course, or in an intermediate-level introduction to algorithms course. The chapters for this book are organized to provide a pedagogical path that starts with the basics of Java programming and object-oriented design. We then discuss concrete structures including arrays and linked lists, and foundational techniques like algorithm analysis and recursion. In the main portion of the book we present fundamental data structures and algorithms, concluding with a discussion of memory management.
Two standout chapters that I simply have to shout out are the following. Notwithstanding the stellar algorithms book that's in the top spot, the treatment in Data Structures and Algorithms in Java of a couple of crucially important, thematically-related topics—(1) Maps, Hash Tables, Skip Lists, and (2) Graph Algorithms—simply knocked my socks off. You'll find the goods on that pair of topics in chapters 10 and 14, respectively.

Consider, too, the care with which the authors explain just about everything you'll be interested in, at least from a pragmatic standpoint 🐳 In that spirit, check out their sparkling clear coverage of the perennially important topic of Sorting with a Priority Queue. They remind us how πŸ„
One application of priority queues is sorting, where we are given a sequence of elements that can be compared according to a total order relation, and we want to rearrange them in increasing order (or at least in nondecreasing order if there are ties). The algorithm for sorting a sequence S with a priority queue P is quite simple and consists of the following two phases: 
A Java implementation of this algorithm is given in Code Fragment 9.11, assuming that the sequence is stored as a positional list. (Code for a different type of collection, such as an array or an array list, would be similar.) 
The algorithm works correctly for any priority queue P, no matter how P is implemented. However, the running time of the algorithm is determined by the running times of operations insert and removeMin, which do depend on how P is implemented. Indeed, pqSort should be considered more a sorting “scheme” than a sorting “algorithm,” because it does not specify how the priority queue P is implemented. The pqSort scheme is the paradigm of several popular sorting algorithms, including selection-sort, insertion-sort, and heap-sort, which we will discuss in this section.
Ah, if only more writers would write with such enviable clarity and precision ✂ Thus, with helpful and unambiguous descriptions such as the example above, Data Structures and Algorithms in Java is replete with the very essence of what makes algorithms tick πŸ’Ž The language aesthete—and pragmatist—in me believes that you'll enjoy this marvelous book. I definitely did 🎧

3. The Nature of Computation (Oxford University Press) by Cristopher Moore and Stephan Mertens πŸ”¦


Here's the deal: We programmers and technologists, too, need inspiration from time to time; inspiration isn't for artists alone. Lest anyone's jaw dropped at that observation—saying, hey we're a cerebral and logical bunch—I will to out on a limb and say that we're at least as much artists as logical, sentient beings, us programmers. To underscore that precise point, I'll remind you that there's an Art in Donald Knuth's eponymous magnum opus entitled The Art of Computer Programming (Addison-Wesley), which is of course composed of four intense volumes πŸŽ“

And then there is the advice to programmers by David Heinemeier Hansson—the creator of the popular Ruby on Rails web development framework—who noted in his book entitled Rework (Crown Business), which he co-authored with Jason Fried that
When Inspiration Strikes, Strike Back (in a section entitled Inspiration is Perishable)
Having made the case, I suppose, for the rightful place of inspiration, allow me to re-introduce an astonishing book—I had mentioned about it elsewhere, too, many moons ago—which is nothing short of staggering in its potential of unleashing unfettered creativity: The Nature of Computation (Oxford University Press) by Cristopher Moore and Stephan Mertens.

This book—The Nature of Computation—is precisely the one that I had in mind, earlier on in this essay, when I had shared with you the following thought, noting how
Algorithms, more than anything else in the entire fabric of computer science, IMHO, evolve and thrive in the hotbed of creativity, and who better to illustrate this with than the true legend of KekulΓ©, who saw in a dream a snake eating its own tail, and which led Kekule—upon awaking from his dream—to the monumental discovery of the benzene molecule's structure πŸ
Fancy that, I'm caught quoting myself in an act of self-referential circularity; this may well invite jabs about self-referential programming magic, as of course enshrined in the fabulous meta-circular evaluator πŸ˜† At any rate, I can't do any better than what Moore and Mertens themselves have articulated in the splendid Preface—and there is so much that is so splendid about this book—when they share the very origins of The Nature of Computation, telling us how
This book was born in 2005 when one of us was approached by a publisher to write a book explaining computational complexity to physicists. The tale grew in the telling, until we decided—with some hubris—to explain it to everyone, including computer scientists. A large part of our motivation was to write the book we would have liked to read. We fell in love with the theory of computation because of the beauty and power of its ideas, but many textbooks bury these ideas under a mountain of formalism. We have not hesitated to present material that is technically difficult when it’s appropriate. But at every turn we have tried to draw a clear distinction between deep ideas on the one hand and technical details on the other—just as you would when talking to a friend. 
Overall, we have endeavored to write our book with the accessibility of Martin Gardner, the playfulness of Douglas Hofstadter, and the lyricism of Vladimir Nabokov. We have almost certainly failed on all three counts. Nevertheless, we hope that the reader will share with us some of the joy and passion we feel for our adopted field. If we have reflected, however dimly, some of the radiance that drew us to this subject, we are content (italics mine).
For engineers, computer scientists, mathematicians, physicists, and, truth be told, for creativity connoisseurs of all stripes who are looking for a refreshing tour of the amazing intellectual fabric that underlies our universe, I can't think of a better recommendation than a leisurely—or intensely studious and tactical—dive into the lushly cavernous pages of The Nature of Computation πŸƒ

Moore and Mertens have obviously lavished great care on knitting together some awesome themes of computation (think algorithms) into a unified thematic whole; I can only aspire to lavishing such care when I set about assembling the quotes and passages for these essays that I write for you ⛄ Consider, for example, these two delightful quotes which the authors use to great effect. Thus, they lead off Chapter 3: Insights and Algorithms with this enchanting quote from—yes, none other than Donald Knuth—whose magnum opus entitled The Art of Computer Programming I had mentioned just a breath away. They quote him as opining how 
It has often been said that a person does not really understand something until he teaches it to someone else. Actually a person does not really understand something until he can teach it to a computer, i.e., express it as an algorithm... The attempt to formalize things as algorithms leads to a much deeper understanding than if we simply try to comprehend things in the traditional way.
~ Donald E. Knuth
Then, and in fact earlier still in The Nature of Computation, in a sub-section of the Preface that's entitled How to read this book, they naughtily let us in on the starling secret that πŸ•
Outside a dog a book is a man’s best friend. Inside a dog it’s too dark to read
~ Groucho Marx (italics mine)
So it's no wonder that several luminaries of our field have been equally wowed by this unprecedented work of Moore and Mertens—here's just a couple of rave reviews: 
To put it bluntly: this book rocks! It's 900+ pages of awesome. It somehow manages to combine the fun of a popular book with the intellectual heft of a textbook, so much so that I don't know what to call it (but whatever the genre is, there needs to be more of it!).
~ Scott Aaronson (Massachusetts Institute of Technology) πŸš…
A treasure trove of ideas, concepts and information on algorithms and complexity theory. Serious material presented in the most delightful manner!
~ Vijay Vazirani (Georgia Institute of Technology) πŸš—
Placing a marker here, as I need to revisit another peachy book by the source of the first quote above—Scott Aaronson (MIT)—which is entitled Quantum Computing since Democritus . Oh, and the money I spent on buying a copy of The Nature of Computation—and this was ages ago, or so it seems anyway—is some of the best investment I've ever made. Period. Expect to be repaid at an exponentially compounded rate πŸš€

4. Essential Algorithms: A Practical Approach to Computer Algorithms (Wiley) by Rod Stephens πŸ“«


Next up we have an eminently user friendly book on algorithms entitled Essential Algorithms: A Practical Approach to Computer Algorithms (Wiley) by Rod Stephens. It's written in a pleasant and thoughtful tone, with the author neither talking down to the reader nor dumbing down the material in the least. The balance thus achieved, plus the blending of the granularity level, really hit the sweet spot for me 🍯, reminding me (albeit in a tangential way) of the following quote, from an essay elsewhere, where I was citing someone as saying that
Scala provides the tools needed to blend the object-oriented and functional programming worlds. Scala is at its best when these two evenly share a codebase. The biggest danger to misusing Scala is to ignore its object orientation or its functional programming. But combining the two is the sweet spot that the language was designed to fulfill (italics mine).
Oh, and check out the author's endearingly smart introduction to how he came upon making the field of algorithms his own. When you get yourself a copy of this, you'll be regaled with how πŸ˜‚
Rod Stephens started out as a mathematician, but while studying at MIT, he discovered how much fun algorithms are. He took every algorithms course MIT offered and has been writing complex algorithms ever since. During his career, Rod has worked on an eclectic assortment of applications in such fields as telephone switching, billing, repair dispatching, tax processing, wastewater treatment, concert ticket sales, cartography, and training for professional football players.
Stephens aptly reminds us of the vitality and centrality of algorithms by observing that πŸ”§πŸ”¨πŸ”©
Studying algorithms lets you build a useful toolkit of methods for solving specific problems. It lets you understand which algorithms are most effective under different circumstances so that you can pick the one best suited for a particular program. An algorithm that provides excellent performance with one set of data may perform terribly with other data, so it is important that you know how to pick the algorithm that is the best match for your scenario. 
Even more important, by studying algorithms you can learn general problem-solving techniques that you can apply to other problems even if none of the algorithms you already know is a perfect fit for your current situation. These techniques let you look at new problems in different ways so that you can create and analyze your own algorithms to solve your problems and meet unanticipated needs.
Last, but certainly not the least, I invite you to note a crucial point that Stephens make in an introductory section entitled Who This Book Is For. This will let you decide whether Essential Algorithms: A Practical Approach to Computer Algorithms is truly the right algorithms book for you. Thus, with that precise thought in mind, Stephens notes how
This book is intended primarily for three kinds of readers: professional programmers, programmers preparing for job interviews, and programming students. Professional programmers will find the algorithms and techniques described in this book useful for solving problems they face on the job. Even when you encounter a problem that isn’t directly addressed by an algorithm in this book, reading about these algorithms will give you new perspectives from which to view problems so that you can find new solutions.
Should you find yourself fit any part of the description above, all I can say is: Go out and grab this book; you won't regret it; I certainly didn't πŸ™‡

5. Algorithms to Live By: The Computer Science of Human Decisions (Henry Holt and Co.) by Brian Christian and Tom Griffiths πŸ”


Okay, so the last algorithms book we'll be looking at today won't actually teach you the ins and outs of algorithms in any details; in fact, not at all, at least from the implementation perspective. But I include Algorithms to Live By: The Computer Science of Human Decisions (Henry Holt and Co.) by by Brian Christian and Tom Griffiths in this list because it deserves a wide readership among those wishing to truly grok algorithms.

Algorithms to Live By will help you situate algorithms in their applicability to our personal world, and indeed to the business world as well. Dare I say, it will help answer the question that I had posed at the outset: Will algorithms remain our servants, or will they overrun as like an out-of-control juggernaut?

In the same breath—and there I had mentioned in passing the evocatively named article Why Software Is Eating the World by Marc Andreessen—I invite you again to hold on to the thought of finally deciphering the stuff of algorithmic magic. This book will tremendously aid you in grokking the bottomline of this precise area πŸ’°

Thus, Christian and Griffiths pertinently point out in the Introduction to Algorithms to Live By that
Talking about algorithms for human lives might seem like an odd juxtaposition. For many people, the word “algorithm” evokes the arcane and inscrutable machinations of big data, big government, and big business: increasingly part of the infrastructure of the modern world, but hardly a source of practical wisdom or guidance for human affairs. But an algorithm is just a finite sequence of steps used to solve a problem, and algorithms are much broader—and older by far—than the computer. Long before algorithms were ever used by machines, they were used by people. 
The notion that studying the inner workings of computers might reveal how to think and decide, what to believe and how to behave, might strike many people as not only wildly reductive, but in fact misguided. Even if computer science did have things to say about how to think and how to act, would we want to listen? We look at the AIs and robots of science fiction, and it seems like theirs is not a life any of us would want to live.
There is a lot going on in this excellent book, far more than I can do justice to at this juncture. Suffice it to say that I'm becoming increasingly and acutely aware of a startling phrase—at least that's how the phrase grabbed me on my first encounter with it—that "Real Artists Ship". There, in his bestseller entitled Linchpin: Are You Indispensable? (p.101), Seth Godin was reminding us of the importance that shipping a product must occupy in our collective consciousness 🚚

So it is that I will now exit, but not before an admittedly flamboyant flourish that harkens back to the 1937 Disney classic, Snow White and the Seven Dwarfs, in which the Evil Queen utters the famous line that I'm here taking the liberty of wildly paraphrasing—with a nod to Godin's moniker that "Real Artists Ship"—by intoning
Magic mirror, on the wall—which one is the fastest shipping method of them all?
πŸš‚ πŸšƒ 🚚 🚒 πŸš…
In the end—and much as I hinted at, at the outset—I invite your comments. Much more importantly, please, do please consider helping our fellow Texans affected by the fury of Hurricane Harvey. I dedicate this essay, once again, to you, fellow Texans, as we go about rebuilding our homes in the Lone Star State πŸ‡ΊπŸ‡Έ Here's how you can help those affected by Harvey πŸŽ―

BTW, and I'll mention this as a friendly reminder—your comments are welcomed, as always—that having read my brief take each on a handful of the finest algorithms books...
  • Did you find that your experience of reading these books was perhaps different
  • Were there other qualities, perhaps, that I did not cover, and which happen to be the ones that you found the more helpful—in these or other books—as you mastered algorithms? 
  • Did I leave out any of your favorite algorithms books?! 
  • I've covered only a tiny fraction of the algorithms books that I've read, necessarily limited by the time available—stay tuned for future installments of this essay 
I trust that these brief vignettes will help you in some small way along your journey to grokking algorithms 🚣



10 comments:

  1. Impressive article akram, hurricane Harvey might have damaged the infrastructure but not the spirit of Texas.

    ReplyDelete
    Replies
    1. - Thank you, Archean, for the kind words. Comments from readers like you make my day, every day. Even more significantly, your magnificent observation—Hurricane Harvey might have damaged the infrastructure but not the spirit of Texas—warmed my heart.

      - I had shared in this essay of course some warm recollections of the years I lived in Houston. So your comment is especially meaningful as I hear in your words the same reflections of the indomitable spirit of Texans that I've seen with my own eyes.

      - Thank you for your vote of confidence that we Texans will make it through what Harvey has lately wrought!

      - While I trust that my opinionated reviews of some of the finest algorithms books will be helpful to you and other readers, my deeper hope is, notwithstanding what I just said, that readers will be motivated, perhaps even compelled to look up the online resources—which I've conspicuously mentioned both atop this essay, as well as toward the conclusion—and truly make a difference in the lives of fellow citizens in distress...

      - And speaking of my opinionated take on some of the finest algorithms books out there, one noteworthy point I should bring to your attention is that I realize in hindsight that I ended up conflating the equally important subject of data structures with algorithms; I made a subliminal assumption that, without suitable data structures, one simply can't go anywhere with algorithms. Period.

      - To underscore the point above, allow me to quote yet another fine book on this subject, albeit this one leaning heavily toward the data structures department, and less so toward algorithms. Thus, the author of this fine book entitled Data Structures and Algorithms in Java 3rd Edition (Cengage Learning) is Adam Drozdek. He notes in the Preface to his book that:

      "The thrust of this book is data structures, and other topics are treated here only as much as necessary to ensure a proper understanding of this subject. Algorithms are discussed from the perspective of data structures, so the reader will not find a comprehensive discussion of different kinds of algorithms and all the facets that a full presentation of algorithms requires".

      - I hope that this will help clarify the notion that data structures and algorithms are equal partners, either going hand-in-hand, or not going anywhere. Period :)

      Delete
  2. I appreciate your enthusiasm for algorithms :) I'm sure this will benefit others with a similar passion.

    ReplyDelete
    Replies
    1. - Thank you, Elizabeth, for appreciating my enthusiasm for algorithms, as well as for reading this admittedly whale-like essay :)

      - Yes, it's definitely my hope that this essay will benefit others with a similar passion!

      - Speaking of my passion for algorithms, I must confess with some sheepishness that it is precisely this passion—coupled with my strong ties to Texas in general, and to Houston in particular—which led me to overlook a fundamental aspect of crafting an essay. Thus, I inadvertently overlooked just how disorienting it may well have been for someone to come looking for a laser-focused treatment on algorithms, only to find, actually not to find that very treatment until quite some way into the essay...

      - In fact, this feedback came my way, in a very nice way, I hasten to add, for example from Reddit readers of my essay, who read it, and shared invaluable feedback with me, and which you may read here, along with my detailed response each :)

      - Again, thanks so much for making the time to share your thoughts, along with invaluable feedback: Encouraging comments from readers like you make my day, every day :)

      Delete
  3. Great essay. What do you think of companies that use algorithm tests for interview testing ?

    There seems to be much debate on this. How can a working engineer keep their DS&A skills sharp if they don't use them in their job much ?

    ReplyDelete
    Replies
    1. - Thank you, Shahbaaz, for making the time to share your kind words of encouragement, along with some really great questions: You've touched upon a vast topic—and an eminently important one at that—and I'll do my best to formulate some thoughts to do justice in my response to those questions...

      - To your first question ("What do you think of companies that use algorithm tests for interview testing?"), I would say that it makes a lot of sense for a job interview to include questions that require you to use your skills to solve a problem. In fact, being well-versed in algorithms—for example by reading up exactly the kind of algorithm books that I've reviewed in-depth in this essay—will get you over the hump in that many of those tests would be rather difficult to tackle were you not to have lately been reading up the related algorithms.

      - Another related practice, which has become common practice (as part of interview testing) is less than well-advised, IMHO. I'm referring here to puzzles that are intended to gauge a candidate’s creativity and problem-solving abilities. The problem with such puzzles is that they inherently and inevitably make numerous assumptions, which simply may not be valid.

      - You know what I'm talking about, right?: Think here to interview puzzles involving marbles, eggs, perhaps fathoming the color of a fabled bear, or deciphering what happens when a genie visits a band of men stranded on an island, and ad nauseam. Good grief, I'm already feeling nauseous ;)

      - Yep, I fully agree that devising the best solution to real-world problems often require creativity. Te only problem is that the majority of these interview puzzles simply don’t measure creativity; what they are effectively measuring is whether you have had the gumption and resourcefulness to wade through a sufficiently large number of such puzzles online—along with their purportedly creative solutions—to come up with a puzzle that your interviewer may be talking about, or perhaps a variation thereof.

      - As to your other question ("There seems to be much debate on this. How can a working engineer keep their DS&A skills sharp if they don't use them in their job much?")—which is truly an awesome question BTW—I would say that trying to formulate my thoughts to do justice (to answering this particular question) in my response will lead us straight to the heart of what exactly it is that brought you and me to the practice of programming in the first place :)

      - It all boils down to the passion (for intellectual growth, among other things) that you bring to the workplace, each and every day. For those of us—and I consider myself lucky to count myself among them—for whom the job (of designing and crafting software) is the perk, your passion for crafting Beautiful Code, Beautiful Prose will inevitably lead you to make all the right decisions in keeping your Data Structures and Algorithms (aka DS&A) skills sharp, even if you don't use them (i.e. fundamental DS&A) in your job that much.

      - I confess that my point above borders on the philosophical lol. But then again, I remind us to explore what brought us to the practice of programming—an art and a science by all reckoning—in the first place...

      Delete
    2. - Do please revisit and let me, and other readers, know your thoughts and impressions of my response. Much as I said at the outset of my response, you've touched upon a vast topic—I invite you and other readers to educate us all in better appreciating this vitally important topic, thanks!

      - Oh, and I nearly forgot to share a marvelous passage—from Russ Olsen's superb book entitled Eloquent Ruby (Addison-Wesley)—that I had in mind when I pontificated earlier about the the passion (for intellectual growth, among other things) that you bring to the workplace. BTW, I did a deep-dive into Ruby many years ago; goodness, that's a whole different story, should anyone be interested in hearing my adventures in that area. But I digress...

      - So here's that marvelous passage in which Olsen eloquently tells the readers of Eloquent Ruby—specifically in Chapter 22. Use method_missing for Delegation—how

      "About ten years ago, for reasons that are still inexplicable to me, I gave up software development. I put down my keyboard and donned the coat if not the actual tie of a software development manager. I prepared schedules. I ran meetings. I did performance reviews. And I was miserable. The more time I spent with people, the more I loved my computer. I look back on those two or three years as the most difficult period of my professional life. Instead of rolling into work every morning, eager to do battle with the essential complexity of the universe, I dragged myself to the office to fight the pervasive stupidity of a Byzantine organization".

      "Still, my years in organizational purgatory were not completely wasted. During my stint as a manager I did learn some things, mainly things about people. The most important thing that I learned was that you just have to trust the folks who work for you. Make sure they know what they’re doing. Make sure they know what you want them to do. Then get out of the way and let them do it. In short, I learned to delegate".

      - Now it's time for you and other readers to please share your impressions, observations, thoughts, etc., about this vast topic—I invite you and other readers once again to educate us all in better appreciating this vitally important topic, thanks!

      Delete
  4. Our hearts go out to the Harvey victims in Houston (and surrounding areas). It's such a huge catastrophe I think the scope is still incomprehensible as we're still in shock. Great digression into your pick of algorithm books. I can't say I've read any. In fact I can't recall the title of the book we used in my Analysis of Algorithms class way back in college.

    I'm reminded how much I enjoy the search for efficiency and elegance in computer science as opposed to the practical "push" in our jobs we constantly feel to just "get it done." While there are 100 ways to skin a cat, I always wish I had more time to delve into better ways rather than being forced to move on to the next problem-- or cat if this analogy holds up. (How did cats ever get dragged into this horrible analogy I really don't want to know).

    Thank you for sharing. It's always nice to your wonderful brain working Sir Akram!

    ReplyDelete
    Replies
    1. - Your warm words of support, Josh, for the Hurricane Harvey victims in Houston (and surrounding areas) have, in turn, warmed my heart. I feel so heartened and encouraged that this essay—which was intended at least as much to bring awareness to the plight of Harvey victims as it was to share my two cents on algorithms—has fulfilled its mission. Thank you!

      - Yes, those are absolutely my own sentiments as well: The enormous scale of the catastrophe that Harvey left in its wake has left many fellow Texans, myself included, in denial. We're still grappling with internalizing the true dimensions of what has taken place, as you eloquently put it, when you said how "I think the scope is still incomprehensible as we're still in shock."

      - As before, my hope is that readers will continue to use the online resources—which I had prominently sprinkled throughout this essay—as well as all other available resources of course, to help our fellow Americans in this time of distress.

      - Now, more than ever, is the time for "unarmed truth and unconditional love". In fact, I'm reminded of the sentiments so eloquently articulated by Martin Luther King, Jr. when he said that

      "I refuse to accept the view that mankind is so tragically bound to the starless midnight of racism and war that the bright daybreak of peace and brotherhood can never become a reality... I believe that unarmed truth and unconditional love will have the final word."

      - Hey, and moving now to the subsidiary theme of this essay, this digression that was my essay—I had, in fact, referred to that subsidiary theme of the essay when I had intoned how

      "...before we dive into the guts of the essay proper, though, allow me to present a bouquet—an overture with which to invite you to help out those affected by Harvey, as much as for you to immerse yourself in my take on algorithms—by way of a collage of pics that I lovingly stitched together to remind us all that we're one global family".

      - And having submitted the sentiment above in the essay—and moved as I was by the conviction that now is the time for "unarmed truth and unconditional love"—I had of course gone on to share in this essay a collage of pics that I lavished much care on, to (seamlessly) knit the pics together into a unified (and thematically) whole. The theme, in other words, of a united humanity, helping one another out during our times of need and distress.

      - Only after presenting the (aforementioned) collage of pics had I assured my reader that the time to finally delve into the topic of algorithms—the essay proper—was near at hand, advising the reader to

      "Brace yourself; we're diving now into the essay proper, as I thank you, with gratitude, for bearing with me, because I had a story that just had to be told".

      Delete
    2. - So I'm pleased that you enjoyed my pick of algorithm books. Thanks for sharing that feedback!

      - Oh goodness, don't we all forget which book(s) we studied, back when we were getting acquainted with the crucial area of algorithms, on our way to mastering this indispensible area that lies at the very heart of (pragmatic) computer science, lol.

      - That was awesome! You made my day by sharing your thoughts on the shared passion we have for our chosen fields (of computer science in general and programming in particular). I see clear reflections of this especially when you note how "I always wish I had more time to delve into better ways rather than being forced to move on to the next problem".

      - Ah, so you do remember that I'm a cat lover, don't you? ;)

      - Folks, besides being a truly pleasant surprise to hear from our reader Josh (the reader and reviewer to whose comment I'm responding here), I wish to mention that Josh (Suarez) also happens to be a brilliant and gifted fellow programmer. I had an awesome time plying our trade—of software design and development of course—together with him at a former workplace.

      - With that brief intro out of the way, I need to have a word with you, amigo: Dog lover that you are, let me remind you one more time of my feline predilictions ;)

      - LOL, just kidding. I'm right there with you in marveling at how and where the cliche ("There are 100 ways to skin a cat") ever originated! Right, how did cats—those most endearing of creatures—ever get dragged into that horrible metaphor of a cliche of an analogy of an...

      - Again, I thank you for sharing all those cool ideas, memes, and thoughts.

      - Ah, as to your point, "It's always nice to [see] your wonderful brain working Sir Akram!", I do believe I've been dubbed a knight—in some kingdom or something—out there yonder lol. You know, I have been known to think a thought or two on the rare occasion ;)

      - I leave you, saying thanks again, with these words that are attributed—apocryphally or otherwise—to the ever-witty George Bernard Shaw (the inimitable Irish playwright, critic and polemicist) when he wryly remarked how

      I have made an international reputation for myself by thinking once or twice a week :)

      Delete