Good programming practice

This is a non-exhaustive guide to writing programs with good style:

  1. Use meaningful variable names.
  2. Indent properly.
  3. Include lots of comments. There should be comments at the top regarding the purpose of the program and the expected input and output. Each function should include a description of what it does. Explain your data structures and the meanings of your variables. You do not have to document i as a loop index. The steps of your algorithm should be documented with meaningful comments. Not comments like this:
    i= 42; // Set i=42.
  4. The main should give a high level outline of what the program does. Don't call some other function that is obscure to do the work of the program. For example for assignment #1:
        while we are able to read a graph
              check the graph
              read a dominating set
              check the dominating set
        end while
  5. Do each task in a function. Functions should do ONE complete task. For example, when reading a graph, do not read the value of n in the main and the rest of the graph in a read_graph function. Do not read a dominating set in the same routine that reads a graph.
  6. Do not read strings for this type of problem and then try to parse your own input. Read one integer at a time.
    ok= scanf("%d", &n);
    returns 1 when successful. Always check the status of your scanf calls.
  7. For a recursive routine, include a variable for the level and make sure you print the level for each debugging statement.
  8. Include debugging code that will print each step your algorithm executes. For C or C++, use:
    #define DEBUG 1 // at the top
    #if DEBUG
        print some stuff
    When you set:
    #define DEBUG 0
    the debugging code is no longer compiled and included with the executable code. For bigger programs you may use debugging variables for different sections of the program. For example:
    #define DEBUG_BFS 1
    might be used when debugging a BFS routine. Then you can selectively turn off parts of the debugging messages. Please put in your debugging messages before sending me your code to get help with it. Possibly you will then be able to find your own bugs.
  9. For research code, it is really important that the program is correct. Watch and check every step on some small examples. Programs for NP-complete problems can often get an optimal solution for a problem without doing an exhaustive check. This is not uncommon especially for problems with several different optimal solutions. An exhaustive search is critical to ensure you always get a correct solution.
  10. Pay attention to the efficiency of your algorithms. For example, do not sort in O(n^3) time when you could do a MaxSort in O(n^2) time. MaxSort is very easy to program making it more likely your code is correct. It is faster than the O(n log n) algorithms such as MergeSort for small problems. Experiments I did in the past showed it to be better up to about n=40. You might use something like MergeSort which runs in O(n log n) time if your problem size is large. Or for problems such as sorting by degrees where the degree values are integer values in a narrow range, you could use a BinSort and this would run in O(n) time.
  11. In research code, correctness is paramount. It is OK to choose a simple approach over more complex algorithms and data structures since it makes it more likely the program is correct. But do not do this when there is an equally elegant faster approach than the one you chose. Sometimes a more complex approach is required to be able to complete the computation in a reasonable amount of time, but this can be decided later. A simpler implementation can be useful for verifying correctness of a more complex solution.
  12. Try to make your code elegant and simple. If you find yourself copying sections to more than one place, then consider putting that functionality in a function.
  13. Use appropriate loop structures. For example:
    while ( i < n )
        // Do some stuff that does not involve i.
    is equivalent to this for loop:
    for (i=0; i <  n; i++)
        // Do some stuff that does not involve i.
    In this case you should use the for loop not the while loop.
  14. Recursive functions are more elegant if you do not write a function that does some of the work and then calls another helper function. An example of bad code will be shown in class.
  15. Do not use global variables.