Mitch's Technical Blog

Induction, Algorithms and Data Structures

July 29, 2018
notes, toots
permalink

As I bounce around exploring details, it is important to step back occasionally and survey the whole. Some quotes to help as reminders.

Most professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science.

- Steven S. Skiena, The Algorithm Design Manual 2nd Ed, Preface

...induction is a style of argument we use to convince ourselves and others that a mathematical statement is always true.

- Oscar Levin, Discrete Mathematics, An Open Introduction (Fall 2015), p. 111

Induction is ... the single most useful tool for reasoning about, developing, and analyzing algorithms.

- Jeff Erickson, [Appendix I: Proof by Induction Fa' 13](http://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf)

...recursion is mathematical induction. I've heard it said that a computer scientist is a mathematician who only knows how to prove things by induction. This is partially true because computer scientists are lousy at proving things, but primarily because so many of the algorithms we study are either recursive or incremental.

- Steven S. Skiena, The Algorithm Design Manual 2nd Ed, p. 15

The study of algorithms and data structures is one of the foundations of computer science, a rich field of elegant techniques and sophisticated mathematical analyses...Every program depends on algorithms and data structures, but few programs depend on the invention of brand new ones. Even within an intricate program like a compiler or a web browser, most of the data structures are arrays, lists, trees, and hash tables. When a program needs something more elaborate, it will likely be based on these simpler ones. Accordingly, for most programmers, the task is to know what appropriate algorithms and data structures are available and to understand how to choose among alternatives.

- Brian W. Kernighan and Rob Pike, The Practice of Programming, p. 29

Contact: hello at escapefromsql.net