0
$\begingroup$

I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary for making your own algorithms (when you need to prove algorithm correctness).

$\endgroup$
1
  • $\begingroup$ Typically you need at least some math to proof the correctnes and the running time of any algorihtm. See this introduction to algorithms book web.karabuk.edu.tr/hakankutucu/CME222/… for the basic math you need. $\endgroup$ Jun 25, 2019 at 8:53

1 Answer 1

2
$\begingroup$

There are several angles to this question.

First, most algorithms work on discrete abstractions like graphs, trees, matrices, sequences. To understand what the algorithm does, you need some acquaintance with those. They are staple of discrete mathematics. To prove the algorithm works as claimed relies on said properties, and the proof is essentially doing discrete mathematics.

Second, to use algorithms successfully, you need to know how to map your real work problem to the above abstractions, that again means knowing their particularities.

Third, you usually will want to derive performance numbers, either to verify the algorithm works within given constraints (time, space), or to compare alternative approaches and evaluate tradeoffs. Again, a job for discrete mathematics.

Sure, you certainly can do a lot without going deeply into discrete mathematics (at least not openly), but it is a valuable toolbox.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.