Alexander Shen
Algorithms and Programming
Problems and Solutions
Springer Science+Business Media, LLC
Alexander Shen
Institute of Problems
of Information Transmission
Moscow 103051
Russia
Library of Congress Cataloging-in-Publication Data
Shen, A. (Alexander), 1958-
Algorithms and programming : problems and solutions I Alexander
Shen.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-8176-4760-5 ISBN 978-0-8176-4761-2 (eBook)
DOI 10.1007/978-0-8176-4761-2
1. Computer algorithms. 2. Electronic digital computers-
-Programming. I. Title.
QA76.9.A43S47 1996 96-30975
005.1--dc 20 CIP
Printedon acid-free paper W
Original published 1995 in Russian Birkhäuser /1W)
© 1997 Springer Science+Business Media New York
Originally pub1ished by Birkhäuser Boston in 1997
Softcover reprint of the bardeover 1st edition 1997
Copyright is not claimed for works of U .S. Government employees.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval
system, or transmitted, in any form or by any means, electronic, mechanical, photocopy-
ing, recording, or otherwise, without prior permission of the copyright owner.
Permission to photocopy for internal or personal use of specific clients is granted by
Birkhäuser Boston for libraries and other users registered with the Copyright Clearance
Center (CCC), provided that the base fee of $6.00 per copy, plus $0.20 per page is paid
directly to CCC, 222 Rosewood Drive, Danvers, MA 01923, U.S.A. Special requests
should be addressed directly to Springer Science+Business Media, LLC.
ISBN 978-0-8176-4760-5
Typeset in Latex by the Author.
9 8 7 6 5 4 3 2 1
Contents
1 Variables, expressions, assignments 1
1.1 Problems without arrays 1
1.2 Arrays . . . . . . . 15
1.3 Inductive functions . . . 29
2 Generation of combinatorial objects 33
2.1 Sequences. 33
2.2 Permutations 34
2.3 Subsets... 35
2.4 Partitions . . 37
2.5 Gray codes and similar problems. 38
2.6 Some remarks 44
2.7 Counting . . . . . . . . 46
3 Tree traversal (backtracking) 49
3.1 Queens not attacking each other: position tree traversal 49
3.2 Backtracking in other problems . . . . . . . . . . . . 58
4 Sorting 60
4.1 Quadratic algorithms . 60
4.2 Sorting in n log n operations 61
4.3 Applications of sorting . . . 67
4.4 Lower bound for the number of comparisons. 69
4.5 Problems related to sorting . . . . . . . . . . 70
5 Finite-state algorithms in text processing 73
5.1 Compound symbols, comments, etc. 73
5.2 Numbers input . . . . . . . . . . . 74
6 Data types 79
6.1 Stacks 79
6.2 Queues 85
6.3 Sets .. 93
6.4 Priority queues 96
7 Recursion 98
7.1 Examples . . . . . . . . . . . . . . . . . . . . 98
7.2 Trees: recursive processing . . . . . . . . . . . 101
7.3 The generation of combinatorial objects; search 103
7.4 Other applications of recursion . . . . . . . . . 107
vi CONTENTS
8 Recursive and nonrecursive programs 114
8.1 Table of values (dynamic programming) 114
8.2 Stack of postponed tasks 118
8.3 Difficult cases . . . . . . . . . . . . . 121
9 Graph algorithms 124
9.1 Shortest paths . . . . . . . . . . . . . . . . . . 124
9.2 Connected components, breadth and depth search 127
10 Pattern matching 133
10.1 Simple example . . . . . 133
10.2 Repetitions in the pattern . 135
10.3 Auxiliary lemmas . . . . 136
10.4 Knuth-Morris-Pratt algorithm 137
10.5 Boyer-Moore algorithm . . . 140
10.6 Rabin-Karp algorithm . . . . 142
10.7 Automata and more complicated patterns 143
11 Set representation. Hashing 151
11.1 Hashing with open addressing 151
11.2 Hashing using lists . . . 153
12 Sets, trees, and balanced trees 158
12.1 Set representation using trees. 158
12.2 Balanced trees . . . . . . . . 165
13 Context-free grammars 176
13.1 General parsing algorithm . . . . . . . 176
13.2 Recursive-descent parsing . . . . . . . 181
13.3 Parsing algorithm for LL(l )-grammars . 191
14 Left-to-right parsing (LR) 198
14.1 LR-processes . . . 198
14.2 LR(O)-grammars .. 204
14.3 SLR(l)-grammars . 207
14.4 LR(l)-gramrnars, LALR(l)-grammars . 208
14.5 General remarks about parsing algorithms 211
Further reading 212
Preface
Somebody once said that one may prove the correctness of an algorithm, but not
of a program. One of the main goals of this book is to convince the reader that
things are not so bad.
A well-known programmer, CA.R. Hoare, said that the beauty of a program
is not an additional benefit but a criterion that separates success from failure. If,
while solving problems in this book, you come to appreciate the beauty of a well-
written program with each part in its correct place, the author's goal will have been
reached.
We have utilized the problem-solution format. Some sections are collections
of problems having a common topic, while others are devoted to one specific
algorithm (e.g., Section 14 covers LR(1)-parsing). The sections are more or less
independent, but the concluding sections are more difficult. Sections 1-7 cover
material usually included in undergradute courses while Sections 13-14 are more
appropriate for a graduate compiler course. In each section we have tried to give
problems at different levels starting with easy exercises.
Problems are usually provided with solutions, answers or hints. However,
we strongly recommend that the reader look at the solutions only after making a
good faith attempt to solve the problems independently.
Pascal is used as a programming language to write program examples; how-
ever, readers familiar with some other procedural language (C, Modula, Oberon,
etc.) will encounter no difficulties.
Most of the problems, of course, are well known. References are rare, but this
does not mean that the problem or algorithm is new. However, we hope that in
some cases the algorithm or the proof is explained better than what is found in
other sources.
This book is addressed both to the ambitious student who wants to test and
improve his/her skills and to the instructor looking for problems for his/her class.
I thank all the people I met while teaching programming (first of all, my former
students from 57th school and A.G. Kushnirenko, who was my programming
teacher) and all readers who sent me corrections for the preliminary versions of
this book (especially Yu.Y. Matijasevich).
I also thank the American Mathematical Society (former Soviet Union aid
fund), International Science Foundation, Open Society Foundation, MIT, Uni-
versity of Bordeaux, Bonn University, the Rosenbaum Foundation, INTAS, the
viii PREFACE
Russian government and the Institute of Problems of Information Transmission
for support during the writing of this book.
I thank Ann Kostant and the other nice people at Birkhauser Publishing house
for their help. Tom Scavo did a great job correcting my English (as well as several
other errors) but in no case should he be blamed for the remaining mistakes.
The Russian version of this book is freely distributed in ASCII, TEX
and PostScript formats; please contact the author (
[email protected],
[email protected],
[email protected]) for details. I'd be
grateful if bug reports will be sent to the same addresses.
To the memory ofAnna Pogossiants
Algorithms and Programming
Problems and Solutions
