# Re: Math/CompSci Interview Question - Thoughts?

*From*: Patricia Shanahan <pats@xxxxxxx>*Date*: Mon, 23 Nov 2009 11:31:15 -0800

Paul E. Black wrote:

....

I took an algorithms or analysis of algorithms class. We solved a ton....

of problems like "design an O(n^2) algorithm for ..." (or n log n or

whatever). After a semester of this, we were pretty good at coming up

with stuff. Note: just "knowing" the complexity of a solution went a

long way as a hint to how it might be solved.

Your algorithms professor was kinder than mine. He set problems of the

form "Write an algorithm for ..." with standing instructions that we had

to state a claimed time complexity, prove correctness, and prove the

claimed time complexity. Given correct proofs, he gave better grades for

lower complexity algorithms.

That was more realistic, because someone starting on designing an

algorithm does not usually know in advance what complexity is

achievable. However, it had the unpleasant consequence that I could

rarely be sure I had finished my homework, even after I had written an

algorithm and the required proofs.

Patricia

.

- Prev by Date:
**Re: Math/CompSci Interview Question - Thoughts?** - Next by Date:
**Re: Math/CompSci Interview Question - Thoughts?** - Previous by thread:
**Re: Math/CompSci Interview Question - Thoughts?** - Next by thread:
**Re: Math/CompSci Interview Question - Thoughts?** - Index(es):