7 Algorithm Design Paradigms

Description

The intended readership includes both undergraduate and graduate students majoring in computer science as well as researchers in the computer science area. The book is suitable either as a textbook or as a supplementary book in algorithm courses. Over 400 computational problems are covered with various algorithms to tackle them. Rather than providing students simply with the best known algorithm for a problem, this book presents various algorithms for readers to master various algorithm design paradigms. Beginners in computer science can train their algorithm design skills via trivial algorithms on elementary problem examples. Graduate students can test their abilities to apply the algorithm design paradigms to devise an efficient algorithm for intermediate-level or challenging problems. Key Features: Dictionary of computational problems: A table of over 400 computational problems with more than 1500 algorithms is provided. Indices and Hyperlinks: Algorithms, computational problems, equations, figures, lemmas, properties, tables, and theorems are indexed with unique identification numbers and page numbers in the printed book and hyperlinked in the e-book version. Extensive Figures: Over 435 figures illustrate the algorithms and describe computational problems. Comprehensive exercises: More than 352 exercises help students to improve their algorithm design and analysis skills. The answers for most questions are available in the accompanying solution manual. Introduction Formulating Computational Problems Least Common Multiple Correctness Volume of a Frustum Euclid's Algorithm Summation Closed Form of Summation Product Computational Complexity Asymptotic Notation Analysis of Algorithms Search Unsorted List Integer Multiplication Maximum Contiguous Subsequence Sum Analysis of Algorithms with Logarithms Exercises Recursive and Inductive Programming Recursion Recursive Programming Types of Recursion Closed Form of a First Order Linear Recursion Inductive Programming on Arithmetic Problems Summation Problems Multiplication n-digit Long Integer Addition n-digit Long Integer Multiplication Matrix Multiplication Power Factorial k-Permutation Fermat Number Problems on List Prefix Sum Number of Ascents Element Uniqueness Searching Order Statistics Sorting Alternating Permutation Random Permutation Palindrome Linked list Definition Array vs. Linked List Insertion Sort with a Linked List Iterative Programming Bubble Sort Tail Recursion Quotient and Remainder Square root of n Lexicographical Order Theorem Proving Exercises Divide and Conquer Dichotomic Divide and Conquer Finding Min Number of Ascents Alternating Permutation Merge Sort Maximum Contiguous Sub-sequence Sum Search Unsorted List Palindrome Checking Up-Down Sequence Bisection With a Single Branch Call Binary Search Bisection Method Power Modulo Quotient and Remainder Problem Beyond Bisection Logarithm Master Theorem n-digit Long Integer Multiplication Matrix Multiplication Beyond the Master Theorem Checking Greater Between Elements Sequence n-digit Long Integer Addition n-digit Long Integer by a Single Digit Multiplication Iterative Divide and Conquer Logarithm Base b Radix r Number System Merge Sort II Partition and Conquer Bit Partitioning Radix-select Radix-sort Stable Counting Sort General Applications Drawing a Perfect Binary Tree Drawing a Fibonacci Tree Truth Table Construction Scheduling a Round Robin Tennis Tournament Exercises Greedy Algorithm Problems on List Order Statistics Sorting Alternating Permutation Optimization Problems Select the k Subset Sum Maximization Postage Stamp Minimization Problem 0-1 Knapsack Fractional Knapsack Unbounded integer knapsack Rod cutting Classical Optimization and Related Problems Scheduling Problems Activity Selection Problem Task Distribution with a Minimum Number of Processors Multiprocessor Scheduling Bin Packing Job Scheduling with Deadline Graph Problems Graph Representation Vertex Cover Minimum Spanning Tree Shortest Path Traveling Salesman Problem Minimum Length Code Huffman Code Minimum Length r-ary Code Exercises Tabulation - Strong Induction Strong Inductive Programming Prime Factors Stamp Problems 3-5 Stamp Problem Postage stamp minimization problems Unbounded Subset Sum Equality Unbounded Subset Sum Minimization More Optimization Problems Rod Cutting Unbounded Integer Knapsack Problem Weighted Activity Selection Problem Proving Recurrence Relations Divide Recurrence Relations Complete Recurrence Relations Euler Zigzag Number Memoization Winning Ways Problem Divide Recurrence Relations Linear Divide Recurrence Relations Fibonacci and Lucas Sequences Fibonacci Kibonacci Number Lucas Sequences Memoization in Divide & Conquer Directed Acyclic Graph Problems Topological Sorting Number of paths problem Shortest Path Length in DAG Shortest Path Cost in Weighted DAG Minimum Spanning Rooted Tree Critical Path Problem Exercises Higher Dimensional Tabulation Two Dimensional Strong Inductive Programming Prefix Sum of Two Dimensional Array Stamp Combinatorics Postage Stamp Equality Minimization Problem 0-1 Knapsack Unbounded Integer Knapsack Subset sum equality problem Unbounded Subset Product Equality Problem Problems on Strings Longest Common Sub-sequence String Edit Distance: InDel Levenshtein Distance Longest Palindromic Sub-sequence Problems on Combinatorics Binomial Coefficient Lucas Sequence Coefficient Integer Partition Twelve Fold Ways of Combinatorics Integer Partition with at Most k Parts Three Dimensional Tabulation 01-Knapsack with Two Constraints Bounded Integer Partition Exercises Stack and Queue Stack Balancing Parenthesis Undo and Redo Procedure Stack NFA Acceptance Propositional Logic with Stacks Infix, Prefix, and Postfix Notations Evaluating Postfix Expression Prefix Evaluation Infix Evaluation Graph Problems with Stacks Depth First Search Graph Connectivity Cycle Detection in Ungraphs Cycle Detection in Digraphs Topological Sorting with a Stack Queue Breadth First Search Shortest Path Length Topological Sorting With a Queue Huffman Code Using a Queue Circular Array in Strong Inductive Programming Kibonacci Postage Stamp Equality Minimization Bouncing Array Cylindrical Two Dimensional Array 0-1 Knapsack Ways of Stamping Rolling Cylinder on Triangle Tables Binomial Coefficient Stirling Numbers of the Second Kind Bell Number Set Partition Number of at Most k Partitions Set Partition Number of at Least k Partitions Integer partition Hopping Cylindrical Array Exercises Tree Data Structures for Dictionary Binary Tree Definition Depth and Height Number of Rooted Binary Trees Binary Search Trees Definition Search in BST Insertion in BST Min and Max in BST Deletion in BST Average Case Analysis AVL Trees Height Balanced Binary Tree Insertion in AVL Deletion in AVL 2-3 Trees Definition Insertion Deletion B Trees Definition Insertion Deletion B+ Trees Definition Insertion Deletion Skip List Insertion Deletion Exercises Priority Queue Heap Complete Tree Heap Definition Insertion Delete_Min/Max Operation Constructing a Heap Problems on Lists Heapselect Heapsort Alternating Permutation Problem Greedy Algorithms with Heap Fractional Knapsack Problem Activity Selection Problem Huffman Code with Heaps Min-max Heap Checking Min-max Heap Insert Delete_min and Delete_max Construct Leftist Heap Definition of a Leftist Heap Merge Operation Construction AVL Tree as a Priority Queue AVL Select Stability Exercises Reduction Definitions Reduction: px p py Dual problem: px p py GBW p LBW Reduction to Sorting Order Statistics Alternating Permutation Element Uniqueness Random Permutation Sorting-complete Reduction to Graph Problems NPP-complete More Sorting Algorithms Critical Path Problem to Longest Path Cost Problem Longest Increasing Sub-sequence to LPL Activity Selection Problem to LPC String Matching to LPC SPC-complete Proving Lower Bound Lower Bound for Sorting Lower Bound for AVL Tree Construction Convex Hull Multi-reduction Combinatorics Integer Partition Problem At Most or At Least Combinatorics Reduction Relations in Fibonacci Related Problems Combining with Strong Inductive Programming Maximum Prefix Sum Longest Increasing Sub-sequence Longest Alternating Sub-sequence Longest Palindromic Consecutive Sub-sequence Consecutive Sub-sequence Arithmetic Problems minCSS p MCSS minCSPp p MCSPp MCSPp p MCSS Kadane's Algorithm Reduction to Matrix Problems Fibonacci Kibonacci Number of Path Problem Exercises NP-complete Definitions Computability Tractability Non-deterministic in Polynomial Time P vs. NP NP-complete NP-hard NP-complete Logic Problems Combinational Circuit Satisfiability Satisfiability of CNF-3 Satisfiability of CNF NAND Gate Only Circuit Satisfiability NP-complete Set Theory Problems Subset Sum Equality Problem Unbounded Subset Sum Problem Set Partition Problem NP-hard Optimization Problems Subset Sum Maximization Problem Subset Sum Minimization Problem 01-Knapsack Problem NP-complete Scheduling Problems Bin Packing Problem Multiprocessor Scheduling Problem NP-hard Graph Problems Clique Problem Independent Set Vertex Cover Set Cover Problem Hamiltonian Path and Cycle Traveling Salesman Problem co-NP-complete Fallacy Tautology LEQ CNF vs. DNF Frobenius Postage Stamp Exercises Randomized and Approximate Algorithms Las Vegas Method Partitioning Quicksort Quickselect Random Permutation by Riffling Random Alternating Permutation Monte Carlo Method Top m Percent Primality Test Approximate Algorithms Subset Sum Maximization Vertex Cover Metric Traveling Salesman Problem Probably Approximately Correct Exercises Bibliography Index of Computational Problems List of Abbreviations List of Symbols and Notations