Used and New from Other Sellers
Used and New from Other Sellers
from $54.64
Usually ships in 12 business days
(Save 30%)
Other sellers (Paperback)

All (6)
from
$54.64

New (2)
from
$125.00

Used (4)
from
$54.64
Note: Marketplace items are not eligible for any BN.com coupons and promotions
$125.00
Seller since 2014
Brand new.
Ships from: acton, MA
Usually ships in 12 business days
 •Standard, 48 States
 •Standard (AK, HI)
$125.00
Seller since 2014
Brand new.
Ships from: acton, MA
Usually ships in 12 business days
 •Standard, 48 States
 •Standard (AK, HI)
More About This Textbook
Overview
The authors challenge more traditional methods of teaching algorithms by using a functional programming context, with Haskell as the implementation language. This leads to smaller, clearer and more elegant programs which enable the programmer to understand the algorithm itself more quickly and to use that understanding to explore alternative solutions. Placing the emphasis on program development rather than the mathematical properties of algorithms, the book uses a succession of practical programming examples to develop in the reader problemsolving skills which can be easily transferred to other language paradigms. Key features of this innovative text include:
Editorial Reviews
Booknews
Placing the emphasis on program development rather than on the mathematical properties of algorithms, Rabhi (computer science, U. of Hull, UK) and Lapalme (computer science, U. of Montreal, Canada) use a number of practical programming examples to develop problemsolving skills which can be transferred from Haskell (which this book uses) to other programming languages. Subjects include functional programming in Haskell, concrete and abstract data types, sorting, graph algorithms, and more advanced topics such as process networks, and parallel algorithms. Each chapter includes exercises for review. Annotation c. Book News, Inc., Portland, OR (booknews.com)Product Details
Related Subjects
Read an Excerpt
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 divideandconquer and dynamic programming by means of higherorder functions. New concepts such as process networks and parallel algorithms can also be introduced in a nonconventional way. Due to this extra material, topics such as lower bound proofs and NP 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 emergein 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 nonessential 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:
...
Table of Contents
Functional Languages.
Bibliographical Notes.
2. Functional Programming in Haskell.
Equations and Functions.
Basic Types and Constructed Types.
Lists.
Higherorder Functional Programming Techniques.
Algebraic Types and Polymorphism.
Arrays.
Type Classes and Class Methods.
Exercises.
Bibliographical Notes.
3. The Efficiency of Functional Programs.
Analyzing the Efficiency of Programs.
Program Transformation.
Conclusion.
Exercises.
Bibliographical Notes.
4. Concrete Data Types.
Trees.
Arrays.
Exercises.
Bibliographical Notes.
5. Abstract Data Types.
Stacks.
Queues.
Priority Queues.
Sets.
Tables.
Binary Search Trees.
Heaps.
AVL trees.
Exercises.
Bibliographical Notes.
6. Sorting.
Comparisonbased Sorting.
Basic Sorting Algorithms.
Treebased Sorting.
Efficiency of Comparisonbased Algorithms.
Representationbased Sorting.
Exercises.
Bibliographical Notes.
7. Graph Algorithms.
The Graph ADT.
Depthfirst and BreadthfirstSearch.
Topological Sort.
Minimum Spanning Tree.
Depthfirst Search Trees and Forests.
Conclusion.
Exercises.
Bibliographical Notes.
8. Topdown Design Techniques.
Backtracking Search.
Priorityfirst Search.
Greedy Algorithms.
Exercises.
Bibliographical Notes.
9. Dynamic Programming.
The Dynamic Programming Higherorder Function.
Chained Matrix Multiplications.
Optimal Binary Search Trees.
Allpairs Shortest Path.
The Travelling Salesperson.
Conclusion.
Exercises.
Bibliographical Notes.
10. Advanced topics.
Monads.
Parallel Algorithms.
Bibliographical Notes.
Bibliography.
B: Mathematical Background.
Notation.
Logarithms.
Summation Formulas.
Solving Recurrence Equations.
Index.
Preface
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 divideandconquer and dynamic programming by means of higherorder functions. New concepts such as process networks and parallel algorithms can also be introduced in a nonconventional way. Due to this extra material, topics such as lower bound proofs and NP 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 thenear 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 nonessential 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/Algorithmsfunctional.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 depthfirst search.
The last part addresses some highlevel methodologies used in the design of algorithms. Chapter 8 describes topdown design techniques such as divideandconquer and backtracking search. Chapter 9 explains some inefficiencies in topdown algorithms and how they can be solved by adopting a bottomup 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 StDenis 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)
Introduction
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 divideandconquer and dynamic programming by means of higherorder functions. New concepts such as process networks and parallel algorithms can also be introduced in a nonconventional way. Due to this extra material, topics such as lower bound proofs and NP 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 thenear 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 nonessential 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.
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 depthfirst search.
The last part addresses some highlevel methodologies used in the design of algorithms. Chapter 8 describes topdown design techniques such as divideandconquer and backtracking search. Chapter 9 explains some inefficiencies in topdown algorithms and how they can be solved by adopting a bottomup 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 StDenis 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.