This easy-to-read 2010 book demonstrates how a simple geometric idea reveals fascinating connections and results in number theory, the mathematics of polyhedra, combinatorial geometry, and group theory. Using a systematic paper-folding procedure it is possible to construct a regular polygon with any number of sides. This remarkable algorithm has led to interesting proofs of certain results in number theory, has been used to answer combinatorial questions involving partitions of space, and has enabled the authors to obtain the formula for the volume of a regular tetrahedron in around three steps, using nothing more complicated than basic arithmetic and the most elementary plane geometry. All of these ideas, and more, reveal the beauty of mathematics and the interconnectedness of its various branches. Detailed instructions, including clear illustrations, enable the reader to gain hands-on experience constructing these models and to discover for themselves the patterns and relationships they unearth.

The Wiley-Interscience Paperback Series consists of selected books that have been made more accessible to consumers in an effort to increase global appeal and general circulation. With these new unabridged softcover volumes, Wiley hopes to extend the lives of these works by making them available to future generations of statisticians, mathematicians, and scientists. "This text is unique in bringing together so many results hitherto found only in part in other texts and papers...The text is fairly self-contained, inclusive of some basic mathematical results needed, and provides a rich diet of examples, applications, and exercises. The bibliographical material at the end of each chapter is excellent, not only from a historical perspective, but because it is valuable for researchers in acquiring a good perspective of the MDP research potential." -Zentralblatt fur Mathematik "...it is of great value to advanced-level students, researchers, and professional practitioners of this field to have now a complete volume (with more than 600 pages) devoted to this topic...Markov Decision Processes: Discrete Stochastic Dynamic Programming represents an up-to-date, unified, and rigorous treatment of theoretical and computational aspects of discrete-time Markov decision processes. " -Journal of the American Statistical Association

In the readition of the bestselling Chaos and A Brief History of Time, here is a science book with mainstream appeal. Proponents of artificial intelligence maintain that eventually a computer will be able to do everything a human mind can do, but Oxford University Professor of Mathematics Roger Penrose explains his view that there are facets of human thinking that can never be emulated by a machine. Drawings throughout.
Some love it, some hate it, but The Emperor's New Mind, physicist Roger Penrose's 1989 treatise attacking the foundations of strong artificial intelligence, is crucial for anyone interested in the history of thinking about AI and consciousness. Part survey of modern physics, part exploration of the philosophy of mind, the book is not for casual readers--though it's not overly technical, it rarely pauses to let the reader catch a breath. The overview of relativity and quantum theory, written by a master, is priceless and uncontroversial. The exploration of consciousness and AI, though, is generally considered as resting on shakier ground.
Penrose claims that there is an intimate, perhaps unknowable relation between quantum effects and our thinking, and ultimately derives his anti-AI stance from his proposition that some, if not all, of our thinking is non-algorithmic. Of course, these days we believe that there are other avenues to AI than traditional algorithmic programming; while he has been accused of setting up straw robots to knock down, this accusation is unfair. Little was then known about the power of neural networks and behavior-based robotics to simulate (and, some would say, produce) intelligent problem-solving behavior. Whether these tools will lead to strong AI is ultimately a question of belief, not proof, and The Emperor's New Mind offers powerful arguments useful to believer and nonbeliever alike. --Rob Lightner

Elements of Programming provides a different understanding of programming than is presented elsewhere. Its major premise is that practical programming, like other areas of science and engineering, must be based on a solid mathematical foundation. The book shows that algorithms implemented in a real programming language, such as C++, can operate in the most general mathematical setting. For example, the fast exponentiation algorithm is defined to work with any associative operation. Using abstract algorithms leads to efficient, reliable, secure, and economical software.
This is not an easy book. Nor is it a compilation of tips and tricks for incremental improvements in your programming skills. The book’s value is more fundamental and, ultimately, more critical for insight into programming. To benefit fully, you will need to work through it from beginning to end, reading the code, proving the lemmas, doing the exercises. When finished, you will see how the application of the deductive method to your programs assures that your system’s software components will work together and behave as they must.
Following key definitions, the book describes a number of algorithms and requirements for types on which they are defined that exemplify its abstract mathematical approach. The code for these descriptions—also available on the Web—is written in a small subset of C++ meant to be accessible to any experienced programmer. This subset is defined in a special language appendix coauthored by Sean Parent and Bjarne Stroustrup.
Whether you are a software developer, or any other professional for whom programming is an important activity, or a committed student, you will come to understand what the book’s experienced authors have been teaching and demonstrating for years—that mathematics is good for programming, that theory is good for practice.

A collection useful programming advice the author has collected over the years; small algorithms that make the programmer's task easier. * At long last, proven short-cuts to mastering difficult aspects of computer programming * Learn to program at a more advanced level than is generally taught in schools and training courses, and much more advanced than can be learned through individual study/experience. * An instant cult classic for programmers! Computer programmers are often referred to as hackers -- solitary problem solvers engrossed in a world of code as they seek elegant solutions to building better software. While many view these unique individuals as "madmen," the truth is that much of the computer programmer's job involves a healthy mix of arithmetic and logic. In Hacker's Delight, veteran programmer Hank Warren shares the collected wisdom -- namely tips and tricks -- from his considerable experience in the world of application development. The resulting work is an irresistible collection that will help even the most seasoned programmers better their craft. Henry S. Warren Jr. has had a 40-year career with IBM, spanning the computer field from the IBM 704 to PowerPC. He has worked on various military command and control systems, and on the SETL project under Jack Schwartz at NYU. Since 1973 he has been in IBM's Research Division at Yorktown Heights, New York. Here he has done compiler and computer architecture work on the 801 computer and its several variants through PowerPC. Presently he is working on the Blue Gene petaflop computer project. He received his Ph.D. in Computer Science from the Courant Institute at New York University in 1980.

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists - the authors themselves rely heavily on it! - but for serious users of mathematics in virtually every discipline. Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories.Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study. Major topics include: *Sums *Recurrences *Integer functions *Elementary number theory *Binomial coefficients *Generating functions *Discrete probability *Asymptotic methods This second edition includes important new material about mechanical summation. In response to the widespread use of the first edition as a reference book, the bibliography and index have also been expanded, and additional nontrivial improvements can be found on almost every page. Readers will appreciate the informal style of Concrete Mathematics. Particularly enjoyable are the marginal graffiti contributed by students who have taken courses based on this material. The authors want to convey not only the importance of the techniques presented, but some of the fun in learning and using them. 0201558025B04062001

Essential Information about Algorithms and Data Structures A Classic Reference The latest version of Sedgewick,s best-selling series, reflecting an indispensable body of knowledge developed over the past several decades. Broad Coverage Full treatment of data structures and algorithms for sorting, searching, graph processing, and string processing, including fifty algorithms every programmer should know. See

Assuming only an elementary background in discrete mathematics, this textbook is an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It includes random sampling, expectations, Markov's and Chevyshev's inequalities, Chernoff bounds, balls and bins models, the probabilistic method, Markov chains, MCMC, martingales, entropy, and other topics. The book is designed to accompany a one- or two-semester course for graduate students in computer science and applied mathematics.

This third edition of the classic textbook in Optimization has been fully revised and updated. It comprehensively covers modern theoretical insights in this crucial computing area, and will be required reading for analysts and operations researchers in a variety of fields. The book connects the purely analytical character of an optimization problem, and the behavior of algorithms used to solve it. Now, the third edition has been completely updated with recent Optimization Methods. The book also has a new co-author, Yinyu Ye of California's Stanford University, who has written lots of extra material including some on Interior Point Methods.

This new and updated edition deals with all aspects of Monte Carlo simulation of complex physical systems encountered in condensed-matter physics, statistical mechanics, and related fields. After briefly recalling essential background in statistical mechanics and probability theory, it gives a succinct overview of simple sampling methods. The concepts behind the simulation algorithms are explained comprehensively, as are the techniques for efficient evaluation of system configurations generated by simulation. It contains many applications, examples, and exercises to help the reader and provides many new references to more specialized literature. This edition includes a brief overview of other methods of computer simulation and an outlook for the use of Monte Carlo simulations in disciplines beyond physics. This is an excellent guide for graduate students and researchers who use computer simulations in their research. It can be used as a textbook for graduate courses on computer simulations in physics and related disciplines.

This book emphasizes the creative aspects of algorithm design by examining steps used in the process of algorithms development. The heart of this creative process lies in an analogy between proving mathematical theorems by induction and designing combinatorial algorithms. The book contains hundreds of problems and examples. It is designed to enhance the reader's problem-solving abilities and understanding of the principles behind algorithm design.

This book offers robust solutions for everyday programming tasks, providing all the necessary information to
understand and use common programming techniques. It includes implementations and real-world examples of
each data structure in the text and full source code on the accompanying website
(http://examples.oreilly.com/masteralgoc/). Intended for anyone with a basic understanding of the C language.
Preface
When I first thought about writing this book, I immediately thought of O'Reilly & Associates to publish it. They were the first publisher
I contacted, and the one I most wanted to work with because of their tradition of books covering "just the facts." This approach is not
what one normally thinks of in connection with books on data structures and algorithms. When one studies data structures and
algorithms, normally there is a fair amount of time spent on proving their correctness rigorously. Consequently, many books on this
subject have an academic feel about them, and real details such as implementation and application are left to be resolved
elsewhere. This book covers how and why certain data structures and algorithms work, real applications that use them (including
many examples), and their implementation. Mathematical rigor appears only to the extent necessary in explanations.
Naturally, I was very happy that O'Reilly & Associates saw value in a book that covered this aspect of the subject. This preface
contains some of the reasons I think you will find this book valuable as well. It also covers certain aspects of the code in the book,
defines a few conventions, and gratefully acknowledges the people who played a part in the book's creation.
Bookmarks
Main Page
Table of content
Copyright
Preface
Organization
Key Features
About the Code
Conventions
How to Contact Us
Acknowledgments
Part I: Preliminaries
Chapter 1. Introduction
1.1 An Introduction to Data Structures
1.2 An Introduction to Algorithms
1.3 A Bit About Software Engineering
1.4 How to Use This Book
Chapter 2. Pointer Manipulation
2.1 Pointer Fundamentals
2.2 Storage Allocation
2.3 Aggregates and Pointer Arithmetic
2.4 Pointers as Parameters to Functions
2.5 Generic Pointers and Casts
2.6 Function Pointers
2.7 Questions and Answers
2.8 Related Topics
Chapter 3. Recursion
3.1 Basic Recursion
3.2 Tail Recursion
3.3 Questions and Answers
3.4 Related Topics
Chapter 4. Analysis of Algorithms
4.1 Worst-Case Analysis
4.2 O-Notation
4.3 Computational Complexity
4.4 Analysis Example: Insertion Sort
4.5 Questions and Answers
4.6 Related Topics
Part II: Data Structures
Chapter 5. Linked Lists
5.1 Description of Linked Lists
5.2 Interface for Linked Lists
5.3 Implementation and Analysis of Linked Lists
5.4 Linked List Example: Frame Management
5.5 Description of Doubly-Linked Lists
5.6 Interface for Doubly-Linked Lists
5.7 Implementation and Analysis of Doubly Linked Lists
5.8 Description of Circular Lists
5.9 Interface for Circular Lists
5.10 Implementation and Analysis of Circular Lists
5.11 Circular List Example: Second-Chance Page Replacement
5.12 Questions and Answers
5.13 Related Topics
Chapter 6. Stacks and Queues
6.1 Description of Stacks
6.2 Interface for Stacks
6.3 Implementation and Analysis of Stacks
6.4 Description of Queues
6.5 Interface for Queues
6.6 Implementation and Analysis of Queues
6.7 Queue Example: Event Handling
6.8 Questions and Answers
6.9 Related Topics
Chapter 7. Sets
7.1 Description of Sets
7.2 Interface for Sets
7.3 Implementation and Analysis of Sets
7.4 Set Example: Set Covering
7.5 Questions and Answers
7.6 Related Topics
Chapter 8. Hash Tables
8.1 Description of Chained Hash Tables
8.2 Interface for Chained Hash Tables
8.3 Implementation and Analysis of Chained Hash Tables
8.4 Chained Hash Table Example: Symbol Tables
8.5 Description of Open-Addressed Hash Tables
8.6 Interface for Open-Addressed Hash Tables
8.7 Implementation and Analysisof Open Addressed Hash Tables
8.8 Questions and Answers
8.9 Related Topics
Chapter 9. Trees
9.1 Description of Binary Trees
9.2 Interface for Binary Trees
9.3 Implementation and Analysis of Binary Trees
9.4 Binary Tree Example: Expression Processing
9.5 Description of Binary Search Trees
9.6 Interface for Binary Search Trees
9.7 Implementation and Analysis of Binary Search Trees
9.8 Questions and Answers
9.9 Related Topics
Chapter 10. Heaps and Priority Queues
10.1 Description of Heaps
10.2 Interface for Heaps
10.3 Implementation and Analysis of Heaps
10.4 Description of Priority Queues
10.5 Interface for Priority Queues
10.6 Implementation and Analysis of Priority Queues
10.7 Priority Queue Example: Parcel Sorting
10.8 Questions and Answers
10.9 Related Topics
Chapter 11. Graphs
11.1 Description of Graphs
11.2 Interface for Graphs
11.3 Implementation and Analysis of Graphs
11.4 Graph Example: Counting Network Hops
11.5 Graph Example: Topological Sorting
11.6 Questions and Answers
11.7 Related Topics
Part III: Algorithms
Chapter 12. Sorting and Searching
12.1 Description of Insertion Sort
12.2 Interface for Insertion Sort
12.3 Implementation and Analysis of Insertion Sort
12.4 Description of Quicksort
12.5 Interface for Quicksort
12.6 Implementation and Analysis of Quicksort
12.7 Quicksort Example: Directory Listings
12.8 Description of Merge Sort
12.9 Interface for Merge Sort
12.10 Implementation and Analysis of Merge Sort
12.11 Description of Counting Sort
12.12 Interface for Counting Sort
12.13 Implementation and Analysis of Counting Sort
12.14 Description of Radix Sort
12.15 Interface for Radix Sort
12.16 Implementation and Analysis of Radix Sort
12.17 Description of Binary Search
12.18 Interface for Binary Search
12.19 Implementation and Analysis of Binary Search
12.20 Binary Search Example: Spell Checking
12.21 Questions and Answers
12.22 Related Topics
Chapter 13. Numerical Methods
13.1 Description of Polynomial Interpolation
13.2 Interface for Polynomial Interpolation
13.3 Implementation and Analysis of Polynomial Interpolation
13.4 Description of Least-Squares Estimation
13.5 Interface for Least-Squares Estimation
13.6 Implementation and Analysis of Least-Squares Estimation
13.7 Description of the Solution of Equations
13.8 Interface for the Solution of Equations
13.9 Implementation and Analysis of the Solution of Equations
13.10 Questions and Answers
13.11 Related Topics
Chapter 14. Data Compression
14.1 Description of Bit Operations
14.2 Interface for Bit Operations
14.3 Implementation and Analysis of Bit Operations
14.4 Description of Huffman Coding
14.5 Interface for Huffman Coding
14.6 Implementation and Analysis of Huffman Coding
14.7 Huffman Coding Example: Optimized Networking
14.8 Description of LZ77
14.9 Interface for LZ77
14.10 Implementation and Analysis of LZ77
14.11 Questions and Answers
14.12 Related Topics
Chapter 15. Data Encryption
15.1 Description of DES
15.2 Interface for DES
15.3 Implementation and Analysis of DES
15.4 DES Example: Block Cipher Modes
15.5 Description of RSA
15.6 Interface for RSA
15.7 Implementation and Analysis of RSA
15.8 Questions and Answers
15.9 Related Topics
Chapter 16. Graph Algorithms
16.1 Description of Minimum Spanning Trees
16.2 Interface for Minimum Spanning Trees
16.3 Implementation and Analysis of Minimum Spanning Trees
16.4 Description of Shortest Paths
16.5 Interface for Shortest Paths
16.6 Implementation and Analysis of Shortest Paths
16.7 Shortest Paths Example: Routing Tables
16.8 Description of the Traveling-Salesman Problem
16.9 Interface for the Traveling-Salesman Problem
16.10 Implementation and Analysis of the Traveling-Salesman Problem
16.11 Questions and Answers
16.12 Related Topics
Chapter 17. Geometric Algorithms
17.1 Description of Testing Whether Line Segments Intersect
17.2 Interface for Testing Whether Line Segments Intersect
17.3 Implementation and Analysis of Testing Whether Line Segments Intersect
17.4 Description of Convex Hulls
17.5 Interface for Convex Hulls
17.6 Implementation and Analysis of Convex Hulls
17.7 Description of Arc Length on Spherical Surfaces
17.8 Interface for Arc Length on Spherical Surfaces
17.9 Implementation and Analysis of Arc Length on Spherical Surfaces
17.10 Arc Length Example: Approximating Distances on Earth
17.11 Questions and Answers
17.12 Related Topics
Colophon
index

Robert Sedgewick has thoroughly rewritten and substantially expanded and updated his popular work to provide current and comprehensive coverage of important algorithms and data structures. Christopher Van Wyk and Sedgewick have developed new C++ implementations that both express the methods in a concise and direct manner, and also provide programmers with the practical means to test them on real applications. Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 250,000 programmers! This particular book, Parts 1n4, represents the essential first half of Sedgewick's complete work. It provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. Although the substance of the book applies to programming in any language, the implementations by Van Wyk and Sedgewick also exploit the natural match between C++ classes and ADT implementations. Highlights * Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures * Greater emphasis on abstract data types (ADTs), modular programming, object-oriented programming, and C++ classes than in previous editions * Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations * New implementations of binomial queues, multiway radix sorting, randomized BSTs, splay trees, skip lists, multiway tries, B trees, extendible hashing, and much more * Increased quantitative information about the algorithms, giving you a basis for comparing them * Over 1000 new exercises to help you learn the properties of algorithms Whether you are learning the algorithms for the first time or wish to have up-to-date reference material that incorporates new programming styles with classic and new algorithms, you will find a wealth of useful information in this book.

This well-accepted introduction to computational geometry is a textbook for high-level undergraduate and low-level graduate courses. The focus is on algorithms and hence the book is well suited for students in computer science and engineering. Motivation is provided from the application areas: all solutions and techniques from computational geometry are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. For students this motivation will be especially welcome. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. All the basic techniques and topics from computational geometry, as well as several more advanced topics, are covered. The book is largely self-contained and can be used for self-study by anyone with a basic background in algorithms. In this third edition, besides revisions to the second edition, new sections discussing Voronoi diagrams of line segments, farthest-point Voronoi diagrams, and realistic input models have been added.

Computers are ubiquitous yet to many they remain objects of irreducible mystery. This text looks at the question of how today's computers can perform such a variety of tasks if computing is just glorified arithmetic. The author illustrates how the answer lies in the fact that computers are essentially engines of logic and that their hardware and software embody concepts developed over centuries by logicians. "Engines of Logic" gives the reader a clear explanation of how and why computers work.

This is a practical guide to building Kalman filters that shows how the filtering equations can be applied to real-life problems. Numerous examples are presented in detail, showing the many ways in which Kalman filters can be designed. Computer code written in FORTRAN, MATLAB[registered], and True BASIC accompanies all of the examples so that the interested reader can verify concepts and explore issues beyond the scope of the text. In certain instances, the authors intentionally introduce mistakes to the initial filter designs to show the reader what happens when the filter is not working properly. The text carefully sets up a problem before the Kalman filter is actually formulated, to give the reader an intuitive feel for the problem being addressed. Because real problems are seldom presented as differential equations, and usually do not have unique solutions, the authors illustrate several different filtering approaches. Readers will gain experience in software and performance tradeoffs for determining the best filtering approach. The material that has been added to this edition is in response to questions and feedback from readers. The third edition has three new chapters on unusual topics related to Kalman filtering and other filtering techniques based on the method of least squares. Chapter 17 presents a type of filter known as the fixed or finite memory filter, which only remembers a finite number of measurements from the past. Chapter 18 shows how the chain rule from calculus can be used for filter initialization or to avoid filtering altogether. A realistic three-dimensional GPS example is used to illustrate the chain-rule method for filter initialization. Finally, Chapter 19 shows how a bank of linear sine-wave Kalman filters, each one tuned to a different sine-wave frequency, can be used to estimate the actual frequency of noisy sinusoidal measurements and obtain estimates of the states of the sine wave when the measurement noise is low.

Semi-supervised learning is a learning paradigm concerned with the study of how computers and natural systems such as humans learn in the presence of both labeled and unlabeled data. Traditionally, learning has been studied either in the unsupervised paradigm (e.g., clustering, outlier detection) where all the data are unlabeled, or in the supervised paradigm (e.g., classification, regression) where all the data are labeled. The goal of semi-supervised learning is to understand how combining labeled and unlabeled data may change the learning behavior, and design algorithms that take advantage of such a combination. Semi-supervised learning is of great interest in machine learning and data mining because it can use readily available unlabeled data to improve supervised learning tasks when the labeled data are scarce or expensive. Semi-supervised learning also shows potential as a quantitative tool to understand human category learning, where most of the input is self-evidently unlabeled. In this introductory book, we present some popular semi-supervised learning models, including self-training, mixture models, co-training and multiview learning, graph-based methods, and semi-supervised support vector machines. For each model, we discuss its basic mathematical formulation. The success of semi-supervised learning depends critically on some underlying assumptions. We emphasize the assumptions made by each model and give counterexamples when appropriate to demonstrate the limitations of the different models. In addition, we discuss semi-supervised learning for cognitive psychology. Finally, we give a computational learning theoretic perspective on semi-supervised learning, and we conclude the book with a brief discussion of open questions in the field. Table of Contents: Introduction to Statistical Machine Learning / Overview of Semi-Supervised Learning / Mixture Models and EM / Co-Training / Graph-Based Semi-Supervised Learning / Semi-Supervised Support Vector Machines / Human Semi-Supervised Learning / Theory and Outlook