(Ebook) An Introduction to the Analysis of Algorithms by Michael Soltys ISBN 9789813235908, 9789813235915, 981323590X, 9813235918

(Ebook) An Introduction to the Analysis of Algorithms by Michael Soltys ISBN 9789813235908, 9789813235915, 981323590X, 9813235918

If he had only learnt a littleless, how infinitely better hemight have taught much more!Charles Dickens [Dickens(1854)], pg. 7This book is a short introduction to the analysis of algorithms, from the point of view of proving algorithm correctness. The quote above refers to Mr. M‘Choakumchild, a caricature of a teacher in Charles Dickens’ HardTimes, who chokes the minds of his pupils with too much information. We will avoid M‘Choakumchild’s mistake, and make a virtue out of brevity.Our theme is the following: how do we argue mathematically, without a burden of excessive formalism, that a given algorithm does what it is supposed to do?And why is this important?In the words of C.A.R.Hoare:As far as the fundamental science is concerned, we still certainlydo not know how to prove programs correct. We need a lot ofsteady progress in this area, which one can foresee, and a lot ofbreakthroughs where people suddenly find there’s a simple wayto do something that everybody hitherto has thought to be fartoo difficult1.Software engineers know many examples of things going terribly wrong because of program errors.