In an earlier posting I described, slightly abstractly, what we’re looking for in article proposals for Code Quarterly Below is a sample proposal I wrote for an article that I’m in fact planning to write. Keep in mind that this is just one example; there are as many ways to write a successful proposal as there are articles to be written. Another thing to keep in mind is that this is as finished a proposal as I could make—it’s not necessary to write something like this before you get in touch with us. As I’ve said before we’re happy to help writers develop their ideas. With all that it mind, here it is.
“If you don’t know what dynamic programming is, then you’re at a severe disadvantage. It’s going to come up time and time again.” —Peter Norvig, Coders at Work
Dynamic programming is, as the text Algorithms by Dasgupta, Papadimitrious, and Vazirani describes it, one of the “sledgehammers of the algorithms craft”. When it is applicable, dynamic programming can solve problems in polynomial time where a naïve brute force solution would grow exponentially. As Peter Norvig says, a programmer who doesn’t understand dynamic programming is at a disadvantage because it shows up again and again. Not only will such a programmer be missing an important tool from their own tool box, but they will also have a hard time understanding many interesting and important bits of code that use dynamic programming, such as Knuth’s famous line breaking algorithm or the core algorithm in the program
Unfortunately, dynamic programming is a topic that seems to inspire tutorials that are either understandable only by people who already understand dynamic programming or which go so far in their attempts to simplify things as to veer into oversimplification. (Programmers who came through a good university computer science program will probably have been taught about dynamic programming though even the academics are sorting out the best way to teach it: the third edition of the widely-used algorithms text, Introduction to Algorithms, published in 2009, advertises “improved treatment of dynamic programming” as one of its features.)
My piece will aim to provide an in-depth introduction to dynamic programming understandable by programmers who’ve never heard of it as well as by those who’ve already been confused by the tutorials that Googling “dynamic programming” will turn up. I will explain the origins of dynamic programming as a mathematical technique for solving planning problems, demonstrate its use as a computer programming technique with a few simple examples, and then look at several famous algorithms that use dynamic programming.
For my simple examples, I plan to use the problems of computing the nth Fibonacci number and counting the number of ways of making change for a given amount of money with certain denominations of coins. Computing Fibonacci numbers is an appealing first example—several existing tutorials use it as well—because it is a very simple problem that has both of the characteristics necessary for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. However it can be a tricky pedagogical device because it is so simple; I will use it to establish what optimal substructure and overlapping sub-problems are but will then be very careful to make clear the connection between that example and the more complex ones to follow.
The change counting problem, which comes from one of the early chapters of the classic, Structure and Interpretation of Computer Programs, is slightly more complex. Unlike the Fibonacci problem, it’s not entirely obvious how to turn a simple recursive function into an iterative one, one of the exercises posed in the book. However, as I’ll show, it’s easy if you use dynamic programming.
While working through these two examples I will discuss the difference between simple recursion (not dynamic programming), recursion with memoization (a way of doing top-down dynamic programming), and classic bottom-up dynamic programming and show how to start with simple recursion and convert it to the other two forms.
This last distinction—between top-down and bottom-up—is particularly important. Some authors try to simplify the presentation of dynamic programming by limiting their explanation to recursion with memoization. While that is one way to implement a dynamic programming algorithm, it leaves the reader unprepared to understand code that uses bottom-up dynamic programming. Also, such top-down algorithms are often less efficient than bottom-up versions due to the overhead of recursion. And for problems where the maximum depth of the recursion is linear with the size of the input, recursive solutions won’t work for large inputs if the language or runtime limits how deeply function calls can recurse.
After presenting the simple examples, I will examine a few historically important and and interesting algorithms that use dynamic programming: the TeX line breaking algorithm described in Knuth’s “Breaking Paragraphs into Lines”, the longest common subsequence algorithm described in Hunt and McIllroy’s paper about the original Unix diff program, “An Algorithm for Differential File Comparison”, and perhaps one more.
I’ll explain these algorithms by reimplementing the key parts in Python, showing first a straightforward implementation using dynamic programming and then explaining some of the tricks described in those papers to make the naive dynamic programming implementation more efficient.
After reading my article, a reader should be will prepared to use dynamic programming in their own code and to recognize and understand its use in other algorithms.
The first step toward writing an article for Code Quarterly is to write a proposal. But you should not think of the proposal as an arbitrary hurdle you have to jump over in order before you can get to writing the article. Really it’s the beginning of your work on your article; the questions you will have to wrestle with to write a good proposal are the same questions you will face when you write the full article.
Here are some of those questions. These apply most directly to technical explanations, think pieces, and articles on computer history. Q&A interviews and book reviews are in some ways more straightforward and I’ll discuss them in a later post.
What is your topic? And, more important, what, in particular, do you want to say about it? It’s fine to start with a broad topic (e.g. “how optimizing compilers work”) but you then need to narrow it to something you can actually cover.
Do you have a firm grasp on the topic? Your own understanding of the topic will almost always need to be broader than what you’re actually going to cover in your piece. At the proposal stage, it’s okay to leave some things to be researched later but it’d be better not to discover things while writing that completely disrupt your plans.
What else has been said about this topic? How is what you are going to say going to add to the conversation? (Quick test: Google your topic and look at the top five hits. Is your article going to be worth reading to someone who has already read those five web pages?)
Why will our readers be interested in your article? This is your chance to start putting yourself in the reader’s shoes and articulating why they are going to want to read what you have to say.
How are you going to organize your article? There are lots of ways to structure the same information and writing is fundamentally about how you choose to do it. For instance, if you are writing about a particular programming technique, you could start with some simple code using the technique and build up to more complex examples or you could start with a realistically complex example which you then explain bit by bit. Or you could discuss the historical development of the technique and show what motivated each step in its history. Or something else. There is no one best structure for a given topic; it depends on what you are trying to accomplish and who you think your readers will be.
Once you think you know the answers to these questions, you’re ready to actually write a proposal. Quite likely, the act of actually writing down your thoughts will—if you pay attention—reveal where those thoughts are not as well formed as they seemed when they were rattling around in your head. That’s fine; it just means you need to circle back and do some more thinking.
In a perfect world, the first thing you send us would be a completed proposal that answers all these questions and gives us a good sense of your writing style. But that may be asking a bit much, especially if you’re new to the writing game. So, if you’re interested in writing for us, you should feel free to get in touch whenever you feel like you could use some help. As I’ve said elsewhere, we’re more interested in getting good content than in streamlining our process and we’re willing—indeed, we’re planning—to work quite closely with our authors. As long as it feels like each iteration is moving us closer toward a good proposal and, later, toward a good article, we’ll be happy to keep working with you.
Since I first announced Code Quarterly a few months ago, there’s been what seems to me a very healthy expression of interest in the idea. Over 1,400 people have filled in the form at our website indicating they might want to subscribe, buy copies, or write for us.
On many fronts things are proceeding apace: I’ve formed a corporation so I won’t lose my house if something goes south, and we’ve drawn up a standard writer’s contract. I’ve also found a handful of folks to help me out with various aspects of getting this thing going including a former Byte magazine editor who’s been giving me the benefit of his experience and a designer who’s been typesetting some gorgeous sample articles. So I’m very excited that we will be able to produce a high-quality, great-looking print journal and I’ve been thinking about all the other ways we could publish things.
However there’s one big question that remains open: will we be able to find enough good articles of the sort we want to publish? A couple hundred people have expressed interest in writing for Code Quarterly, but I’ve received fewer than a dozen proposals and of those, only a handful have been right for us. So I thought I’d take this chance to talk a little bit more about why you, or someone you know, might consider writing for the Quarterly and to expand a bit on the kind of thing we’re looking for.
What’s in it for you?
While we will share our profits 50/50 with our authors, I have to admit there’s no guarantee that those profits will be large or even greater than zero. So I can’t suggest that you write for us as a way to get rich.
But there are other rewards to writing, chief among them, the joy of creation. And the joy of creation is greatest when you create something really good. If you write for us, we will work with you throughout the writing process to help you write the best piece you possibly can.
If you’ve never had the experience of someone taking apart your writing and helping you put it back together so it says exactly what you mean in a way people will want to read, this may be your chance. Or if you have ideas but aren’t sure the best way to organize them, we can help. Or if you just think you would benefit from having someone pointing out where you need to dig deeper and where you could be more clear, we can do that too.
This kind of editorial guidance is something you probably won’t get writing for your own blog or website. And, at least based on my own experience, and that of several other authors I’ve talked to, you’re not likely to get it from traditional tech book publishers either.
So whether you’re a new writer daunted by the blank screen or an experienced writer who appreciates the value of a good editorial sounding board, you should consider writing for us.
What we want
Still reading? Thinking about writing for us? Good. Now, what kind of thing are we looking for? To start with, let me mention one change of plans. In early versions of our writer’s guidelines, I said we were looking specifically for long pieces—in the 8,000 to 20,000 word range. I now think that was unnecessarily restrictive. Though we are still interested in long pieces, the current plan is to publish pieces of a variety of lengths and I’ve updated the writer’s guidelines accordingly.
I think our tagline, “The Hackademic Journal,” captures quite well what we are about. To me, the essence of hacking is a combination of curiosity and pragmatism. Like academics, hackers like to explore ideas, to learn new things, and to understand concepts fully—there’s a reason that hacker jargon is where Heinlein’s word grok found a home. But hackers also like to build stuff—ideas purely for ideas’ sake are for academics, not hackers. Yet it’s possible to take our pragmatism too far—sometime there’s nothing as practical as a good theory. I want Code Quarterly to fill the niche between academic journals, which can be dry and inaccessible, and a lot of mainstream tech writing, which, sadly, is often superficial, ahistorical, or badly written. And sometimes all three.
We want to publish clearly written explanations of useful bits of theory, critiques of interesting bits of actual code, explorations of the history of our field, interviews with the leaders of our field, and book reviews that say more than just whether the reviewer liked or disliked the book. We care less about original results than academic journals but more about good writing.
In future postings, I’ll talk more about the different kinds of articles we are looking for and what we are looking for in proposals. Until then, if you have any questions or comments, feel free to leave them here or to drop me an email.