When I write a paper comparing my algorithm to someone else's, how should I make sure that the results are not skewed because I implemented the other algorithm poorly? Is it acceptable to write that the other algorithm was implemented to my best knowledge?
It is usually sufficient to say that you tried to optimize both your algorithm and the baseline(s) as much as you could (provided you actually did so).
Before writing your own implementations though, you should first check that the authors of the baseline(s) haven't published their source code. You may even write to them. I've heard all kinds of replies to such requests: from people sending me the code within minutes, to people telling me their code was lost in an old laptop long ago (the paper was 2 years old...). If they don't have the code, you can ask them how they would/did implement their algorithm.
It would be good practice and very beneficial for the community if you then publish both the code for your algorithm AND (if you implemented them) the code for the baselines.