Algorithms for Functional Programming
- Length: 404 pages
- Edition: 1
- Language: English
- Publisher: Springer
- Publication Date: 2018-11-07
- ISBN-10: 3662579685
- ISBN-13: 9783662579688
- Sales Rank: #3663863 (See Top 100 Books)
High Algorithms is a text geared to a junior level course in algorithms using Scheme as the programming language. Using the high- level language Scheme allows the author to make extensive use of concise yet highly readable source code or psuedocode for the implementation of all the algorithms covered in the book. This avoids a major weakness of other books currently used as texts for a course in algorithms. The resulting book covers all the traditional algorithms and introduces students to abstractions in a gradual and sensible manner. It is a light and lively presentation including prose descriptions, mathematical presntations and psuedocode for a comprehensive list of the major algorithms. The book lends itself to an accompanying lab on the topic and much supporting material both for teachers and readers or students is available at the accompanying website for the book.
Preface Acknowledgements Contents Chapter 1 Essential Notations 1.1 Simple Values Exercises 1.2 Identifiers and Expressions Exercises 1.3 Functions and Procedures 1.4 Arithmetic Functions Addition Subtraction Multiplication Division Exponentiation Procedure Summaries Exercises 1.5 Procedure Calls Exercises 1.6 lambda-Expressions Procedures of Variable Arity Building Lists Returning Multiple Values Computations Without Results Exercises 1.7 Predicates Classification Predicates Equality Predicates Equality and Types Exercises 1.8 Conditional Expressions and-Expressions and or-Expressions Exercises 1.9 Definitions Procedure Definitions Recursive Definitions Exercises 1.10 Local Bindings Local Procedures Local Recursion Expressions Exercises Chapter 2 The Tool Box 2.1 List Mapping The map Procedure Exercises 2.2 Constant Procedures Exercises 2.3 Procedure Sections The invoke Procedure Currying Exercises 2.4 Couplers Procedure Composition Parallel Application Dispatching Exercises 2.5 Adapters Selection Rearrangement Preprocessing and Postprocessing Exercises 2.6 Recursion Managers The recur Procedure Recursive Predicates Iteration Exercises 2.7 Euclid’s Algorithm Exercises 2.8 Raised Boolean Procedures Operating on Booleans and on Predicates The ^if Procedure Exercises 2.9 Natural Numbers and Recursion Mathematical Induction Managing Recursion with Natural Numbers Tallying Bounded Generalization Exercises Chapter 3 Data Structures 3.1 Modeling Exercises 3.2 The Null Value Exercises 3.3 Sum Types Enumerations Discriminated Union Recursive Type Equations Exercises 3.4 Pairs Naming Pairs Product Types Discriminated Unions Reconsidered Reimplementing Natural Numbers Exercises 3.5 Boxes Using Pairs to Model Boxes Exercises 3.6 Lists Selection Procedures Homogeneous Lists Recursive Procedures for Lists The Principle of List Induction Managing Recursion with Lists Unfolding Exercises 3.7 List Algorithms Arity Extension Filtering and Partitioning Sublists Positional Selection Extending Predicates from List Elements to Lists Transposing, Zipping, and Unzipping Aggregating Multiple Results Exercises 3.8 Sources Finite Sources Exercises 3.9 Tuples Building the Model Record Types Exercises 3.10 Trees The Principle of Tree Induction Managing Recursion with Trees Exercises 3.11 Bushes The Principle of Bush Induction Managing Recursion with Bushes Exercises 3.12 Bags Basic Bag Procedures Bag Operations Managing Recursion with Bags Exercises 3.13 Equivalence Relations Extending Equivalence Relations Exercises 3.14 Sets Managing Recursion with Sets Filtering and Partitioning Sets Additional Set Operations Union, Intersection, and Difference Exercises 3.15 Tables Updating Tables Exercises 3.16 Buffers Managing Recursion with Buffers Exercises Chapter 4 Sorting 4.1 Ordering Relations Implicitly Defined Equivalence Relations Testing Whether a List Is Ordered Searching for an Extreme Value Compound Ordering Relations Lexicographic Ordering Exercises 4.2 Sorting Algorithms Sorting by Insertion Sorting by Selection Quicksort Sorting by Merging Exercises 4.3 Binary-Search Trees Testing the Binary-Search-Tree Invariant Extracting a Value from a Binary-Search Tree Binary-Search-Tree Sort Exercises 4.4 Red-Black Trees Implementing Red-Black Trees Color Flips and Rotations Insertion Search Deletion Implementing Tables with Red-Black Trees Exercises 4.5 Heaps Folding and Unfolding Heaps Heap Sort Exercises 4.6 Order Statistics Exercises Chapter 5 Combinatorial Constructions 5.1 Cartesian Products Ordering Cartesian Products Ranking and Unranking Exercises 5.2 List Selections Sublists Sections Subsequences and Selections Exercises 5.3 Bag Selections Exercises 5.4 Permutations Ranking and Unranking Exercises 5.5 Partitions Bag Partitions Partitioning Natural Numbers Exercises Chapter 6 Graphs 6.1 Implementing Graphs Graph Construction Graphs and Relations Properties of Graphs Additional Graph Accessors Undirected Graphs Exercises 6.2 Depth-First Traversal Traversing Graphs The Depth-First Order Topological Sorting Reachable Vertices Exercises 6.3 Paths Connected Components Exercises 6.4 Breadth-First Traversal Exercises 6.5 Spanning Trees An Alternative Method Exercises 6.6 Shortest Paths The Bellman–Ford Algorithm Dijkstra’s Algorithm The Floyd–Warshall Algorithm Exercises 6.7 Flow Networks Residual Networks and Maximum Flows Exercises Chapter 7 Sublist Search 7.1 The Simple, Slow Algorithm Substring Search Exercises 7.2 The Knuth–Morris–Pratt Algorithm Substring Search Exercises 7.3 The Boyer–Moore Algorithm Exercises 7.4 The Rabin–Karp Algorithm Exercises Appendix A Recommended Reading Appendix B The (afp primitives) Library Appendix C Using the AFP Libraries Scheme Language Processors Downloading and Installing the Libraries Creating Program Files Executing Programs Limitations Index
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.