Re: Math/CompSci Interview Question - Thoughts?

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.


Relevant Pages

  • Re: FUD about CGD and GBDE
    ... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
  • Re: Hooray: the Church of Scotland shows the way
    ... If you are simply pointing out the limitations of algorithmic machines then I agree completely. ... any Turing machine could print out the solution to a non-computable problem if that solution were part of the machine's algorithm. ... Given the complexity of the universe it doesn't seem unlikely that the solutions to all manner of non-computable problems have been physically realised in some form and lie there waiting for us to latch on to them somehow. ... Whilst it's true that fundamental physics are essentially algorithmic in nature, ...
  • Re: ALFREDO RIZZI - 21-st Century Breakthrough - AKS algorithm (primality test) is O log
    ... You have to read the number into memory! ... a paper where a present a new algorithm ... Input time does not matter. ... May I suggest that you read a book on complexity analysis? ...
  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ... cannot be algorithmically random. ...
  • Re: Intro to Programming w/ Machine Language
    ... > Based upon your previous posts, I found this pretty surprising. ... > If n is sufficiently large, the Ocomplexity obviously matters. ... where's the Oor Oalgorithm that's ... people use in the good old "assembly vs. HLL" religous wars. ...