- Failing to give key idea before algorithm.
No one wants to read code before being told
what the code does at a high level.
- Claiming to give the key idea, but in actuality
only stating some trivial observation that does not
lead to an algorithm.
bad: In the problem of finding the diameter of a tree,
"The key idea in the algorithm is to find 2 vertices
u and v such that the distance between them is maximal."
This is just restating the problem and so is not really
the key idea.
good: "The key idea is that if a diameter has endpoints
(u,v), then we can replace one of u,v with any deepest
node x in the tree, as found using dfs from an arbitrary root r,
and the resulting pair will also be the endpoints of a diameter."
- Stating things that are false.
This happens so much it is absurd. Before submitting work,
read each statement and make sure it is true.
bad: "Let R>r>0. If n is the largest integer such that
a regular n-gon of side length r can fit into a disk of radius
R, then we cannot fit more than n disjoint disks each of radius
r into the larger disk." This statement, though technical sounding
and therefore tempting, is false.
good: Use simple reasoning that can be backed up easily:
"The most number of disjoint disks each of radius r that we
can fit into a disk of radius R is at most the floor of the ratio
of their areas: floor(R^2/r^2)."
If you feel the need to state something complex and you are
not sure it is true, suppress the urge and look for something
simpler.
- Using several pages to describe a poor algorithm or analysis,
only to later give a superior algorithm or analysis.
Why do this?
One may feel compelled to record a history of failed ideas,
and truely this has worth sometimes, but only when there is something to
be gained by studying them.
For example, this may happen if the final algorithm is too complicated
to be understood by itself, but can be understood more easily as
an extension of another, simpler algorithm.
But before giving into the temptation of describing a sequence of algorithms,
remember that you should write as if the reader is ignorant,
but intelligent.
In particular, the grader has just seen 50 other algorithms that
are probably minor variations of yours and may not need the warm
up exercise.
Another possible reason to give multiple algorithms is to hedge
one's bet, reasoning as follows: "If one of these algorithms
does not work, the other one will be my backup and I can still
get credit."
If you really feel you must do this,
give the superior algorithm first and clearly indicate its superior status.
Of course if a second algorithm has some other advantage,
such as being an order of magnitude faster, if only
the extended Riemann hypothesis holds, feel free to divulge it.
The hard rule is to not write stuff that wastes the reader's time.
bad: "Here is a dynamic program to solve the problem
in O(2^n n!) time and here are 3 intricate lemmas that together
prove its correctness. (then later...) Here is another
approach that solves the problem in O(n) time and
1 simple paragraph that proves its correctness."
- Confusing "the" with "a" and similar pairs.
Do not assert that some object is unique unless it really is.
Often this seemly minor point will lead to very wrong logic.
For example, one might try to reason,
"The problem asks me to prove that T is the mst
and Kruskal's algorithm gives the mst, so I can prove
T is the mst by proving that Kruskal's algorithm
yields T."
But this is fallacious since Kruskal's algorithm only
gives 1 of perhaps many possible mst's and it might
be that T is some mst other than that given by Kruskal.
One could try to argue that Kruskal could yield T,
but then one is not really using Kruskal, but rather is
using the ideas in the proof of the correctness of Kruskal,
in which case the simpler thing is to just use those ideas
and don't even mention Kruskal!
Here are things that usually are unique.
- optimal values
- smallest elements of sets
- the output of a particular algorithm on a particular input
Here are things that usually are not unique.
- optimal solutions
- smallest elements of lists
- feasible solutions
- upper/lower bounds
- proofs
- algorithms that can solve the problem "optimally"
bad: "This algorithm finds the shortest path/mst/smallest element/etc."
good: "This algorithm finds a shortest path/mst/smallest element/etc."
- Assuming things that have no relevance to the problem.
bad: To find the diameter of a tree,
"Let r be a vertex of degree at least 2."
There need not be such a vertex, and even though most trees
have such a vertex (indeed there are only 3 isomorphism classes
of trees that do not), it is not relevant.
- Emphasis inversion: placing undue stress on the obvious
only to omit the truly necessary details.
- Gossiping about the algorithm:
what it is "thinking", what it would "like", what it is "trying" to do.
We only care about what it does and does not do.