Dynamic Programming Basics for UVa 787


In programming contests, some algorithms and techniques get more emphasis than they do in school or in professional programming work. One such technique is dynamic programming. CP3 has this to say about dynamic programming:

This technique was not known before 1940s, nor frequently used in ICPCs or IOIs before mid 1990s, but it is considered a definite prerequisite today. As an illustration: There were ≥3 DP problems (out of 11) in the recent ICPC World Finals 2010.

As you might expect for such a popular competitive programming topic, uHunt has twenty-one starred problems, divided into seven sub-categories, for dynamic programming practice. As I make my way through that list, I’ll be writing about a selection of these problems. Today I’ll cover the first one, UVa 787: Maximum Sub-sequence Product.

« Continue »

Write Your Own Manual


You can become a better software developer by improving your ability to organize information. A key part of that skill is being able to communicate what you know in writing. Whether you’re enlightening your peers on Stack Overflow or writing FAQs for your team, it’s good to have a reputation as a person who Knows The Answers. If you can write clear technical designs, how-to guides, and other documentation, you can have a lot of influence. In fact, even if you just write for yourself, you can get things done faster by avoiding trips to the Web to repeatedly look up the same information.

Here are some tips on when, what, and how to write as a programmer.

« Continue »

Rules for Working Intensely


Cal Newport likes to distill the components of productivity into the following formula:

Work Accomplished = Time Spent x Intensity

We all have 24 hours per day, excluding the occasional leap second. That plus the need for sleep puts an upper limit on the Time Spent component of the formula. Intensity, in theory, has no upper limit. You could spend a lifetime getting better at concentrating. So it would seem that the Intensity component is the one to target for improvement.

There’s some truth to that analysis. Cal’s fixed-schedule productivity technique starts by making Time Spent a constant. Intensity is the only component you’re allowed to adjust.

But as you make your way toward that gloriously fixed schedule, it’s helpful to track how many hours you’re actually working, as well as how intensely you’re focusing during those hours. To do that, you have to follow a few rules.

Here are four rules to make use of the Work Accomplished formula.

« Continue »

The Trouble With Books


I love the idea of books. Years ago, I used to browse in bookstores. I bought paper copies of some of the books I looked at, and read some of the books I bought. Once Amazon came along, I clicked around their suggested items list for ideas. These days, I keep an Amazon wish list of Kindle books. When I’m reading online and someone recommends a book that looks interesting, I add it to the list. Often I can download it from my local public library. Sometimes I’ll buy a copy if a book is too popular to get from the library, or if I just decide that I want to have it around.

I find that always having an ebook on my phone is the best way to read more books. When I have some spare time, instead of clicking around the usual sites, I can read a few pages of a book. When I’m done with it, I download another one. Since the books are electronic, I don’t have books lying around taking up space and waiting to be read.

In some ways, it’s a better time to be a reader of books than it has ever been. But books still aren’t perfect. Here are a few complaints about (nonfiction) books.

« Continue »