Programming Pearls Col 1 – Cracking the Oyster

Before starting to read Programming Pearls, I have never seriously considered the true importance of approaches stemmed from algorithms. Whenever I tried my hands on harder problems on LeetCode, I’ve always thought that coming up with an optimal solution in the blink of an eye is an activity reserved to only the geniuses and the brightest of them all.

But after just reading col. 1 from Programming Pearls, I realized how forgetful I am of all the power I have from the knowledge of algorithms. And from asking a simple question as “How do I sort a disk file?”, the approach of asking the right questions and framing a problem properly is not reserved to computer science Ph.D.’s only – everyone should be able to do so.

Consider the file sorting problem. We ask some questions first to make proper assumptions about data: What is the input? What is the desired output? What is the data? What are the constraints on the data? How big is the input file? What are the time and memory constraints?

As soon as we have answers to these questions, we formally define the problem by listing the input, output, and constraints.

Now we begin to construct several solutions and compare them. In this case, solutions using merge sort (time-efficient) and a multipass sort (memory-efficient) were proposed.

Some may stop here and pick one to end problem-solving process, but we can even dream bigger and go further, because we haven’t exploited all the conditions we have.  Can we do better than O(nlogn) sorting with non-specialized data? No. But can we save space by compressing data (representing data in a different way)? Definitely.

Then we arrive at the bitmap representation of numbers. Since the file contains unique numbers only, this satisfies the requirements for our problem. This marks the end of the disk file sorting problem, but there are many other considerations left to explore for the reader.

What was especially interesting to me were the design problems proposed at the end of the chapter. These are questions designed to challenge how the reader, after being inspired by the disk file sorting problem, thinks about other tricky problems. I have been afraid of the large scope of a design-oriented problem, but this chapter encouraged me to think about all the tools I have at hand to propose as many solutions as possible and compare them at the end.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s