Algorithms and programming : problems and solutions

Description

Cover Springer Undergraduate Texts in Mathematics and Technology Algorithms and Programming: Problems and Solutions, Second Edition ISBN 9781441917478 Contents Preface to the second edition 1 Variables, expressions, assignments 1.1 Problems without arrays 1.2 Arrays 1.3 Inductive functions 2 Generation of combinatorial objects 2.1 Sequences 2.2 Permutations 2.3 Subsets 2.4 Partitions 2.5 Gray codes and similar problems 2.6 Some remarks 2.7 Counting 3 Tree traversal (backtracking) 3.1 Queens not attacking each other: position tree 3.2 Tree traversal 3.3 Queens: position tree implementation 3.4 Backtracking in other problems 4 Sorting 4.1 Quadratic algorithms 4.2 Sorting in nlogn operations 4.3 Applications of sorting 4.4 Lower bound for the number of comparisons 4.5 Problems related to sorting 5 Finite-state algorithms in text processing 5.1 Compound symbols, comments, etc. 5.2 Numbers input 6 Data types 6.1 Stacks 6.2 Queues 6.3 Sets 6.4 Priority queues 7 Recursion 7.1 Examples 7.2 Trees: recursive processing 7.3 The generation of combinatorial objects; search 7.4 Other applications of recursion 8 Recursive and non-recursive programs 8.1 Table of values (dynamic programming) 8.2 Stack of postponed tasks 8.3 Difficult cases 9 Graph algorithms 9.1 Shortest paths 9.2 Connected components, breadth- and depth-first search 10 Pattern matching 10.1 Simple example 10.2 Repetitions in the pattern 10.3 Auxiliary lemmas 10.4 Knuth–Morris–Pratt algorithm 10.5 Boyer–Moore algorithm 10.6 Rabin–Karp algorithm 10.7 Automata and more complicated patterns 10.8 Suffix trees 11 Games analysis 11.1 Game examples 11.2 Game cost 11.3 Computing the game cost by backtracking 11.4 Alpha-beta pruning 11.5 A retrospective analysis 12 Optimal coding 12.1 Codes 12.2 The Kraft–McMillan inequality 12.3 Huffman code 12.4 Shannon–Fano code 13 Set representation. Hashing 13.1 Hashing with open addressing 13.2 Hashing using lists 14 Sets, trees, and balanced trees 14.1 Set representation using trees 14.2 Balanced trees 15 Context-free grammars 15.1 General parsing algorithm 15.2 Recursive-descent parsing 15.3 Parsing algorithm for LL(1)-grammars 16 Left-to-right parsing (LR) 16.1 LR-processes 16.2 LR(0)-grammars 16.3 SLR(1)-grammars 16.4 LR(1)-grammars, LALR(1)-grammars 16.5 General remarks about parsing algorithms Further reading Appendix: C and Pascal examples Index