Good programming practice
This is a non-exhaustive guide to writing programs with good style:
Use meaningful variable names.
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.
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
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.
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.
For a recursive routine, include a variable for the level
and make sure you print the level for each debugging statement.
Include debugging code that will print each step your algorithm executes.
For C or C++, use:
#define DEBUG 1 // at the top
print some stuff
When you set:
#define DEBUG 0
the debugging code is no longer compiled and included with the
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.
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.
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
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.
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.
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.
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.
Do not use global variables.