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.