Description: Purpose/goals This book is primarily an introduction to the design of algorithms for problem solving. Its prominent feature is to use a functional language as an implementation language. Because of the high level of abstraction provided, functional programs tend to be shorter, clearer and faster to develop than their imperative counterparts. This contributes to a better understanding of the algorithm being implemented and makes it possible to explore alternative solutions more rapidly. Although we believe that this is true for a wide range of algorithms, the book also discusses the limitations of functional style in dealing with certain problems. This book is not about a particular functional language. The material is arranged in the same way as in a classic algorithms book: it is a succession of chapters on ''traditional'' topics such as sorting and searching algorithms. In addition, the choice of a functional language permits the introduction of algorithm design strategies such as divide-and-conquer and dynamic programming by means of higher-order functions. New concepts such as process networks and parallel algorithms can also be introduced in a non-conventional way. Due to this extra material, topics such as lower bound proofs and N-P completeness theory are not covered. The emphasis of the book is on intuitive and pragmatic program development techniques. This is only a small step forward, as we believe that functional programming provides a link between the study of algorithms and the study of correctness proofs and systematic derivation from formal specifications. We are hoping that more publications covering this area will emerge in the near future. Another aim of this book is to provide a useful reference of functional programs related to a variety of problems. Programmers will be able to choose (or adapt) a functional program that is relevant to their problem as they already do with other languages such as Fortran, Pascal or C. We are also hoping that this book will contribute towards making functional languages more viable as a programming tool. Approach Each chapter addresses a specific problem area by describing the associated algorithms. Each algorithm is specified using a trivial (but sometimes inefficient) functional program. In some cases, a more efficient (and often more obscure) version can be derived. Sections containing non-essential material are marked with a (t) symbol and can be safely skipped. Exercises are included at the end of each chapter. For an excellent companion book which provides further details about most of the algorithms presented in this book, we recommend Brassard and Bratley''s Fundamentals of Algorithmics 19. Another feature of the book is the use of Haskell, a newly proposed functional language standard, named after the logician Haskell B. Curry. Haskell is purely functional, uses lazy evaluation and incorporates most of the features of modern functional languages. It is free to use, has numerous implementations on almost all platforms, and is available from sites worldwide. Appendix A provides some information about these implementations. The Haskell source code of the programs given in this book and the answers to selected exercises are available from the following WWW site: http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html Target audience This book is primarily targeted at undergraduate students in computer science studying algorithms. Within a traditional course that uses imperative languages, only a fraction of the known algorithms can be completely implemented. By adopting a functional language, more prototypes can be developed; this contributes to a better understanding of the techniques involved, since implementing a particular algorithm requires a complete understanding of all the details related to this algorithm. This approach also allows experimentation with certain types of algorithms (such as process networks) which would be too difficult to program in an imperative language. The prerequisites are: Students must have had some programming experience in any language, preferably a functional language. Some notion of how functional languages are implemented is also desirable. A minimum mathematical background (mostly summations) is required for the analysis of algorithms although these sections can safely be omitted by those who are not interested in complexity or efficiency analysis. The book can also be used to support an advanced functional programming course in a variety of ways: (1) by presenting examples of implementing and using data structures such as queues, trees and graphs, (2) by introducing program design techniques, (3) by increasing the awareness concerning time and space efficiency, and (4) by presenting some advanced topics such as process networks and parallel algorithms. As mentioned previously, the book is also a useful source of functional programs which can be regarded as executable specifications of the algorithms concerned. Overview The book is roughly divided into three parts. The first part contains all the background information needed before embarking on the main body of the book. Chapter I presents the basic concept of an algorithm and highlights key features of functional languages with a brief history of their evolution and role in recent years. Chapter 2 contains an introduction to the functional language Haskell. Chapter 3 is a review of evaluation mechanisms such as strict and lazy evaluation, with an overview of the graph reduction model. It defines what is meant by ''efficiency'' and presents some simple transformations that increase the efficiency of programs. Chapter 4 examines simple concrete data structures (lists, trees, and arrays) and the efficiency of the operations used to manipulate these data structures. The second part of the book considers some basic algorithms for a variety of purposes. Chapter 5 examines abstract data types (ADTs), using them to represent for example priority queues and binary search trees. Chapter 6 presents sorting techniques such as quicksort and heapsort and Chapter 7 discusses graphs and associated algorithms such as computing the minimum spanning tree and depth-first search. The last part addresses some high-level methodologies used in the design of algorithms. Chapter 8 describes top-down design techniques such as divide-and-conquer and backtracking search. Chapter 9 explains some inefficiencies in top-down algorithms and how they can be solved by adopting a bottom-up approach, namely dynamic programming. Finally, Chapter 10 examines some advanced topics such as process networks, monads, and parallel algorithms through some extensions to the Haskell language. Acknowledgments The idea of the book came while the first author was a visiting lecturer at Allegheny College so our special thanks are due to Mike Holcombe, Bob Cupper and Ben Haytock for making it possible. We would like to thank Aster Thien, Marina Mahmood, Chris Meen, Len Bottaci and Rob Turner for their contribution to some of the programs presented in this book. We also thank Guy St-Denis for his many constructive suggestions on a preliminary version of this book, our editor Michael Strang for his continued support, and the anonymous reviewers who found many inaccuracies and gave constructive ideas on presentation. Finally, we are grateful to the (enthusiastic!) Haskell community for their efforts in designing a standard functional language and for providing the scientific community with free implementations. Fethi Rabhi (F.A.Rabhi@dcs. hull. ac. uk) Guy Lapalme (lapalme@iro. umontreal. ca) 0201596040P04062001

Please Wait