-
Programming Pearls: Chapter 11
Problems from Column #11: Sorting Lessons from Programming Pearls: Work on the right problem. Explore the design space of solutions. Look at the data. Use the back of the envelope. Exploit symmetry Design with components. Build prototypes. Make tradeoffs when you have to. Keep it simple. Strive for elegance. First implementation of quicksort: template <class I, class C> bool is_partitioned(I begin, I end, I mid, C cmp) { while (begin < end) { if (!
Read more… -
Programming Pearls: Chapter 10
Problems from Column #10: Squeezing Space Problem #1 In the late 1970’s Stu Feldman build a Fortran 77 compiler that barely fit in a 64-kilobyte code space. To save space he had packed some integers in critical records into four-bit fields. When he removed the packing and stored the fields in eight bits, he found that although the data space increased by a few hundred bytes, the overall size of the program went down by several thousand bytes.
Read more… -
Programming Pearls: Chapter 9
Problems from Column #9: Code Tuning Note: I did skip several problems from several columns because I didn’t find them particularly useful. Several of the questions here on out are also pretty dated so I’m just going to jump around to the ones that I like. Lessons Speed comes from knowing your data and specializing. ** This comes with what can be a huge cost in terms of maintainability. For most programs this speed is only required in a small part of the program.
Read more… -
Programming Pearls: Chapter 4
Problems from Column #4: Writing Correct Programs Lessons Consider using formal verification methods on tricky functions Loop invariants are a helpful tool Problem #1 As laborious as our proof of binary search was, it is still unfinished by some standards. How would you prove that the program is free of run-time errors (such as division by zero, word overflow, variables out of declared range, or array indices out of bounds)?
Read more… -
Programming Pearls: Chapter 3
Problems from Column #3: Data Structures Programs Lessons Proper view of data structures programs ** The data a system is to process gives deep insight into a good module structure ** Understand the input, the output, and the intermediate data structures Separate data from control (e.g. Model+View+Controller) Don’t write a big program when a little one will do ** The more general problem may be easier to solve (Polya’s “Inventor’s Paradox”) Problem #1 As the second edition of this book goes to press, individual income in the United States is taxed at five different rates, the maximum of which is around forty percent.
Read more… -
Programming Pearls: Chapter 2
Problems for Column #2: “Aha! Algorithms” Lessons Break problem down into primitives for which there are known algorithms. “A Problem Solver’s Perspective”: Good programmers are a little bit lazy: they sit back and wait for an insight rather than rushing forward with their first idea. Problem #1 Consider the problem of finding all the anagrams of a given input word. How would you solve this problem given only the word and the dictionary?
Read more… -
Programming Pearls: Chapter 1
Some notes and solutions to the Column #1: “Cracking the Oyster” in Programming Pearls by Jon Bentley. Lessons Ask the right question. Similar to “5 Whys”; make sure you understand the real problem. Look for simple designs “A designer knows he has arrived at perfection now when there is no longer anything to add, but when there is no longer anything to take away.” – Antoine de Saint-Exupéry
Read more…