Set theory, logic, discrete mathematics, and fundamental algorithms (along with their correctness and complexity analysis) will always remain useful for computing professionals and need to be understood by students who want to succeed. This textbook explains a number of those fundamental algorithms to programming students in a concise, yet precise, manner. The book includes the background material needed to understand the explanations and to develop such explanations for other algorithms. The author demonstrates that clarity and simplicity are achieved not by avoiding formalism, but by using it properly.
The book is self-contained, assuming only a background in high school mathematics and elementary program writing skills. It does not assume familiarity with any specific programming language. Starting with basic concepts of sets, functions, relations, logic, and proof techniques including induction, the necessary mathematical framework for reasoning about the correctness, termination and efficiency of programs is introduced with examples at each stage. The book contains the systematic development, from appropriate theories, of a variety of fundamental algorithms related to search, sorting, matching, graph-related problems, recursive programming methodology and dynamic programming techniques, culminating in parallel recursive structures.
Author(s): Jayadev Misra
Publisher: Association for Computing Machinery
Year: 2023
Language: English
Pages: 564
Cover
Halftitle
Title Page
Copyright Page
Dedication
Contents
Preface
Acknowledgment
Chapter 1 Introduction
1.1 Motivation for This Book
1.2 Lessons from Programming Theory
1.3 Formalism: The Good, the Bad and the Ugly
Chapter 2 Set Theory, Logic and Proofs
2.1 Set
2.2 Function
2.3 Relation
2.4 Order Relations: Total and Partial
2.5 Propositional Logic
2.6 Predicate Calculus
2.7 Formal Proofs
2.8 Examples of Proof Construction
2.9 Exercises
Chapter 3 Induction and Recursion
3.1 Introduction
3.2 Examples of Proof by Induction
3.3 Methodologies for Applying Induction
3.4 Advanced Examples
3.5 Noetherian or Well-founded Induction
3.6 Structural Induction
3.7 Exercises
Chapter 4 Reasoning About Programs
4.1 Overview
4.2 Fundamental Ideas
4.3 Formal Treatment of Partial Correctness
4.4 A Modest Programming Language
4.5 Proof Rules
4.6 More on Invariant
4.7 Formal Treatment of Termination
4.8 Reasoning about Performance of Algorithms
4.9 Order of Functions
4.10 Recurrence Relations
4.11 Proving Programs in Practice
4.12 Exercises
4.A Appendix: Proof of Theorem 4.1
4.B Appendix: Termination in Chameleons Problem
Chapter 5 Program Development
5.1 Binary Search
5.2 Saddleback Search
5.3 Dijkstra’s Proof of the am–gm Inequality
5.4 Quicksort
5.5 Heapsort
5.6 Knuth–Morris–Pratt String-matching Algorithm
5.7 A Sieve Algorithm for Prime Numbers
5.8 Stable Matching
5.9 Heavy-hitters: A Streaming Algorithm
5.10 Exercises
Chapter 6 Graph Algorithms
6.1 Introduction
6.2 Background
6.3 Specific Graph Structures
6.4 Combinatorial Applications of Graph Theory
6.5 Reachability in Graphs
6.6 Graph Traversal Algorithms
6.7 Connected Components of Graphs
6.8 Transitive Closure
6.9 Single Source Shortest Path
6.10 Minimum Spanning Tree
6.11 Maximum Flow
6.12 Goldberg–Tarjan Algorithm for Maximum Flow
6.13 Exercises
6.A Appendix: Proof of the Reachability Program
6.B Appendix: Depth-first Traversal
Chapter 7 Recursive and Dynamic Programming
7.1 What is Recursive Programming
7.2 Programming Notation
7.3 Reasoning About Recursive Programs
7.4 Recursive Programming Methodology
7.5 Recursive Data Types
7.6 Dynamic Programming
7.7 Exercises
7.A Appendices
Chapter 8 Parallel Recursion
8.1 Parallelism and Recursion
8.2 Powerlist
8.3 Pointwise Function Application
8.4 Proofs
8.5 Advanced Examples Using Powerlists
8.6 Multi-dimensional Powerlist
8.7 Other Work on Powerlist
8.8 Exercises
8.A Appendices
Bibliography
Author’s Biography
Index
