programminga general overview figure sample word puzzle because they are entirely impractical for input sizes that third algorithm can handle in reasonable amount of time second problem is to solve popular word puzzle the input consists of twodimensional array of letters and list of words the object is to find the words in the puzzle these words may be horizontalverticalor diagonal in any direction as an examplethe puzzle shown in figure contains the words thistwofatand that the word this begins at row column or ( , )and extends to ( , )two goes from ( , to ( , )fat goes from ( , to ( , )and that goes from ( , to ( , againthere are at least two straightforward algorithms that solve the problem for each word in the word listwe check each ordered triple (rowcolumnorientationfor the presence of the word this amounts to lots of nested for loops but is basically straightforward alternativelyfor each ordered quadruple (rowcolumnorientationnumber of charactersthat doesn' run off an end of the puzzlewe can test whether the word indicated is in the word list againthis amounts to lots of nested for loops it is possible to save some time if the maximum number of characters in any word is known it is relatively easy to code up either method of solution and solve many of the real-life puzzles commonly published in magazines these typically have rows columnsand or so words supposehoweverwe consider the variation where only the puzzle board is given and the word list is essentially an english dictionary both of the solutions proposed require considerable time to solve this problem and therefore might not be acceptable howeverit is possibleeven with large word listto solve the problem very quickly an important concept is thatin many problemswriting working program is not good enough if the program is to be run on large data setthen the running time becomes an issue throughout this book we will see how to estimate the running time of program for large inputs andmore importanthow to compare the running times of two programs without actually coding them we will see techniques for drastically improving the speed of program and for determining program bottlenecks these techniques will enable us to find the section of the code on which to concentrate our optimization efforts mathematics review this section lists some of the basic formulas you need to memorizeor be able to deriveand reviews basic proof techniques