Forem: Alaina Kafkes

Exploring the Linguistics Behind Regular Expressions

Alaina Kafkes — Mon, 20 Nov 2017 15:39:36 +0000

Regular expressions inspire fear in new and experienced programmers alike. When I first saw a regular expression — often abbreviated as “regex” — I remember feeling dizzy from looking at the litany of parentheses, asterisks, letters, and numbers. Regular expressions seemed nonsensical, impenetrable.

I expected regular expressions to crop up again in my upper-level computer science coursework — maybe by then I’d finally feel ready to tackle them — but I encountered them in an introductory class that I had put off until my senior year. The purpose of this course was to draw students who had never written a line of code into CS by introducing them to concepts like cryptography, human-computer interaction, machine learning — you know, only the latest and greatest of tech buzzwords.

I didn’t attend more than a handful of lectures, but one of the assignments stuck with me. I had to write an essay about a famous computer scientist or academic whose work impacted computer science. I chose Noam Chomsky.

Little did I know that learning about Chomsky would drag me down a rabbit hole back to regular expressions, and then magically cast regular expressions into something that fascinated me. What enchanted me about regular expressions was the homonymous linguistic concept that powered them.

I hope to spellbind you, too, with the linguistics behind regular expressions, a a backstory unknown to most programmers. Though I won’t teach you how to use regular expressions in any particular programming language, I hope that my linguistic introduction will inspire you to dive deeper into how regular expressions work in your programming language of choice.

To begin, let’s return to Chomsky: what does he have to do with regular expressions? Hell, what does he even have to do with computer science?

A Computer Scientist By Accident

Wikipedia christens Noam Chomsky as a linguist, philosopher, cognitive scientist, historian, social critic, and political activist, but not as a computer scientist. Because he is so highly regarded in all of these fields, his indirect contributions to the field of computer science often fall by the wayside.

The more I researched Chomsky’s academic work, the more accidental Chomsky’s foray into computing seemed. This affirmed my belief that all fields — even those that appear disparate from computer science — have something to offer to computing and the tech industry.

His contributions to the field of linguistics in particular exemplify the impact of interdisciplinary research on computer science. The Chomsky hierarchy transformed the code that computer scientists, software engineers, and hobbyists write today.

Yes, it was this hierarchy that brought regular expressions to computer science. But, before we can understand the jump from Chomsky to regular expressions, I’ll outline the Chomsky hierarchy.

Linguistic Law & Order

The Chomsky hierarchy is an ordering of formal grammars — think syntactic rules for formal languages — such that each grammar exists as a proper subset of the grammars above it in the hierarchy. Some formal languages have stricter grammars than others, so Chomsky sought to organize formal grammars into his eponymous hierarchy.

I briefly mentioned that formal grammars are syntactic rules: rules that give all possible valid phrases for a given formal language. Grammars provide the rules that build languages. In linguist-speak, a language’s formal grammar provides a framework with which nonterminals (input or intermediate string values) can be converted into terminals (output string values).

To elucidate this new vocabulary, I’ll walk through an example of converting a set of nonterminals into terminals using a made-up formal grammar. Let’s say that our pretend formal language, Parseltongue, has the following formal grammar:

Terminals: {s, sh, ss}
Nonterminals: {snake, I, am}
Production rules: {I → sh, am → s, snake → ss}

Using the production rules, I can convert the input sentence “I am snake” into “sh s ss.” This conversion happens piece by piece: “I am snake” → “sh am snake” → “sh s snake” → “sh s ss.”

As my Parseltongue example illustrates, formal grammars parse strings of nonterminals into terminal-only strings — grammatically correct phrases. But formal grammars act not only as generators of a language, but also recognizers of whether a string fits the formal grammar. Whereas the example string “I am a snake” can be fully converted into terminals, the string “I am not a snake” cannot be written in Parseltongue because the nonterminal “not” cannot be translated into a Parseltongue terminal.

To re-emphasize something I stated earlier: formal grammars generate formal languages. That means that, by creating a hierarchy of formal grammars, Chomsky also categorized languages themselves.

With that sobering introduction, let’s look at the four formal grammars in Chomsky’s hierarchy. From most to least strict, they are:

Regular grammars, which retain no past state knowledge from input string to output string
Context-free grammars, which retain only recent state knowledge from input string to output string
Context-sensitive grammars, which keep all past state knowledge from input string to output string
Unrestricted (or recursively enumerable) grammars, which have all state knowledge and thus can create every output string imaginable from a given input string

What is this “state knowledge” that I speak of? Think of knowledge in terms of scope. Regular grammars, for example, have no knowledge of the string’s past states in their "scope" in the process of converting an input string into an output string. This suggests that once the grammar makes an individual conversion of nonterminal to terminal (plus a series of zero or more nonterminals), the grammar “forgets” the previous state of the string.

On the other hand, unrestricted grammars hold onto every possible state of the string-in-translation. Context-free and context-sensitive grammars fall somewhere in the middle.

If you’re looking for a more detailed explanation of the grammars in the Chomsky hierarchy, you’ll have to take a peek at automata theory. I’ll focus on the grammar that brings us back to regular expressions, fittingly called the regular grammar.

On the Regular Expressions

Regular expressions and regular grammars are equivalent. They communicate the same set of syntactic rules, albeit using different formalisms, and both produce the same regular languages.

In linguistics, a regular expression is recursively defined as follows:

The empty set is a regular expression.
The empty string is a regular expression.
For any character x in the input alphabet, x is a regular expression that produces the regular language {x}.
Alternation: If x and y are regular expressions, then x | y is a regular expression. For example, the regular expression 0|1 produces the regular language {0,1}.
Concatenation: If x and y are regular expressions, then x • y is a regular expression. For example, the regular expression 0•1 produces the regular language {01}.
Repetition (also known as Kleene star): If x and y are regular expressions, then x* is a regular expression. For example, the regular language 0•1* produces the regular language {0, 01, 011, 0111, ...}, ad infinitum.

A regular grammar is composed of rules like those of Parseltongue. Just as a regular grammar can be utilized to parse an input string into an output string, a regular expression converts strings quite similarly. You can see examples of this parsing for the alternation, concatenation, and repetition operations — or, to use my prior analogy, rules — that regular expressions adopt.

Let’s return to our friend Noam Chomsky for a moment. According to his hierarchy of grammars, regular grammars retain no information about intermediate steps in converting from an input string to an output string. What does this tell us about regular expressions?

The “forgetfulness” of regular grammars implies that translations in one part of the string do not impact how the other nonterminals in the string are translated in future steps. There is no coordination between different parts of the string in the creation of the output string.

Looking at the linguistics behind regular grammars gives us insight into why programmers first brought regular expressions into code. Although I’ve only discussed formal grammars as generators and recognizers of language, the fact that regular grammars convert input string to output string piece by piece makes them pattern-matchers. In programming, regular expressions use production rules to convert an input string — a pattern — into a regular language — a set of strings that match that pattern.

But I would have never written this blog post if programming language creators implemented regular expressions exactly as they are defined in the field of linguistics. Computational regular expressions are a far cry from their linguistic precursor, but the linguistic regular expressions that I covered provide a useful framework for understanding regular expressions in code.

Two Regular Expressions, Both Alike in Dignity

Hereafter, I will use the term regular expression to mean a linguistic regular expression and the term regex to signify a programmatic regular expression. In the wild, both linguistic and programmatic regular expressions are referred to as “regular expressions” even though they are quite different from one another — how confusing!

The difference between regular expressions and regexes stems from how they are used. Regular expressions — or regular grammars — are part of formal language theory, which exists to describe shared elements of natural languages — languages that evolved over time without human premeditation. Linguists use regular expressions for theoretical purposes, like the categorization of formal grammars in the Chomsky hierarchy. Regular expressions help linguists understand the languages that humans speak.

Regexes, on the other hand, are utilized by everyday programmers who want to search for strings that match a given pattern. While regular expressions are theoretical, regexes are pragmatic. Programming languages are formal languages: languages designed by people (here, programmers) for specific purposes. As you might imagine, programming language creators augmented the functionality of regexes in code. Let’s examine these enhancements.

Remember that regular expressions have three operations: alternation, concatenation, and repetition. I’m no regex expert — regexpert? — but all it takes is a peek at the regular expression Wikipedia page to notice that regexes implement more than just three operations.

For example, using POSIX regex syntax, the pattern .ork matches all four-character strings that end with the three characters “ork.” That period is more powerful than simple alternation, concatenation, and repetition, right?

Nope. Truth be told, even the fanciest of regex metacharacters — characters that invoke a regex operation — derive from regular expression operations. Assuming that the twenty-six lowercase letters of the alphabet are the only characters in the regular grammar, the regex pattern .ork could be written using only regular expression operations as [a|b|c|...|z]ork.

Though the sheer volume of metacharacters suggests that regex has a more powerful set of operations than regular expressions themselves, metacharacters are merely shortcuts for various permutations of the operations that define regular expressions. Regex metacharacters provide a programmer-friendly abstraction for common combinations of alternation, concatenation, and repetition.

So far, I’ve portrayed regexes as regular expressions with amazing shortcuts and clear-cut use cases. However, as you may recall from Chomsky’s hierarchy, regular grammars have the strictest rules and no scope. Luckily, regexes have a little more leeway than their linguistic precursor, thereby bestowing them with more practical power.

Breaking the Regular Grammar Rules

Recall that, according to the the Chomsky hierarchy, regular grammars retain no knowledge in converting an input string to an output string. Since regular expressions are equivalent to regular grammars, this means that regular expressions also have no memory of the intermediate states of a string as it changed from input to output. It also means that translating a nonterminal in one part of a regular expressions has no bearing on the translation of a nonterminal in another part of the expression.

For regexes, it’s a different story. Regexes violate this key regular grammar characteristic by supporting the ability to backreference. Backreferencing allows the programmer to parenthetically separate a subsection of a regular expression and refer to it using a metacharacter. To give an example, the pattern (la)\1 matches “lala” by employing the \1 metacharacter to repeat the search for “la.”

Because different parts of the string cannot influence one another in regular expressions, backreferencing gives regexes a lot more power than their predecessor. More importantly, backreferencing facilitates practical uses of regex such as searching for typos in which the same word was accidentally typed twice in a row. Pragmatism gives insight into why regular expressions were tweaked to create regexes in programming.

Another feature that increases the functionality of regex is the ability to alter the greediness of the matching. Different quantifiers — categories of regex patterns — can look similar but match drastically different parts of a string. A greedy quantifier (*) will attempt to match as much of the string as possible, whereas a reluctant quantifier (?) will try to match the minimum amount of characters in the string. Given the string “abcorgi,” the pattern .*corgi would match the entire string but the pattern .?corgi would only match “bcorgi.”

A possessive quantifier (+) also attempts to match as much of the string as possible, but, unlike the greedy quantifier, it will not backtrack to previous characters in the string in order to find the largest possible match. Given the string “abcorgi,” the patterns .*corgi and .+corgi would match the entire string. Though possessive and greedy qualifiers will often produce the same result, possessive qualifiers tend to be more efficient because they avoid backtracking.

Because quantifiers are metacharacters, they can technically be built from alternation, concatenation, and repetition: the three operations of regular expressions. However, quantifiers create a simple abstraction that allows programmers to quickly specify what type of match they would like.

Conclusion & Further Reading

What a journey we’ve undertaken! We learned about Chomsky and his eponymous hierarchy, then dove deeper into regular grammars. From regular grammars, we explored the linguistic definition of a regular expression. Finally, we used the differences between regular expressions and regexes to motivate how programmers use regex today.

Although I trace the history of regular expressions from Chomsky to modern programming languages, this blog post is not the end of the regex story. If you’d like to learn more about linguistic and computational regular expressions, I have some motivating questions for you.

What is automata theory and how does it relate to the Chomsky hierarchy?
How is regex implemented? What are the tradeoffs of various regex algorithms?
When is it appropriate to use regexes instead of built-in string match and manipulation libraries?

I also have a list of resources that I used to study up on the linguistic and computational elements of regular expressions. Happy regex-ing!

Enjoy what you read? Spread the love by liking and sharing this piece. Have thoughts or questions? Reach out to me on Twitter or in the comments below. This post was originally published on Medium. Cover image credits belong to xkcd.

Rejection & Revision: On Improving Conference Proposals

Alaina Kafkes — Mon, 23 Oct 2017 15:07:49 +0000

One of my goals for 2018 is to speak at more tech conferences.

Although I gave talks at two conferences in 2017, the call for proposals (CFP) process still feels opaque to me. Submitting a talk proposal to CFP reviewers is like dropping a letter into the void: usually, the only contact I receive from the reviewers or organizers about my proposal is an email stating whether they accepted or rejected my talk.

Newcomers to the technical speaking circuit haven't mastered the CFP process yet. Receiving so little feedback – an auto-generated rejection most of the time – leaves them without a clear path to improve their proposal for the next CFP.

For an industry that prides itself on iterative development, the black box nature of CFPs feels particularly egregious to me. If a conference wishes to invest in scouting fresh technical speaking talent, feedback besides (and even before!) acceptance or rejection should be high priority.

Despite the flaws of the CFP process, I have developed strategies to turn the rejections I receive into better proposals. I'll share the steps I took to turn my most recent rejections into revisions in the hopes that it will assuage the discouragement of speaker-hopefuls (like you!) and provide them with actions that they can take to improve their talk proposals.

Ask for Feedback

I emailed two conference organizers asking for their reviewers' feedback on my proposal. Both organizers were quite willing to share this information with me.

Before I provide excerpts of this feedback, I'd like to introduce a framework that I use to sift the useful feedback and discard the fluff: Lara Hogan's card suits. In her book Demystifying Public Speaking, she elaborates:

Hearts: "feedback that is positive, but not specific"
Diamonds: "feedback that is positive, and specific or actionable"
Clubs: "feedback that is negative, but not specific or constructive"
Spades: "feedback that is negative, but gives specific suggestions"

After receiving a rejection, speakers and speakers-to-be should seek diamonds and spades from the organizers. I'll categorize some of the feedback I received for my rejected talk proposal:

"The audience participation section feels like something that would work great in a small meetup group or a tutorial session at a larger conference, but probably won't go quite as well in a 400-person single-track event."

I consider this feedback a diamond. As someone who has never spoken in front of a 400-person audience, it would be impossible for me to ascertain this fact without the wisdom of a seasoned conference speaker or organizer. This ill-placed audience participation could mark me as unprepared to give this talk, which is untrue. I have since removed this section from my talk proposal.

"[Topic] was not a topic that we saw other people submitting talks about. That is also a great feather in your cap for the uniqueness factor."

I consider this feedback a heart. When speaking with this organizer, it was clear that the reviewers liked my proposal, but not enough to select it.

"I think restructuring the talk/proposal to show evidence of why... [would make] you and your material sound more authoritative than anecdotal."

I consider this feedback a diamond or spade, depending on how negatively the organizer connotes the word "anecdotal." I have since cut out any weak language in my talk proposal and put more emphasis on explaining the why.

I'm grateful to these conference organizers for providing me with mostly diamonds – feedback that I can use. When asking for feedback on a rejected talk proposal, push for those diamonds and spades.

Look to the Abstract

Of all the sections of a talk proposal, the abstract is the canary in the coal mine. If the abstract is bad – meaning unclear, illogical, or underdeveloped – then the rest of the proposal probably follows suit.

Before I continue talking about the abstract, I'd like to outline the anatomy of a talk proposal. Typically, it has these three parts:

Abstract: short, elevator pitch that motivates the talk and summarizes the desired outcome
Description: talk outline
Notes: any additional information, especially why this speaker should give this talk at this conference

Since the abstract is often the first thing an organizer or reviewer sees on a talk proposal, it sets up their perception of a given talk. Even though abstracts tend to be looked at first, they should be written last: as in scientific research papers, abstracts act as introduction, content summary, and conclusion.

The best way for a speaker-hopeful to vet and improve their abstract is, paradoxically, to elucidate their talk description. Writing a razor-sharp description can help the speaker determine the biggest selling points of their talk, which is exactly what they should share in the abstract. I'll discuss honing the talk description more in the next section.

Speakers can also ameliorate their abstract by tailoring it to the unique traits of a conference. If a speaker-hopeful wishes to present at a Ruby conference, then their abstract should include how their talk benefits Ruby developers. Even language-agnostic conferences have traits that a speaker can reflect in their abstract – all it takes is a little research to find their quirks! Tailoring an abstract to a conference can convince reviewers of the talk's value-add for their audience.

The abstract that I submitted to conferences in September and October was, admittedly, not a good reflection of my talk description. It also was not tailored to the special characteristics of each conference. My abstract – and overall proposal – feels much more polished now that I have addressed these flaws. But, in order for me to strengthen my abstract, I first had to edit my description.

Whittle Down to the Essentials

As I mentioned earlier, the talk description influences the direction an abstract should take. An airtight talk description leads to an airtight abstract.

The description section of my rejected proposal was thorough but lacked direction. I was trying to sell the audience on a thesis muddled by too many arguments.

When I put together slides to give this talk at a meetup, I leaned on one of these arguments more heavily than others. This made me realize that my talk description didn't accurately reflect what I wanted to talk talk about. Instead of including every possible argument for my thesis, I rewrote my description with a focus on one.

My choice to narrow the scope of this talk was validated at the meetup: attendees loved the clear cause-and-effect relationship that I presented. Confidently settling on a focal point for my talk also helped me eliminate wishy-washy language in my description, and as you can imagine, whittling down my talk description helped me write a stronger abstract for the next round of CFPs.

But not every speaker-hopeful has taken the opportunity to practice their talk in front of an audience before applying to speak at conferences. Another technique that speakers use to find the linchpin of their proposed talk is the conclusion framework.

I learned about the conclusion framework from Bill Kennedy. He shared it with me as an exercise for succinctly expressing the purpose of my talk.

Here's my take on the conclusion framework:

I believe... [thesis]
I have shown you... [argument(s) that support thesis]
We now both agree on... [reworded thesis]
Go forth and... [call to action]

I recommend that every speaker-hopeful fill in these four sentences at least once per talk proposal. The conclusion framework acts as the speaker-hopeful's North Star: it will keep them on track as they revise their abstract and description.

Try a Meetup

Although talk proposals can be revised alone, there's nothing like presenting a talk in front of an audience to discover where a talk shines and where it flops.

When speaking at a meetup – especially a more intimate one – I preface my talk with instructions for my audience: feedback, please! I share my Twitter handle on every slide in my deck to encourage audience members to reach out. In the parlance of card suits, those who tweet at me usually share hearts.

To dig for more diamonds and spades, after the conclusion and Q&A I like to ask the audience some questions of my own beyond "Any thoughts?":

"Do you have any criticisms of my talk?"
"How did you feel about [slide]"?
"Was there anything I said that didn't feel clear?"

One diamond I received at a meetup was that I sometimes use uncommon words – English words, not jargon – on my slides. Given that my talk deals with words more than code, utilizing language that will keep the audience engaged matters deeply to me. I never would have received this feedback without presenting in front of audience members who don't speak the way I do.

Finding a meetup to speak at seems like it would be just as daunting as submitting talk proposals to conferences, but it's been so much more relaxed in my experience. I search Meetup for meetups in my area that interest me and email the organizer(s) to see if they have any open speaking opportunities.

Keep Submitting

At the end of the day, there's only one way for a newcomer to speak at a conference: by continuing to submit talk proposals to conferences.

I hope that, by sharing with you – the speaker-hopeful – how I bounced back from my recent talk proposal rejections, you feel empowered to improve your talk proposals and own the next round of CFPs. Anytime you feel discouraged by rejection, remember that you can channel that negativity into actions that make your talk even better.

Resources

Acknowledgments

Thank you to everyoneÂ – and I am fortunate there are so many of you! –Â who has helped me navigate the labyrinthine world of technical speaking. This blog post wouldn't have happened without your support.

Photo credits to Unsplash and #WoCInTechChat.

Enjoy what you read? Spread the love by sharing this piece. Have thoughts or questions? Reach out to me on Twitter or in the comments below.

This blog post was originally published in Chronicles of a Junior Dev, where I've been blogging about my first year as a software engineer. You can keep up-to-date with Chronicles by following me on Twitter.

What do you talk about during your one-on-one meetings with your engineering (or other) manager?

Alaina Kafkes — Tue, 10 Oct 2017 21:52:47 +0000

As much as I love chatting with my manager, sometimes I worry that I walk into our weekly one-on-ones woefully underprepared. My question in the discussion title says it all, but here are some related questions that I have about one-on-ones:

What subjects are typically discussed during one-on-ones?

What are your goals going into a one-on-one meeting?

What can I – a new full-time software engineer – do to get the most out of my one-on-ones?

I'd love to hear about any and all of your experiences. Thank you!

Tackling Technical Writing

Alaina Kafkes — Fri, 18 Aug 2017 14:23:39 +0000

I recently received a request from a reader for technical writing advice. As I sat down to respond, I thought back to something I heard Scott Hanselman say at We Rise Conf in June: we only have so many keystrokes left to type in our lives, so we may as well use them effectively. Why not share what I’ve learned from technical writing to a greater audience?

If you’ve never read my writing before, here’s a quick backstory.

Though I’ve been an avid writer since the days of elementary school, I got into technical writing when I found out about Medium last year. The first pieces I read weren’t about code per se, but they covered subjects like data as storytelling. I was hooked, and hastened to write my first article.

Upon becoming a Clarifai Champion in the fall of 2016, I challenged myself to write more about code. I created a well-received beginner’s guide to open source, and followed up with my step-by-step dynamic programming tutorial this summer.

Since August 2016, I’ve written a total of 10 technical writing pieces, and recently announced a new blogging initiative. I’d like to share five takeaways that I’ve learned from my year of technical writing.

(1) Break things into steps or sections.

Every technical blog post I’ve written is broken down into smaller pieces to make it more digestible to an audience with a short attention span (aka most of us on the Internet). This way someone can skim through your blog post and determine if it’s in their best interest to read it. Similarly, section headers can help a reader easily bookmark where they left off in your piece.

(2) Write about how YOU solved a technical problem.

I couldn’t find a comprehensive resource for getting into open source, so I created my own. I studied dynamic programming quite aggressively to succeed in my algorithms class, so I wrote about how I solve problems that require dynamic programming. Writing about what you learned while solving a technical problem is never a waste of words because it documents your growth, confirms your understanding, and provides a resource for future learners. Your technical writing will be more detailed and empathetic if you’ve been in the shoes of your audience!

(3) Don’t feel pressured to write only aboutÂ code.

I’ve written about “softer topics like how reading books can benefit engineers, which is a contender for my favorite technical blog post that I’ve ever written. You could write about a subject that matters to people in technologyâ€Š–â€Šsuch as takeaways from a conference, lessons learned in a first job, or thoughts on technical speakingâ€Š–â€Šand it would still be worthwhile technical writing. Remember, not all of us are software engineers.

(4) To gain an audience, leverage popular technical writing platforms.

I got a lot of traction as a technical writer by getting pieces accepted in freeCodeCamp, which is one of the biggest technical writing publications on Medium with ~300,000 followers. I sometimes publish my writing on dev.to, a technical writing platform that will tweet out your piece if they find it interesting, thereby reaching an audience of ~125,000 followers. By publishing in these and other well-known places, I gained more readership than I would have in my own network.

(5) Ask friends to look over yourÂ work!

Behind every great technical writer is a team of proofreaders. Before you hit publish, it’s helpful to see how a few friends respond to what you’ve written. Does it make sense? Is it too wordy? Are there grammatical errors? Although any good friend will be inclined to think highly of your work, probe them for any mistakes, weak arguments, or other problems in your blog post. Criticism is more easily taken from a friend than a stranger on the Internet, and more easily resolved before you publish.

These five tips have helped me write some pretty cool stuff over the past year, and I’m looking forward to my future technical writing endeavors. Now it’s your turn to try out technical writing. So get out there and whip up that blog post idea that’s been on your mind!

Enjoy what you read? Spread the love by sharing this piece. Have thoughts or questions? Reach out to me on Twitter or in the comments below.

The Goldilocks Contribution: How can someone find open source issues that challenge them just the right amount?

Alaina Kafkes — Wed, 05 Jul 2017 13:16:54 +0000

In open source, how can someone find their Goldilocks issue — one that stretches their skillset just right — in the chasm between contributions that are too easy and too hard?

I'll use myself as an example. As someone who has already had a few pull requests merged, I find that issues labeled “beginner don't seem challenging enough to help me grow. However, some issues labeled "bug" or "feature" can be over my head. My goal in contributing to open source is to give back to programming communities I care about, but also to advance my technical skills.

Demystifying Dynamic Programming

Alaina Kafkes — Wed, 28 Jun 2017 13:17:05 +0000

Maybe you’ve heard about it in preparing for coding interviews. Maybe you’ve struggled through it in an algorithms course. Maybe you’re trying to learn how to code on your own, and were told somewhere along the way that it’s important to understand dynamic programming. Using dynamic programming (DP) to write algorithms is as essential as it is feared.

And who can blame those who shrink away from it? Dynamic programming seems intimidating because it is ill-taught. Many tutorials focus on the outcomeâ€Š–â€Šexplaining the algorithmâ€Š–â€Šinstead of the processâ€Š–â€Šfinding the algorithmâ€Š–â€Šwhich encourages memorization, not understanding.

Not this one.

During my algorithms class this year, I pieced together my own process for solving problems that require dynamic programming. Parts of it come from my algorithms professor (to whom much credit is due!), and parts from my own dissection of dynamic programming algorithms.

In this post, I'll teach you my process for creating dynamic programming algorithms. But before I share this process, let’s start with the basics. What is dynamic programming, anyway?

DP Defined

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.

// Detect dark theme var iframe = document.getElementById('tweet-868089738669899776-411'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=868089738669899776&theme=dark" }

To be honest, this definition may not make total sense until you see an example of a sub-problem. That’s okayâ€Š–â€Šit’s coming up in the next section.

What I hope to convey is that DP is a useful technique because it looks through all possible sub-problems and never recomputes the solution to any sub-problem. This guarantees correctness and efficiency, which cannot be said of most techniques used to solve or approximate algorithms. This alone makes DP special.

In the next two sections, I’ll explain what a sub-problem is, and then motivate why storing solutionsâ€Š–â€Ša technique known as memoizationâ€Š–â€Šmatters in dynamic programming.

Sub-problems on Sub-problems on Sub-problems

Sub-problems are simply smaller versions of the original problem. In fact, sub-problems often look like a reworded version of the original problem. If formulated correctly, sub-problems build on each another in order to obtain the solution to the original problem.

To give you a better idea of how this works, let’s find the sub-problem in an example dynamic programming problem.

Pretend you’re back in the 1950s working on an IBM-650 computer. You know what this meansâ€Š–â€Špunchcards! Your job is to manâ€Š–â€Šor womanâ€Š–â€Šthe IBM-650 for a day. You’re given a natural number n punchcards to run. Each punchcard i must be run at some predetermined start time si and stop running at some predetermined finish time fi. Only one punchcard can run on the IBM-650 at once. Each punchcard also has an associated value vi based on how important it is to your company.

Problem: As the person in charge of the IBM-650, you must determine the optimal schedule of punchcards that maximizes the total value of all punchcards run.

Because I’ll go through this example in great detail throughout this article, I’ll only tease you with its sub-problem for now:

Sub-problem: The maximum value schedule for punchcards i through n such that the punchcards are sorted by start time.

Notice how the sub-problem breaks down the original problem into components that build up the solution. With the sub-problem, you can find the maximum value schedule for punchcards n-1 through n, and then for punchcards n-2 through n, et cetera. By finding the solutions for every single sub-problem, you can then tackle the original problem itself: the maximum value schedule for punchcards 1 through n.

Otherwise put, since the sub-problem looks like the original problem, sub-problems can be used to solve the original problem.

In dynamic programming, after you solve each sub-problem, you must memoizeâ€Š–â€Šor storeâ€Š–â€Šit. Let’s find out why in the following section.

Motivating Memoization with Fibonacci Numbers

When told to implement an algorithm that calculates the Fibonacci value for any given number, what would you do? Most people I know would opt for a recursive algorithm that looks something like this in Python:

def fibonacciVal(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fibonacciVal(n-1) + fibonacciVal(n-2)

This algorithm accomplishes its purpose, but at a huge cost. For example, let’s look at what this algorithm must calculate in order to solve for n=5 (abbreviated as F(5)):

                      F(5)  
                    /      \                  
                   /        \
                  /          \
               F(4)          F(3)
            /       \        /   \
          F(3)     F(2)     F(2)  F(1)
         /   \     /  \     /   \
       F(2) F(1) F(1) F(0) F(1) F(0)
       /  \
     F(1) F(0)

The tree above represents each computation that must be made in order to find the Fibonacci value for n=5. Notice how the sub-problem for n=2 is solved thrice. For a relatively small example (n=5), that’s a lot of repeatedâ€Š–â€Šand wastedâ€Š–â€Šcomputation!

What if, instead of calculating the Fibonacci value for n = 2 three times, we created an algorithm that calculates it once, stores its value, and accesses the stored Fibonacci value for every subsequent occurrence of n=2? That’s exactly what memoization does.

With this idea in mind, I’ve written a dynamic programming solution to the Fibonacci value problem:

def fibonacciVal(n):
  memo = [0] * (n+1)
  memo[0], memo[1] = 0, 1
  for i in range(2, n+1):
    memo[i] = memo[i-1] + memo[i-2]
  return memo[n]

Notice how the solutionâ€Š–â€Šthe return valueâ€Š–â€Šcomes from the memoization array memo[], which is iteratively filled in by the for loop. By “iteratively,” I mean that memo[2] is calculated and stored before memo[3], memo[4],Â …, and memo[n]. Because memo[] is filled in this order, the solution for each sub-problem (e.g., n=3) can be found using the solutions to its preceding sub-problems (e.g., n=2 and n=1) because these values were already stored in memo[] at an earlier time.

Memoization means no re-computation, which makes for a more efficient algorithm. Thus, memoization ensures that dynamic programming is efficient, but it is choosing the right sub-problem that guarantees overall correctness.

Now that we’ve addressed memoization and sub-problems, it’s time to learn the dynamic programming process. Buckle in.

My Dynamic Programming Process

Step 1: Identify the sub-problem inÂ words.

Too often, programmers will turn to writing code before thinking critically about the problem at hand. Not good. One strategy for firing up your brain before you touch the keyboard is using wordsâ€Š–â€ŠEnglish or otherwiseâ€Š–â€Što describe the sub-problem that you have identified within the original problem.

If you’re solving a problem that requires dynamic programming, grab a piece of paper and think about the information that you need in order to solve this problem. Write out the sub-problem with this in mind.

For example, in the aforementioned punchcard problem, I stated that the sub-problem can be written as “the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time.” I found this sub-problem by realizing that, in order to determine the maximum value schedule for punchcards 1 through n such that the punchcards are sorted by start time, I would need to find the answer to the following sub-problems:

The maximum value schedule for punchcards n-1 through n such that the punchcards are sorted by start time
The maximum value schedule for punchcards n-2 through n such that the punchcards are sorted by start time
The maximum value schedule for punchcards n-3 through n such that the punchcards are sorted by start time
(Et cetera)
The maximum value schedule for punchcards 2 through n such that the punchcards are sorted by start time

If you can identify a sub-problem that builds upon previous sub-problems in order to solve the problem at hand, then you’re on the right track.

Step 2: Write out the sub-problem as a recurring mathematical decision.

Once you’ve identified a sub-problem in words, it’s time to write it out mathematically. Why must this be done? Well, the mathematical recurrenceâ€Š–â€Šor repeated decisionâ€Š–â€Šthat you find will eventually be what you put into your code. Besides, writing out the sub-problem mathematically vets your sub-problem in words from Step 1. If it is difficult to encode your sub-problem from Step 1 in math, then it may be the wrong sub-problem!

There are two questions that I ask myself every time I try to find a recurrence:

What decision do I make at every step?
If my algorithm is at step i, what information would it need to decide what to do in step i+1? (And sometimes: If my algorithm is at step i, what information did it need to decide what to do in step i-1?)

Let’s return to the punchcard problem and ask these questions.

What decision do I make at every step? Assume that the punchcards are sorted by start time, as mentioned previously. For each punchcard that is compatible with the schedule so far (i.e., its start time is after the finish time of the punchcard that is currently running), the algorithm must choose between two options: to run, or not to run, the punchcard.

If my algorithm is at step i, what information would it need to decide what to do in step i+1? In order to decide between the two options, the algorithm needs to know the next compatible punchcard in the order.Â

If my algorithm is at step i, what information did it need to decide what to do in step i-1? The algorithm needs to know about future decisions: the ones made for punchcards i through n in order to decide to run or not to run punchcard i-1.

Now that we’ve answered these questions, perhaps you’ve started to form a recurring mathematical decision in your mind. If not, that’s also okayâ€Š–â€Šit becomes easier and easier to write recurrences as you get exposed to more dynamic programming problems.

Without further ado, here’s our recurrence:

OPT(i) = max(vi + OPT(next[i]), OPT(i+1))

This mathematical recurrence requires some explaining, especially for those who haven’t written one before. Here, I use OPT(i) to represent the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time. Sounds familiar, right? OPT(â€¢) is our sub-problem from Step 1.

In order to determine the value of OPT(i), we consider two options, and we want to take the maximum of these options in order to meet our goal: the maximum value schedule for all punchcards. Once we choose the option that gives the maximum result at step i, we memoize its value as OPT(i).

The two optionsâ€Š–â€Što run or not to run punchcard iâ€Š–â€Šare represented mathematically as follows:

vi + OPT(next[i])

This clause represents the decision to run punchcard i. It adds the value gained from running punchcard i to OPT(next[i]), where next[i] represents the next compatible punchcard following punchcard i. OPT(next[i]) gives the maximum value schedule for punchcards next[i] through n such that the punchcards are sorted by start time. Adding these two values together produces maximum value schedule for punchcards i through n such that the punchcards are sorted by start time if punchcard i is run.

OPT(i+1)

Conversely, this clause represents the decision to not run punchcard i. If punchcard i is not run, its value is not gained. OPT(i+1) gives the maximum value schedule for punchcards i+1 through n such that the punchcards are sorted by start time. Otherwise stated, OPT(i+1) gives the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time if punchcard i is not run.

In this way, the decision made at each step of the punchcard problems is encoded mathematically to reflect the sub-problem in Step 1.

Step 3: Solve the original problem using Steps 1 andÂ 2.

In Step 1, we wrote down the sub-problem for the punchcard problem in words. In Step 2, we wrote down a recurring mathematical decision that corresponds to these sub-problems. How can we solve the original problem with this information?

OPT(1)

It’s that simple. Since the sub-problem we found in Step 1 is the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time, we can write out the solution to the original problem as the maximum value schedule for punchcards 1 through n such that the punchcards are sorted by start time. Since Steps 1 and 2 go hand in hand, the original problem can also be written as OPT(1).

Step 4: Determine the dimensions of the memoization array and the direction in which it should beÂ filled.

Did you find Step 3 deceptively simple? It sure seems that way. You may be thinking, how can OPT(1) be the solution to our dynamic program if it relies on OPT(2), OPT(next[1]), et cetera?

You’re correct to notice that OPT(1) relies on the solution to OPT(2). This follows directly from Step 2:

OPT(1) = max(v1 + OPT(next[1]), OPT(2))

But this is not a crushing issue. Think back to Fibonacci memoization example. In order to find the Fibonacci value for n=5, the algorithm relied on the fact that the Fibonacci values for n=4, n=3, n=2, n=1, and n=0 had already been memoized. If we fill in our memoization table in the correct order, the reliance of OPT(1) on other sub-problems is no big deal.

How can we identify the correct direction to fill the memoization table? Well, in the punchcard problem, since we know OPT(1) relies on the solutions to OPT(2) and OPT(next[1]), and that punchcards 2 and next[1] have start times after punchcard 1 due to sorting, we can infer that we need to fill our memoization table from OPT(n) to OPT(1).

How do we determine the dimensions of this memoization array? Here’s a trick: the dimensions of the array are equivalent to the number and size of the variables on which OPT(â€¢) relies. In the punchcard problem, we have OPT(i), which means that OPT(â€¢) only relies on variable i, which represents the punchcard number. This suggest that our memoization array will be one-dimensional and that its size will be n since there are n total punchcards.

If we know that n=5, then our memoization array might look like this:

memo = [OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

However, because many programming languages start indexing arrays at 0, it may be more convenient to create this memoization array so that its indices align with punchcard numbers:

memo = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Step 5: CodeÂ it!

To code our dynamic program, we put together Steps 2–4. The only new piece of information that you’ll need to write a dynamic program is a base case, which you can find as you tinker with your algorithm.

A dynamic program for the punchcard problem will look something like this:

def punchcardSchedule(n, values, next):
 '''Where values stores the punchcard values (ordered by punchcard start time)
        & next[i] stores the next punchcard that can run after punchcard i'''
 # Initialize memoization array - Step 4
  memo = [0] * (n+1)

 # Set base case
  memo[n] = values[n]

 # Build memoization table from n to 1 - Step 2
  for i in range(n-1, 0, -1):
    memo[i] = max(values[i] + memo[next[i]], memo[i+1])

 # Return solution to original problem OPT(1) - Step 3
  return memo[1]

Congrats on writing your first dynamic program! Now that you’ve wet your feet, I’ll walk you through a different type of dynamic program.

Paradox of Choice: Multiple Options DPÂ Example

Although the previous dynamic programming example had a two-option decisionâ€Š–â€Što run or not to run a punchcardâ€Š–â€Šsome problems require that multiple options be considered before a decision can be made at each step.

Time for a new example.

Pretend you’re selling the friendship bracelets to n customers, and the value of that product increases monotonically. This means that the product has prices {p1,Â …, pn} such that pi â‰¤ pj if customer j comes after customer i. These n customers have values {v1,Â …, vn}. A given customer i will buy a friendship bracelet at price pi if and only if pi â‰¤ vi; otherwise the revenue obtained from that customer is 0. Assume prices are natural numbers.

Problem: You must find the set of prices that ensure you the maximum possible revenue from selling your friendship bracelets.

Take a second to think about how you might address this problem before looking at my solutions to Steps 1 and 2.

Step 1: Identify the sub-problem inÂ words.

Sub-problem: The maximum revenue obtained from customers i through n such that the price for customer i-1 was set at q.

I found this sub-problem by realizing that, in order to determine the maximum revenue for customers 1 through n, I would need to find the answer to the following sub-problems:

The maximum revenue obtained from customers n-1 through n such that the price for customer n-2 was set at q.
The maximum revenue obtained from customers n-2 through n such that the price for customer n-3 was set at q.
(Et cetera)

Notice that I introduced a second variable q into the sub-problem. I did this because, in order to solve each sub-problem, I need to know the price I set for the customer before that sub-problem. Variable q ensures the monotonic nature of the set of prices, and variable i keeps track of the current customer.

Step 2: Write out the sub-problem as a recurring mathematical decision.

There are two questions that I ask myself every time I try to find a recurrence:

What decision do I make at every step?
If my algorithm is at step i, what information would it need to decide what to do in step i+1? (And sometimes: If my algorithm is at step i, what information did it need to decide what to do in step i-1?)

Let’s return to the friendship bracelet problem and ask these questions.

What decision do I make at every step? I decide at which price to sell my friendship bracelet to the current customer. Since prices must be natural numbers, I know that I should set my price for customer i in the range from qâ€Š–â€Šthe price set for customer i-1â€Š–â€Što viâ€Š–â€Šthe maximum price at which customer i will buy a friendship bracelet.

If my algorithm is at step i, what information would it need to decide what to do in step i+1? My algorithm needs to know the price set for customer i and the value of customer i+1 in order to decide at what natural number to set the price for customer i+1.

With this knowledge, I can mathematically write out the recurrence:

OPT(i, q) = max~([Revenue(vi, a) + OPT(i+1, a)])
such that max~ finds the maximum over all a in the range q â‰¤ a â‰¤ vi

Once again, this mathematical recurrence requires some explaining. Since the price for customer i-1 is q, for customer i, the price a either stays at integer q or it changes to be some integer between q+1 and vi. To find the total revenue, we add the revenue from customer i to the maximum revenue obtained from customers i+1 through n such that the price for customer i was set at a.

In other words, to maximize the total revenue, the algorithm must find the optimal price for customer i by checking all possible prices between q and vi. If vi â‰¤ q, then the price a must remain at q.

What about the otherÂ steps?

Working through Steps 1 and 2 is the most difficult part of dynamic programming. As an exercise, I suggest you work through Steps 3, 4, and 5 on your own to check your understanding.

Runtime Analysis of DynamicÂ Programs

Now for the fun part of writing algorithms: runtime analysis. I’ll be using big-O notation throughout this discussionâ€Š–â€Šif you’re not yet familiar with big-O, I suggest you read up on it here.

Generally, a dynamic program’s runtime is composed of the following features:

Pre-processing
How many times the for loop runs
How much time it takes the recurrence to run in one for loop iteration
Post-processing

Overall runtime takes the following form:

Overall runtime = Pre-processing + Loop * Recurrence + Post-processing

Let’s perform a runtime analysis of the punchcard problem in order to get familiar with big-O for dynamic programs. Here is the punchcard problem dynamic program:

def punchcardSchedule(n, values, next):
 '''Where values stores the punchcard values (ordered by punchcard start time)
        & next[i] stores the next punchcard that can run after punchcard i'''
 # Initialize memoization array - Step 4
  memo = [0] * (n+1)

 # Set base case
  memo[n] = values[n]

 # Build memoization table from n to 1 - Step 2
  for i in range(n-1, 0, -1):
    memo[i] = max(values[i] + memo[next[i]], memo[i+1])

 # Return solution to original problem OPT(1) - Step 3
  return memo[1]

Let’s break down its runtime:

Pre-processing: Here, this means building the the memoization array. O(n).
How many times the for loop runs: O(n).
How much time it takes the recurrence to run in one for loop iteration: The recurrence takes constant time to run because it makes a decision between two options in each iteration. O(1).
Post-processing: None here! O(1).

The overall runtime of the punchcard problem dynamic program is O(n) O(n) * O(1) + O(1), or, in simplified form, O(n).

You Did It!

Well, that’s itâ€Š–â€Šyou’re one step closer to becoming a dynamic programming wizard!

One final piece of wisdom: keep practicing dynamic programming. No matter how frustrating these algorithms may seem, repeatedly writing dynamic programs will make the sub-problems and recurrences come to you more naturally. Here’s a crowdsourced list of classic dynamic programming problems for you to try.

So get out there and take on your interviews, classes, and life (of course) with your newfound dynamic programming knowledge!

Many thanks to Steven Bennett, Claire Durand, and Prithaj Nath for proofreading this blog post. You all rock. Thank you Professor Hartline for getting me so excited about dynamic programming that I willingly wrote about it at length.

Enjoy what you read? Spread the love by liking and sharing this piece! Have thoughts or questions? Reach out to me on Twitter or in the comments below.

How can someone prepare for their first full-time software engineering job?

Alaina Kafkes — Thu, 25 May 2017 15:43:00 +0000

Alternatively: what do you expect from new grad/junior software engineers that join your team?

Thanks in advance for your thoughts. ðŸŽ‰

On Literature and Linked Lists

Alaina Kafkes — Mon, 08 May 2017 20:03:16 +0000

Up until recently, my experience with reading for pleasure followed a typical-but-sad trajectory. I got hooked on reading at a young age, often consuming several novels per week. Then, high school extracurriculars and college applications caused my reading frequency to nosedive to almost never. This habit followed me into college: part of why I studied computer science was its promise of project-based work instead of the incessant reading that characterizes many other majors.

Reading decline is not a new story, and fortunately, it was not the end of mine. Remembering the glory days of elementary school, I grabbed Make It Stick and The Glass Palace â€Š– â€Štwo books that friends had lent to me – and finished them over my winter break. These books drew me back in, hook, line, and sinker. Since winter break, I have pored through ten other books. It feels fantastic to reconnect with this childhood joy!

However, as a computer science latecomer, I’ve always felt the pressure to code, code, code in my spare time. I couldn’t help but wonder:

Would spending my free time reading hinder the development of my software engineering skills?

My conclusion? Improving technical acumen is super important, but readers have a few traits from which software engineers can learn. I present to you the ways in which I believe reading can make someoneâ€Š – â€Šlike me, and perhaps like you! â€Š–â€Š a better software engineer.

(Slight caveat: my arguments may also apply to non-engineering roles, but I frame them in the context of the career I know best.)

Reading books from different voices enhances yourÂ empathy.

One research study suggests that fiction books build more empathy in readers than nonfiction books. Another study detailed in Scientific American corroborated these results in comparing popular fiction, literary fiction, and nonfiction books.

I think what explains this result is that reading fictionâ€Š – â€Šespecially literary fictionâ€Š – â€Šencourages the reader to develop empathy. While many of us are guilty of pigeonholing people on the Internet into stereotypes (picture any toxic comments thread), literary fiction discourages such stereotyping. Because the characters in literary fiction tend to have complex personalities that defy labels, readers have to work harder to understand them. Through this work, readers gain a sorely needed ability: imagining reality from a different perspective.

So why should you, an engineer, get comfortable with new perspectives? You hopefully want to design a product that suits your users well. How can you learn what works well for your users? It takes empathy to understand your user’s needs, potential pain points, and goals. You must put yourself in the target user’s shoes – â€Šsometimes literally â€Š–â€Š to build meaningful products.

Reading fiction is a practice that fosters empathy, and a great place to start developing the empathy necessary for your engineering work. But, let’s say fiction isn’t your cup of tea. Not to worry â€Š–â€Š the next three takeaways focus on the benefits of a broader selection of books, not just fiction.

Reading can make you a better problem-solver.

To most software engineers, “problem-solver” sounds like an clichÃ© resume buzzword that suggests that someone is adept at addressing bugs and failed deployments. However, the problems that engineers must solve in their day-to-day work go beyond the technical.

Engineering takes teamwork, so software engineers often need to deal with team-related problems. Engineers also write a good deal of code on their own, so they also need to be able to address blockers: technical and non-technical impediments on their progress. Fortunately, reading can build the unspoken but essential problem-solving skills needed to overcome personal and interpersonal issues.

As silly as it sounds, reading books like the Harry Potter series and comics like Avatar: The Last Airbender when I was younger taught me the importance of healthy team dynamics. These children’s books guided me to behave with respect, honesty, and kindness in all of my relationships. If I see a teammate in trouble, I’m more than willing to take a stab at the problem myself, or connect them with someone else who can help. If a conflict arises in my team, I know that the books I have read shown me how to resolve it without damaging the integrity of my team.

I also draw upon books to guide myself and others through the personal struggles we face in our professional lives. When my sister faltered in her study habits as a college freshman, I relayed advice that I had read in Make It Stick about how to maximize information retention. When younger members of Women in Computingâ€Š – â€Ša club I co-organized in college – wanted to rekindle their passion for technology, I suggested they read pop science books like The Code Book.

Readers act as a net that accumulates knowledge from a variety of sources. Upon encountering a problem, they can use any pertinent knowledge that they’ve picked up to provide advice, direction, or even a solution. This is how reading can impact a software engineer’s problem-solving skills.

Reading inspires constant curiosity.

Readers are inherently curious people. After all, why even pick up a book if you weren’t curious about learning something?

Many software engineers treat a technical career as something routine: from stand-up to stand-up, they fall under the illusion that they must do the same thing day in and day out. They trudge along, waiting for a clear-cut promotion from engineer to senior/staff engineer or engineering manager. Even in that new role, they lapse into the same old patterns.

With this mindset, it’s easy to live humdrum lives and work humdrum jobs.

I see curiosity as the antidote to monotony.

Curiosity is a spark that makes you wonder about everything. The more you wonder, the more you question, and the more you question, the more you can create! Software engineering is meant to be a creative practice, one in which you can slip indefinitely into flow state.

Of all the takeaways I’ve outlined, I think the benefits of curiosity are most noticeable in an engineering career. Though we tend to praise â€˜geniuses’ in the tech industry, I believe that we should just as strongly exalt engineers who are curious. After all, research suggests that curiosity leads to higher investment in intellectual pursuits over time. Curiosity becomes its own kind of genius.

Curiosity is impactful in the short-term, too. Curious engineers may express new ideas in meetings or try new ways of approaching bugs. Curiosity underpins empathy. Unsurprisingly, research shows that curiosity leads to greater performance at work because curiosity drives engineers to perform several notches above what is expected of them.Â

Curiosity is the ultimate game-changer in software engineering careers.

Reading reducesÂ stress.

Stress management is nothing new. Many people already have techniques that they use to keep their stress levels low; from meditation to morning walks, I applaud those who have found what works for them.

However, in the office, we don’t always have the space to meditate, or the time to get outside and move around. Reading acts as a convenient alternative: it’s never disruptive to pull out a book at one’s desk or in a lounge area. Better yet, researchers found that reading reduces stress by as much as 68 percentâ€Š–â€Šsignificantly more than any other stress-relieving activity testedâ€Š–â€Šand that as little as six minutes of reading is enough to notice these benefits. Social anthropologist Ceridwen Dovey even penned a piece in The New Yorker about the effectiveness of bibliotherapy on increasing happiness.

It has been shown that happiness really does boost productivity, and that too much stress can destroy it. Since reading has the power to lessen stress and raise happiness, I believe that it is the key to a more productive workplace with more content engineers.

There you have it, future employers. Ask me how I can apply the books I’ve read to software engineering, not how to implement yet another balanced binary tree. ðŸ˜‰

In all seriousness, the impact that reading booksâ€Š –â€Š yes, even non-technical, non-Cracking the Coding Interview books â€Š–â€Š can have on a software engineer’s career is tremendous. Just as it is never too late to start coding, it is never too late to bury your nose in a good book and benefit from these takeaways.

Enjoy what you read? Spread the love by sharing this piece. Have thoughts, questions, or book recommendations? Reach out to me on Twitter or in the comments below. Want to see what I've been reading? Check out my Tumblr.