New answers tagged

2

I see several advantages of mastering the proof of correctness and complexity of an algorithm. I list them below and illustrate with a concrete example. I tried to stay in the domain of classical textbook algorithms. Understanding why the algorithm works Certainly the most obvious reason of having proofs. Many algorithms exploit some structure in the ...


2

A practical answer: In my career I encountered a few scenarios, some with my direct involvement, where I had to prove that my algorithm performs just as good as the currently best known possible. There are many examples where such knowledge can have a direct effect on one's career... In my experience, making a good claim at a design review meeting or to your ...


4

Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "in parallel." The task is this: Input: An undirected graph. Task: Find a subgraph with maximum edge-connectivity. Note: What makes the task non-trivial is ...


Top 50 recent answers are included