Debugging and Code Optimization

Debugging

• Turn on compiler/interpreter warnings. Although inexperienced programmers sometimes view warnings as a nuisance, they help catch some bugs at the early stages of software implementations.

• Use assert statements. Each time there is a condition that must be true at a certain point of the program, add the following line:

---

 assert(condition)

---

A precondition is a statement that has to be true before the call to a function. Whereas a postcondition is a statement that has to be true after the call to a function. It makes sense to state preconditions and postconditions for every function in a program. For example, it would save time if the following line

---

 assert($index_1$ $\neq$ $index_2$ )

---

is added to the code when implementing an algorithm for the Maximum Pairwise Product Problem discussed previously.

The assert statements can also be used to ensure that a certain point in a program is never reached. See the following pseudocode for computing the greatest common divisor of two positive integers.

---

 $GreatestCommonDivisor$($a$, $b$):
 assert($a$ $\geq$ $1$ and $b$ $\geq$ 1)
 for $d$ from min($a, b$) downto $1$:
  if $a$ mod $d = 0$ and $b$ mod $d = 0$:
   return $d$
 assert(False)

---

• Do not optimize the code at the early stages. As Donald Knuth once said, “premature optimization is the root of all evil in programming.” The code should be correct and have the expected asymptotic runtime. Do not apply any non-asymptotic optimizations before ensuring the correctness of the code. Suppose the code is correct. In that case, it does not get the wrong answer feedback from the grader but is still too slow and gets a time limit exceeded message. After that, start optimizing it. Measure its running time and locate bottlenecks in the code. Note that when compilers apply code optimization, even professional programmers have difficulties predicting bottlenecks.

• Be careful with recursion. In some cases, recursive solutions are easier to implement and more readable than corresponding iterative solutions. For example, it is easier to explore graphs recursively rather than iteratively. Also, for many dynamic programming algorithms, it is natural to first implement a recursive approach and then convert it into an iterative one if needed. As usual, advantages come together with some disadvantages. The main two cons of recursion that should be kept in mind are the following.

• Stack overflow: When using recursion, make sure to avoid the stack overflow issue that usually occurs due to high recursion depth. Test your program on inputs that force it to make deep recursive calls (say, a graph that is just a path with $10^5$ nodes). Increase the stack size if needed.

• Performance: In many cases (but not always!), an iterative solution is faster and uses less memory than the corresponding recursive one. The reason is that a recursive solution needs to store all function calls and its local variables on stack.

Integers and floating point numbers

• Avoid integer overflow. Check the bounds on the input values, estimate the maximum value for the intermediate results, and pick a sufficiently large numeric type. When computing modulo $m$, take every intermediate result modulo $m$.

Let’s say you want to compute the remainder of the product of all elements of $array$ modulo $17$. The naive way of doing this is the following:

---

 $product$ $\leftarrow$ 1
 for $element$ in $array$:
  $product$ $\leftarrow$ $product$ $\cdot$ $element$
 return $product$ mod $17$

---

In languages with integer overflow (like C++ and Java), this will give a wrong result in many cases. Even if an array has only 100 elements and all its elements are equal to 2, the product does not fit into 64 bits. In languages with out-of-the-box long arithmetic, this code will be slower than needed as the product gets larger at every iteration. For example, in Python, both pow(a, b, m) and pow(a, b) % m compute $a^b$ mod $m$, but the former one works faster. The right way to compute the product is the following.

---

 $product$ $\leftarrow$ $1$
 for $element$ ...