Berlin: Springer, 2009. — 434 p. This Festschrift volume, published in honor of Kurt Mehlhorn on the occasion of his 60th birthday, contains 28 papers written by his former Ph.D. students and colleagues as well as by his former Ph.D. advisor, Bob Constable. The volume's title is a translation of the title of Kurt Mehlhorn's first book, "Effiziente Algorithmen", published by...
Parberry I., University of North Texas, 2001, -118 p. Contents: Induction. Correctness. Analysis. Divide and Conquer. Dynamic Programming. Greedy Algorithms. Backtracking. NP completeness.
San Rafael: Morgan & Claypool Publishers, 2019. — 166 p. — (Synthesis Lectures on Distributed Computing Theory). — ISBN: 1681735369. This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization , introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within...
Oxford: Oxford University Press, 1997. - 394 p. Issues of matching and searching on elementary discrete structures arise pervasively in computer science and many of its applications, and their relevance is expected to grow as information is amassed and shared at an accelerating pace. Several algorithms were discovered as a result of these needs, which in turn created the...
Cambridge University Press, 2009, -605 p. Computational complexity theory has developed rapidly in the past three decades. The list of surprising and fund a mental results provedsince 1990 alone could fill a book: These include new probabilistic definitions of classical complexity classes (IP=PSPACE and the PCP theorems) and their implications for the field of approximation...
Boca Raton: CRC Press LLC, 2000. — 1265 p. This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility...
Chapman&Hall/CRC Press, 2010, -990 p. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new...
Chapman and Hall/CRC, 2009. - 950 p. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising...
InTech, 2008, -596 p. Digest of articles The greedy algorithm is one of the simplest approaches to solve the optizmization problem in which we want to determine the global optimum of a given function by a sequence of steps where at each stage we can make a choice among a class of possible decisions. In the greedy method the choice of the optimal decision is made on the...
Atlantis Press, 2012, -247 p. The concept of an instruction sequence is a key concept in practice, but strangely enough it has as yet not come prominently into the picture in theoretical circles. In much work on computer architecture, instruction sequences are under discussion. In spite of this, the notion of an instruction sequence has never been subjected to systematic and...
Manning Publications, 2016. — 258 p. Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and...
Manning Publications, 2016. — 258 p. Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and...
Manning Publications, 2016. — 258 p. Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and...
Manning Publications, 2016. — 258 p. Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and...
Manning Publications, 2016. — 258 p. Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and...
N.-Y.: Prentice Hall, 1997. - 312 p. It's main purpose is to show how to calculate programs. Describing an algebraic approach to programming based on a categorical calculus of relations, Algebra of Programming is suitable for the derivation of individual programs, and for the study of programming principles in general. The programming principles discussed are those paradigms...
Computing Research Repository, 2008, -81 p. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform...
Nova Science Publishers, Inc., 2021. — 114 p. — ISBN: 1536190071. Heuristic local search algorithms are used to find “good” solutions to the NP-hard combinatorial optimization problems that cannot be solved using analytical methods. Chapter one discusses the characterization and computation of heuristic local search algorithm for the Traveling Salesman Problem (TSP) from the...
Prentice Hall, 2006, -291 p. The birth of the theory of computational complexity can be set in the early 1960s when the first users of electronic computers started to pay increasing attention to the performances of their programs. As in the theory of computation, where the concept of a model of computation had led to that of an algorithm and of an algorithmically solvable...
N.-Y.: Springer, 2015. - 554 p. The field of natural computing has been the focus of a substantial research effort in recent decades. One particular strand of this concerns the development of computational algorithms using metaphorical inspiration from systems and phenomena that occur in the natural world. These naturally inspired computing algorithms have proven to be...
Prentice Hall, 1988. - 302 p. From the Preface of the book: Our book is neither a programming manual nor an account of the proper use of data structures. Still less is it a "cookbook" containing a long catalogue of programs ready to be used directly on a machine to solve certain specific problems, but giving at best a vague idea of the principles involved in their design. On...
Prentice-Hall, 1996. — 546 p. — ISBN: 0-13-335068-1. This is an introductory-level algorithm book. It includes worked-out examples and detailed proofs. Presents Algorithms by type rather than application. KEY TOPICS: Includes structured material by techniques employed, not by the application area, so readers can progress from the underlying abstract concepts to the concrete...
Prentice-Hall, 1996. — 546 p. — ISBN: 0-13-335068-1. This is an introductory-level algorithm book. It includes worked-out examples and detailed proofs. Presents Algorithms by type rather than application. KEY TOPICS: Includes structured material by techniques employed, not by the application area, so readers can progress from the underlying abstract concepts to the concrete...
New York: Springer, 2017. — 396 p. This book presents in their basic form the most important models of computation, their basic programming paradigms, and their mathematical descriptions, both concrete and abstract. Each model is accompanied by relevant formal techniques for reasoning on it and for proving some properties. After preliminary chapters that introduce the notions...
London: Springer, 2001. - 153 p. Randomized Algorithms discusses two problems of fine pedigree: counting and generation, both of which are of fundamental importance to discrete mathematics and probability. When asking questions like "How many are there?" and "What does it look like on average?" of families of combinatorial structures, answers are often difficult to find -- we...
North-Holland, 1988, -500 p. During the 1890's, when Peano's five axioms were set afloat, a great effort was done to establish what functions are or are not what we can today algorithmically computable functions. Dedekind and Peano have been the first to use functions defined by induction, an important preliminary stage of the recursive function theory. The foundational...
Springer, 1999. — 533 p. — ISBN: 3-540-63369-3. A Source Book for the History of Mathematics, but one which offers a different perspective by focusing on algorithms. With the development of computing has come an awakening of interest in algorithms. Often neglegted by historians and modern scientists, more concerned with the nature of concepts, algorithmic procedures turn out to...
College Publications, 2004. 256 p. ISBN10: 9780954300647 ISBN13: 978-0954300647 String matching is a very important subject in the wider domain of text processing. It consists of finding one,or more generally, all the occurrences of a string (more generally called a pattern) in a text. The Handbook of Exact String Matching Algorithms presents 38 methods for solving this...
Springer, 2018. - 316 p. - ISBN: 9783319784557 This book constitutes the refereed proceedings of the 12th International Workshop on Frontiers in Algorithmics, FAW 2018, held in Guangzhou, China, in May 2018.The 23 full papers presented in this volume were carefully reviewed and selected from 38 submissions. The papers of this workshop provide a focused forum on current trends...
New York: Springer, 2014. — 358 p. This book constitutes the refereed proceedings of the 8th International Frontiers of Algorithmics Workshop, FAW 2013, held in Zhangjiajie, China, in June 2014. The 30 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 65 submissions. They provide a focused forum on current trends of research...
New Delhi: Wiley India Private Limited, 2007. — 649 p. This text strikes a good balance between rigor and an intuitive approach to computer theory. Covers all the topics needed by computer scientists with a sometimes humorous approach that reviewers found refreshing. The goal of the book is to provide a firm understanding of the principles and the big picture of where computer...
A K Peters, 2002. — 344 p. This book provides a systematic approach for the algorithmic formulation and implementation of mathematical operations in computer algebra programming languages. The viewpoint is that mathematical expressions, represented by expression trees, are the data objects of computer algebra programs, and by using a few primitive operations that analyze and...
A K Peters, 2002. — 344 p. This book provides a systematic approach for the algorithmic formulation and implementation of mathematical operations in computer algebra programming languages. The viewpoint is that mathematical expressions, represented by expression trees, are the data objects of computer algebra programs, and by using a few primitive operations that analyze and...
Gács P., Lovász L. 1999. -180 p. Contents: Introduction and Preliminaries Models of Computation Algorithmic decidability Computation with resource bounds General theorems on space and time complexity Non-deterministic algorithms Randomized algorithms Information complexity: the complexity-theoretic notion of randomness Pseudo-random numbers An application of complexity:...
The MIT Press, 2001. — 1180 p. — ISBN: 0262032937. This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or...
McGraw-Hill Higher Education, 2008. - 332 p. This text explains the fundamentals of algorithms in a story line that makes the material enjoyable and easy to digest. Emphasis is placed on understanding the crisp mathematical idea behind each algorithm, in a manner that is intuitive and rigorous without being unduly formal. Include: The use of boxes to strengthen the narrative:...
Independently published, 2019. — 363 p. — ISBN10: 1686863268; ISBN13: 978-1686863264 This book was written to fill the gap that exists when Computer Science students, and programmers, attempt to learn and analyze the different algorithms that currently exist. I took a course on Algorithms and was disappointed in the type of material that’s currently available. There are two...
CRC Press, 2010. — 824 p. — ISBN: 1420068296, 9781420068290 Explores the Impact of the Analysis of Algorithms on Many Areas within and beyond Computer Science A flexible, interactive teaching format enhanced by a large selection of examples and exercises Developed from the author’s own graduate-level course, Methods in Algorithmic Analysis presents numerous theories,...
Springer, 2011. — 195 p. — ISBN: 0857291203 9780857291202. Logic is a branch of philosophy, mathematics and computer science. It studies the required methods to determine whether a statement is true, such as reasoning and computation. Proofs and Algorithms: An Introduction to Logic and Computability is an introduction to the fundamental concepts of contemporary logic - those of...
Springer, 2011. — 195 p. — ISBN: 0857291203 9780857291202. Logic is a branch of philosophy, mathematics and computer science. It studies the required methods to determine whether a statement is true, such as reasoning and computation. Proofs and Algorithms: An Introduction to Logic and Computability is an introduction to the fundamental concepts of contemporary logic - those of...
John Wiley, 2000, -506 p. Computational complexity theory has been a central area of theoretical computer science since its early development in the mid-1960s. Its subsequent rapid development in the next three decades has not only established itself as a rich, exciting theory but also shown strong influence on many other related areas in computer science, mathematics, and...
Wiley. Hoboken, NJ, USA, Second Edition. 2014. 512 p. Includes references and index. ISBN: 978-1-118-30608-6 (cloth) A thorough revision based on advances in the field of computational complexity and readers’ feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational...
Second edition. — John Wiley, 2014. — 514 p. Computational complexity theory has been a central area of theoretical computer science since its early development in the mid-1960s. The subsequent rapid development in the next three decades has not only established it as a rich exciting theory, but also shown strong influence on many other related areas in computer science,...
Duke University, 2008.- 95 p. The main topics to be covered in this course are: Design Techniques; Searching; Prioritizing; Graph Algorithms; Topological Algorithms; Geometric Algorithms; NP-completeness. The emphasis will be on algorithm design and on algorithm analysis.
The MIT Press, 2017. — 336 p. — ISBN: 978-0262036634. Picture a computer scientist, staring at a screen and clicking away frantically on a keyboard, hacking into a system, or perhaps developing an app. Now delete that picture. In Once Upon an Algorithm, Martin Erwig explains computation as something that takes place beyond electronic computers, and computer science as the study...
The MIT Press, 2017. — 336 p. — ISBN: 978-0262036634. Picture a computer scientist, staring at a screen and clicking away frantically on a keyboard, hacking into a system, or perhaps developing an app. Now delete that picture. In Once Upon an Algorithm, Martin Erwig explains computation as something that takes place beyond electronic computers, and computer science as the study...
Cambridge University Press, 2011. — 355 p. — (London Mathematical Society Lecture Note Series 379). — ISBN: 0521718201. Intended for researchers and graduate students in theoretical computer science and mathematical logic, this volume contains accessible surveys by leading researchers from areas of current work in logical aspects of computer science, where both finite and...
Princeton: Princeton University Press, 2013. — 192 p. — ISBN: 978-0-691-15649-1. The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. The Golden Ticket provides a nontechnical introduction to P-NP,...
McGill-Queen's University Press, 1986. — 203 p. This volume contains papers presented at the First International Workshop on Distributed Algorithms. The papers present solutions to a wide spectrum of problems (leader election, resource allocation, routing, etc.) and focus on a variety of issues that influence communications complexity. The bit complexity of probabilistic leader...
Philadelphia: University of Pennsylvania, 2020. — 446 p. The main goal of this book is to present a mix of material dealing with: Proof systems. Computability and undecidability. The Lambda Calculus. Some aspects of complexity theory. Historically, the theory of computability and undecidability arose from Hilbert’s efforts to completely formalize mathematics and from Godel’s...
W.H. Freeman, 1979. — 347 p. Few technical terms have gained such rapid notoriety as the appelation "NP-complete." In the short time since its introduction in the early 1970's, this term has come to symbolize the abyss of inherent intractability that algorithm designers increasingly face as they seek to solve larger and more complex problems. A wide variety of commonly...
Cambridge University Press, 2008, -632 p. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures...
Cambridge University Press, 2010, -216 p. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures...
New York: Springer, 2018. — 355 p. Insertion, Deletion, and Substitution Register Machines Input-Driven Register Machines and Counter Automata Tissue P Automata as Multiset Pushdown Automata Accepting Strings Input-Driven Tissue P Automata One-Membrane Antiport P Automata Examples and Results Membrane Systems The Efficiency of Membrane Systems A New Solution to N-Queens Problem...
Birkhauser, 1981. - 107 p. A quantitative study of the efficiency of computer methods requires an in-depth understanding of both mathematics and computer science. This monograph, derived from an advanced computer science course at Stanford University, builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in...
Birkhauser, 2008. — 132 p. — ISBN13: 978-0-8176-4728-5 e-ISBN13: 978-0-8176-4729-2. This monograph is derived from an advanced course in computer science at Stanford University on the analysis of algorithms. The course presents examples of the major paradigms used in the precise analysis of algorithms, emphasizing some of the more difficult techniques. Much of the material is...
Third Edition. — Boston: Birkhäuser, 1990. — 139 p. — ISBN: 0817635157, 978-0817635152. This monograph collects some fundamental mathematical techniques that are required for the analysis of algorithms. It builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms,...
3rd ed. — Boston, 2010. — 141 p. — ISBN: 0817647287, 9780817647285 This monograph collects some fundamental mathematical techniques that are required for the analysis of algorithms. It builds on the fundamentals of combinatorial analysis and complex variable theory to present many of the major paradigms used in the precise analysis of algorithms, emphasizing the more difficult...
Oxford University Press, 1995. — 327 p. This book provides a comprehensive analysis of the most important topics in parallel computation. It is written so that it may be used as a self-study guide to the field, and researchers in parallel computing will find it a useful reference for many years to come. The first half of the book consists of an introduction to many fundamental...
Springer, 2008. - 448 p. ISBN: 3540699007 This book constitutes the refereed proceedings of the 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008, held in Gothenborg, Sweden, in July 2008. The 36 revised full papers presented together with 2 invited lectures were carefully reviewed and selected from 111 submissions. Papers were solicited for original research on...
O’Reilly Media, Inc., 2021. — 282 p. — ISBN: 978-1-492-09106-6. 2021-07-20: First Release When it comes to writing efficient code, every software professional needs to have an effective working knowledge of algorithms. In this practical book, author George Heineman (Algorithms in a Nutshell) provides concise and informative descriptions of key algorithms that improve coding in...
Aalto University, 2021. — 221 p. This book is an Introduction to the theory of distributed algorithms, with a focus on distributed graph algorithms (network algorithms) . The topics covered include: Models of computing : precisely what is a distributed algorithm, and what do we mean when we say that a distributed algorithm solves a certain computational problem? Algorithm...
New York: Springer, 2021. — 225 p. This book aims to address the two problems by compressing and unifying important concepts of the two areas and providing exercises in widely-used software applications. We give a transition from logic to computation via linear temporal logic and state machines. The book combines theoretical teaching and practical exercises; the latter is...
Springer, 2021. — 221 p. — (Texts in Computer Science). — ISBN: 978-3-030-87882-5. This textbook aims to help the reader develop an in-depth understanding of logical reasoning and gain knowledge of the theory of computation. The book combines theoretical teaching and practical exercises; the latter is realized in Isabelle/HOL, a modern theorem prover, and PAT, an industry-scale...
Palgrave Macmillan Cham, 2022. — 180 p. — ISBN: 978-3-031-04219-5. During the Iraq War, American soldiers were sent to both fight an enemy and to recover a “failed state” in pixelated camouflage uniforms, accompanied by robots, and armed with satellite maps and biometric hand-held scanners. The Iraq War, however, was no digital game: massive-scale physical death and destruction...
Palgrave Macmillan Cham, 2022. — 180 p. — ISBN: 978-3-031-04219-5. During the Iraq War, American soldiers were sent to both fight an enemy and to recover a “failed state” in pixelated camouflage uniforms, accompanied by robots, and armed with satellite maps and biometric hand-held scanners. The Iraq War, however, was no digital game: massive-scale physical death and destruction...
New York: I/O Press, 2019. — 214 p. Computer science, specifically the theory of computation, deserves to be better known even among non-computer scientists. The reason is simply that it is full of profound thoughts and ideas. It contains some paradoxes that reveal the limits of human knowledge. It provides ways to reason about information and randomness that are understandable...
From the Foundations and Trends in Theoretical Computer Science series by NOWPress, 2009, -110 p. Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to discrete as well...
New York: ACM Books, 2023. — 426 p. Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for "his advancement of our understanding of the complexity of computation in a significant and profound way." This volume includes a...
ACM Books, 2023. — 426 p. — ISBN: 979-8-4007-0778-0. Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for "his advancement of our understanding of the complexity of computation in a significant and profound way." This volume...
Independently published, 2020. — 346 p. — ISBN B08LD1NKL1. An Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology. This book introduces the fundamental concepts of Designing Strategies, Complexity analysis...
IGI Global, 2018. — 385 p. — ISBN: 1522550208, 978-1522550204. Many techniques have been developed to control the variety of dynamic systems. To develop those control techniques, it is fundamental to know the mathematical relations between the system inputs and outputs. Incorporating Nature-Inspired Paradigms in Computational Applications is a critical scholarly resource that...
Prentice-Hall, 2001. — 209 p. — ISBN: 0-13-027961-7. This book focuses on fundamental issues of computation. The readers can master the content and gain lasting perspective from which to understand computers by carefully worked out examples, illustrations, and algorithmic proofs. Teaches the fundamental concepts behind computation. Hundreds of exercises marked according to the...
Pearson Education, Inc., 2005. - 857 p. Introduction: Some representative problems. Basics of Algorithm Analysis. Graphs. Greedy Algorithms. Divide and Conquer. Dynamic Programming. Network Flow. NP and Computational Intractability. PSPACE: A Class of problems beyond NP. Extending the Limits of Tractability. Approximation Algorithms. Local Search. Randomized Algorithms.
Pearson Education, 2005. — 864 p. — ISBN: 0-321-29535-8. Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of...
Cambridge University Press, 2019. — 534 p. — (Encyclopedia of Mathematics and its Applications: 170). — ISBN: 978-1-108-41684-9. Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This self-contained book presents the basic concepts, classical results, current state of the art and possible future directions in the...
Philadelphia: SIAM, 2020. - 222 p. - ISBN: 1611976162. My inspiration for writing a survey of the best algorithms can be summarized by quoting Martin Aigner and Günter Ziegler, whose splendid book Proofs from THE BOOK is now in its sixth edition. They write: Paul Erdós liked to talk about THE BOOK, in which God maintains the perfect proofs for mathematical theorems, following...
Budapest: Typotex, 2014. — 261 p. Some notation and definitions Models of Computation Finite automata The Turing machine The Random Access Machine Boolean functions and Boolean circuits Algorithmic decidability Recursive and recursively enumerable languages Other undecidable problems Godel's incompleteness theorem First-order logic Computation with resource bounds Polynomial...
From the Foundations and Trends in Theoretical Computer Science series by NOWPress, 2009, -127 p. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as...
Chapman & Hall/CRC, 2007. — 253 p. A Taxonomy of Algorithmic Complexity Fundamental Assumptions Underlying Algorithmic Complexity Examples of Complexity Analysis Sources of Disappointments Implications of Nonuniform Memory for Software Implications of Compiler and Systems Issues for Software Implicit Assumptions Implications of the Finiteness of the Representation of Numbers...
New York: Prentice-Hall, 1997. — 375 p. Appropriate for senior and graduate-level courses in Computer Science Theory, Automata, and Theory of Computation. This is the long-awaited Second Edition of Lewis and Papadimitriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the...
Springer, 2010, -222 p. Does P=NP? In just five symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he first wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of computation, it is a very hard...
Springer, 1979, -228 p. Lectures given at Centro Internazionale Matematico Estivo (C.I.M.E.), held in Bressanone (Bolzano), Italy, June 14-23, 1979. The purpose of these lectures is to develop some deeper results in α-recursion theory which will hold in somewhat more general setting than L(α) and in particular in many other admissible sets and structures. In addition, I will...
ITexLi, 2021. — 94 p. — ISBN: 1789852145 9781789852141 1839628553 9781839628559. This book will be useful to an audience interested in the different problems and approaches that are used within the theory of complexity This book examines the meaning of complexity in the context of systems both social and natural. Chapters cover such topics as the traveling salesman problem,...
Princeton: Princeton University Press, 2018. — 408 p. An accessible and rigorous textbook for introducing undergraduates to computer science theory What Can Be Computed? is a uniquely accessible yet rigorous introduction to the most profound ideas at the heart of computer science. Crafted specifically for undergraduates who are studying the subject for the first time, and...
Ottawa: Carleton University, 2017. - 251 p. This is a free textbook for an undergraduate course on the Theory of Computation, which we have been teaching at Carleton University since 2002. Until the 2011/2012 academic year, this course was offered as a second-year course and was compulsory for all Computer Science students. Starting with the 2012/2013 academic year, the course...
Springer, 1998, -337 p. Proof Verification and Approximation Algorithms - Hardly any area in theoretical computer science has been more lively and flourishing during the last few years. Different lines of research which had been developed independently of each other over the years culminated in a new and unexpected characterization of the well-known complexity class NP, based...
New York: Leanpub, 2021. — 194 p. Complexity science is one pillar of modern ways of working. While Complexity literature is very theoretic, this book explores practical applications in software and digital products development. The practices help you navigate everyday Complexity. This book is for leaders, managers, facilitators (Scrum Masters, Agile Coaches), and team...
D. Reidel, 1987. — 384 p. The purpose of this book is manyfold. It is intended both to present techniques useful in software engineering and to expose results of research on properties of these techniques. The major goal of the book is to help the reader in elaboration of his own views on foundations of computing. The present authors believe that semantics of programs will...
Oxford University Press, 2009, -880 p. The idea for this book came about when I was invited to give the Ulam Memorial Lectures in Santa Fe — an annual set of lectures on complex systems for a general audience, given in honor of the great mathematician Stanislaw Ulam. The title of my lecture series was The Past and Future of the Sciences of Complexity. It was very challenging to...
Springer, 2019. — 285 p. — (Algorithms and Computation in Mathematics 27). — ISBN: 978-3-030-03903-5. This book is divided into two parts, one theoretical and one focusing on applications, and offers a complete description of the Canonical Gröbner Cover, the most accurate algebraic method for discussing parametric polynomial systems. It also includes applications to the...
Oxford University Press, 2011. — 985 p. — ISBN: 978-0199233212. Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. But this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results like interactive proofs, cryptography, and...
Springer, 2023. — 530 p. This textbook introduces formal languages and automata theory for upper-level undergraduate or beginning graduate students. While it contains the traditional mathematical development usually employed in computational theory courses, it is also quite different from many of them. Machines, grammars, and algorithms developed as part of a constructive proof...
Addison-Wesley, 1998. — 471 p. — ISBN: 0-201-25828-5. Taking a practical approach, this modern introduction to the theory of computation focuses on the study of problem solving through computation in the presence of realistic resource constraints. The Theory of Computation explores questions and methods that characterize theoretical computer science while relating all...
N.-Y.: Addison-Wesley, 1998. - 471 p. Taking a practical approach, this modern introduction to the theory of computation focuses on the study of problem solving through computation in the presence of realistic resource constraints. The Theory of Computation explores questions and methods that characterize theoretical computer science while relating all developments to practical...
Addison-Wesley, 1998. - 453 p. Taking a practical approach, this modern introduction to the theory of computation focuses on the study of problem solving through computation in the presence of realistic resource constraints. The Theory of Computation explores questions and methods that characterize theoretical computer science while relating all developments to practical issues...
2. Auflage. Vieweg+Teubner Verlag, Springer Fachmedien Wiesbaden GmbH., 2006, 2012. 250 p. — ISBN: 978-3-8348-1692-4, ISBN: 978-3-8348-1980-2. Rezension "Viele brauchbare, nützliche und praktische Beispiele. Die Realisierung mit der Standardsoftware MS Office Excel ist hervorragend." Prof. Dr. Ulrich Schwellenberg, FH Düsseldorf "Das Buch knüpft an dem für Ingenieure bereits...
Springer, 2015. — 160 p. Algorithms are extremely important in science and engineering. One of the main objectives of science is to predict future events; this usually requires sophisticated algorithms. Once we are able to predict future events, a natural next step is to influence these events, i.e., to control the corresponding systems; control also usually requires complex...
Pitman/John Wiley, 1987, -211 p. Parallel complexity theory, the study of resource-bounded parallel computation, is surely one of the fastest-growing areas of theoretical Computer Science. In the light of this, it would be foolish to attempt an encyclopedic coverage of the field. However, it is the belief of the author that its foundations are becoming increasingly clear and...
Cambridge University Press, 1996, -321 p. In the modern world, the importance of information can hardly be overestimated. Information also plays a prominent role in scientific computations. A branch of computational complexity which deals with problems for which information is partial, noisy and priced is called information-based complexity. In a number of information-based...
Rodney Anderson, 2018. — 124 p. — ASIN B07DS7GXFG. An easy & simple guide to analyzing programs and algorithms using Big-O, Big Omega, & Big Theta, including cheat sheets and practice problems.
Rodney Anderson, 2018. — 124 p. — ASIN B07DS7GXFG. An easy & simple guide to analyzing programs and algorithms using Big-O, Big Omega, & Big Theta, including cheat sheets and practice problems.
Th Edition. — World Scientific Publishing, 2023. — 497 p. — ISBN: 9789811260674. This unique compendium highlights the theory of computation, particularly logic and automata theory. Special emphasis is on Computer Science (CS) applications including loop invariants, program correctness, logic programming, and algorithmic proof techniques. This innovative volume differs from...
3rd edition. — Singapore: World Scientific Publishing, 2017. — 468 p. This text presents the formal concepts underlying Computer Science. It starts with a wide introduction to Logic with an emphasis on reasoning and proof, with chapters on Program Verification and Prolog. The treatment of computability with Automata and Formal Languages stands out in several ways: it emphasizes...
Cham: Springer, 2022. — 577 p. Computation theory is a discipline that uses mathematical concepts and tools to expose the nature of "computation" and to explain a broad range of computational phenomena: Why is it harder to perform some computations than others? Are the differences in difficulty that we observe inherently, or are they artifacts of the way we try to perform the...
Cambridge University Press, 2021. — 675 p. — ISBN: 1108494315, 9781108494311. There are no silver bullets in algorithm design, and no single algorithmic idea is powerful and flexible enough to solve every computational problem. Nor are there silver bullets in algorithm analysis, as the most enlightening method for analyzing an algorithm often depends on the problem and the...
Springer, 2021. — 155 p. — (Schriftenreihe der Institute für Systemdynamik (ISD) und optische Systeme (IOS)). — ISBN: 978-3-658-34458-0. Flash memory is an important non-volatile storage medium. Reliable and secure data storage in flash memories requires sophisticated coding and signal processing techniques. Although error-correcting codes are applied in practically all flash...
Rnssd Warren Schaifer, 1992. — 91 p. Heapsort is a classical sorting algorithm doe to Williams. Given an array to sort, Heapsort first transforms the keys of the array into a heap. The heap is then sorted by repeatedly swapping the root of the heap with the last key in the bottom row, and then sifting this new root down to an appropriate position to restore heap order. This...
Independently published, 2023. — 102 p. In the past decade, Artificial Intelligence has been making waves. From self-driving cars to Siri to Alexa, Artificial Intelligence (AI) is everywhere. But what exactly is it? The term "artificial intelligence" was coined in 1956 by John McCarthy, a computer scientist at Dartmouth College. His work was based on the idea that computers...
Bibliographisches Institut & F.A. Brockhaus AG, 1994. — 311 p. About ten years ago I have started my work on a voluminous book project with tentative title Computational Complexity and Fundamental Problems of Numerical Mathematics. One of the central goals with this project is a thorough development of my Splitting Circle Method for fast approximate factorization of complex...
New York: Springer, 2021. — 387 p. In this monograph, the authors develop a methodology that allows one to construct and substantiate optimal and suboptimal algorithms to solve problems in computational and applied mathematics. Throughout the book, the authors explore well-known and proposed algorithms to analyze their quality and the range of their efficiency. The concept of...
American Mathematical Society, 2017. — 519 p. Basic notions and notation. Introduction. What is this book about? Plain Kolmogorov complexity. The complexity of pairs and conditional complexity. Martin-Löf randomness. A priori probability and prefix complexity. Monotone complexity. General scheme for complexities. Shannon entropy and Kolmogorov complexity. Some applications....
American Mathematical Society, 2017. — 519 p. Basic notions and notation. Introduction. What is this book about? Plain Kolmogorov complexity. The complexity of pairs and conditional complexity. Martin-Löf randomness. A priori probability and prefix complexity. Monotone complexity. General scheme for complexities. Shannon entropy and Kolmogorov complexity. Some applications....
Second Edition. — Thomson Course Technology, 2006. — xx+432 p. — ISBN: 0-534-95097-3. This highly anticipated revision of Michael Sipser's popular text builds upon the strengths of the previous edition. It tells the fascinating story of the theory of computation-a subject with beautiful results and exciting unsolved questions at the crossroads of mathematics and computer...
Pearson Education Limited, 2003. — 423 p. The computation of patterns in strings is a fundamental requirement in many areas of science and information processing. The operation of a text editor, the lexical analysis of a computer program, the functioning of a finite automaton, the retrieval of information from a database - these are all activities which may require that...
World Scientific Publishing Company – 2012, 200 p., 2nd Edition ISBN: 9814401153, 9789814401159 A successor to the first edition, this updated and revised book is a great companion guide for students and engineers alike, specifically software engineers who design reliable code. While succinct, this edition is mathematically rigorous, covering the foundations of both computer...
3rd Edition. — World Scientific Publishing, 2018. — 322 p. — ISBN: 978-981-3235-90-8. A successor to the first and second editions, this updated and revised book is a leading companion guide for students and engineers alike, specifically software engineers who design algorithms. While succinct, this edition is mathematically rigorous, covering the foundations for both computer...
O’Reilly Media, 2013. — 332 p. — ISBN: 1449329276, 9781449329273. Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you’ll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming. Rather than use...
Amazon KDP, 2021. — 193 p. — ISBN: 9798749449730. This book presents practical geometry algorithms with computationally fast C++ code implementations. It covers algorithms for fundamental geometric objects, such as points, lines, rays, segments, triangles, polygons, and planes. These algorithms determine the basic 2D and 3D properties, such as area, distance, inclusion, and...
Oxford University Press, 1997. — 683 p. Models of Computation and Formal Languages presents a comprehensive and rigorous treatment of the theory of computability. The text takes a novel approach focusing on computational models and is the first book of its kind to feature companion software. Deus Ex Machina, developed by Nicolae Savoiu, comprises software simulations of the...
New York: Springer, 2007. - 944 p. The papers included topical sections on graph algorithms, computational geometry, complexity, graph drawing, distributed algorithms, optimization, data structure, and game theory.
Hoboken: Wiley, 2012. — 409 p. Offering an accessible approach to the topic, Theory of Computation focuses on the metatheory of computing and the theoretical boundaries between what various computational models can do and not do — from the most general model, the URM (Unbounded Register Machines), to the finite automaton. A wealth of programming-like examples and easy-to-follow...
Wiley, 2012. — 416 p. Offering an accessible approach to the topic, Theory of Computation focuses on the metatheory of computing and the theoretical boundaries between what various computational models can do and not do — from the most general model, the URM (Unbounded Register Machines), to the finite automaton. A wealth of programming-like examples and easy-to-follow...
Kostanay: KSPU, 2018. — 99 p. The manual is written in accordance with the requirements of the State Program for the Development of Education and Science of the Republic of Kazakhstan for 2016-2019 — a phased transition of the formation of the Republic of Kazakhstan to a trilingual education and is intended for students of polyglot groups of specialty 5B011100 "Informatics"....
N.-Y.: Springer, 2009. - 238 p. Computable models pervade present day science and engineering and are implicit in the specification of software systems. Raymond Turner first provides a logical framework for specification and the design of specification languages, then uses this framework to introduce and study computable models. In doing so he presents the first systematic...
Elsiever / MIT Press, 1990. — 1010 p. A comprehensive guide to the various types of complexity in algorithms and computations. Modern developments in computer and software systems have raised many challenging issues concerning the design and efficiency of complex programming applications. There is an increasing need for "advanced theory", to understand and exploit basic...
Springer, 2008. - 432 p. ISBN: 3540763937 Hinter vielen Computer-Programmen stecken intelligente Verfahren, die man als Algorithmen bezeichnet. Algorithmen lösen nicht nur mathematische Zahlen-Aufgaben, sondern auch ganz alltägliche Probleme: Wie ermittle ich den kürzesten Weg zwischen zwei Orten? Oder, wie kann ich einen Kuchen gerecht aufteilen? In diesem Buch erklären...
Princeton: Princeton University Press, 2017. — 391 p. The information age owes its existence to a little-known but crucial development, the theoretical study of logic and the foundations of mathematics. The Great Formal Machinery Works draws on original sources and rare archival materials to trace the history of the theories of deduction and computation that laid the logical...
Springer International, 2014. XII, 466 p., 245 b/w illustrations. - ISBN: 978-3-319-09887-6 (Print) 978-3-319-09888-3 (Online) This book introduces the essential concepts of algorithm analysis required by core undergraduate and graduate computer science courses, in addition to providing a review of the fundamental mathematical notions necessary to understand these concepts....
A K Peters, 2002, -226 p. For the past several years, mathematics majors in the computing track at the University of Pennsylvania have taken a course in continuous algorithms (numerical analysis) in the junior year, and in discrete algorithms in the senior year. This book has grown out of the senior course as I have been teaching it recently. It has also been tried out on a...
Society for Industrial and Applied Mathematics, 1980, -99 p. The two major problem areas which are the concern of Arithmetic Complexity of Computations are: What is the minimum number of arithmetic operations which are needed to perform the computation? How can we obtain a better algorithm when improvement is possible? These two questions are very large in scope, since they...
Springer, 2017. - 281 p. - ISBN: 9783319596051 This book constitutes the proceedings of the 11th International Workshop on Frontiers in Algorithmics, FAW 2017, held in Chengdu, China, in June 2017. The 24 papers presented in this volume were carefully reviewed and selected from 61 submissions. They deal with all aspects of theoretical computer science and algorithms
Springer, 2021. — 256 p. — ISBN: 978-981-16-2608-1. Graph data is powerful, thanks to its ability to model arbitrary relationship between objects and is encountered in a range of real-world applications in fields such as bioinformatics, traffic network, scientific collaboration, World Wide Web and social networks. Graph data mining is used to discover useful information and...
Cambridge: Cambridge University Press, 2022. — 148 p. Using basic category theory, this Element describes all the central concepts and proves the main theorems of theoretical computer science. Category theory, which works with functions, processes, and structures, is uniquely qualified to present the fundamental results of theoretical computer science. In this Element, readers...
Oxford University Press, 1999. - 528 p. ISBN10: 0195125169 ISBN13: 978-0195125160 Popular computer algebra systems such as Maple, Macsyma, Mathematica, and REDUCE are now basic tools on most computers. Efficient algorithms for various algebraic operations underlie all these systems. Computer algebra, or algorithmic algebra, studies these algorithms and their properties and...
Springer, 2011. — 279 p. — (Synthese Library 355). — ISBN: 978-94-007-1346-8. This book intends to show that radical naturalism (or physicalism), nominalism and strict finitism account for the applications of classical mathematics in current scientific theories. The applied mathematical theories developed in the book include the basics of calculus, metric space theory, complex...
New York: Academic Press/Elsevier, 2023. — 230 p. Algebraic Theory for True Concurrency presents the algebraic laws for true concurrency. Parallelism and concurrency are two of the core concepts within Computer Science. This book covers the different realms of coincidence, which enables programs, algorithms or problems to be broken out into order-independent or partially...
IBM T.J. Watson Research Center Yorktown Heights, New York. — 12 p. P-adic Representation and Approximation Newton's Iteration A sample Usage in Algebraic formula Power Series Application Another Example Coupled p-adic Construction Newton's Iteration on P-adic space Zassenhaus' Construction Hensel Lemma Order of Convergence Versus Computational Efficiency Applications of...
World Scientific, 2012. — 856 p. — ISBN: 9814374296. This volume, with a foreword by Sir Roger Penrose, discusses the foundations of computation in relation to nature. It focuses on two main questions: The contributors are world-renowned experts who have helped shape a cutting-edge computational understanding of the universe. They discuss computation in the world from a variety...
Cham: Springer, 2022. — 270 p. This book explores a different pragmatic approach to algorithmic complexity rooted or motivated by the theoretical foundations of algorithmic probability and explores the relaxation of necessary and sufficient conditions in the pursuit of numerical applicability, with some of these approaches entailing greater risks than others in exchange for...
Elsevier, 2004, -353 p. About "quantitative perspective." The subtitle of the book seems to be redundant and requires an explanation. The main purpose of computational complexity is to measure the amount of time, or of space, or of some other resource, that is necessary to solve a computational problem. Thus, by its very nature, computational complexity is a quantitative...
Springer, 2006, -737 p. The proliferation of computing devices in every aspect of our lives increases the demand for better understanding of emerging computing paradigms. For the last fifty years most, if not all, computers in the world have been built based on the von Neumann model, which in turn was inspired by the theoretical model proposed by Alan Turing early in the...
Comments