Design Analysis Of Algorithm

This book features essential principles of algorithm design and analysis, covering key topics such as algorithm complexity, divide-and-conquer strategies, dynamic programming, and greedy algorithms. Each chapter presents clear explanations, practical examples, and illustrative diagrams, making complex concepts accessible and easy to understand.

• The Vertex-cover Problem
• The Bellman-ford Algorithm
• Representation Of Polynomials
• A Sorting Network
• Properties Of Matrices
• Inverting Matrices
• Polynomials And The Fft
• The Naive String-matching Algorithm
• Flow Networks
• A Bitonic Sorting Network
• Finding The Closest Pair Of Points
• The Set-covering Problem
• String Matching With Finite Automata
• A Merging Network
• The Subset-sum Problem
• Np-completeness And Reducibility
• Single-source Shortest Paths In Directed Acyclic Graphs
• Maximum Bipartite Matching
• Difference Constraints And Shortest Paths
• The Hamiltonian-cycle Problem
• Shortest Paths And Matrix Multiplication
• The Traveling-salesman Problem
• Push-relabel Algorithms
• The Relabel-to-front Algorithm
• String Matching
• The Rabin-karp Algorithm
• The Algorithms Of Kruskal And Prim
• Line-segment Properties
• Determining Whether Any Pair Of Segments Intersects
• Polynomial-time Verification
• Topological Sort
• Strongly Connected Components
• Breadth-first Search
• Minimum Spanning Trees
• Np-completeness Proofs
• Np-completeness
• Representations Of Graphs
• The Knuth-morris-pratt Algorithm
• Approximation Algorithms
• Polynomial Time
• Depth-first Search
• Comparison Networks
• Growing A Minimum Spanning Tree
• Johnson's Algorithm For Sparse Graphs
• Solving Systems Of Linear Equations
• The Ford-fulkerson Method
• Finding The Convex Hull
• The Floyd-warshall Algorithm
• The Zero-one Principle
• Dijkstra's Algorithm
• Least-squares Approximation
• The Dft And Fft
• Np-complete Problems
• Single-source Shortest Paths
• Efficient Fft Implementations
• Introduction To Algorithms
• Efficiency Of Algorithm
• Analysis Of Insertion Sort
• Insertion Sort
• Randomized Algorithms
• The Divide-and-conquer Approach
• The Hiring Problem
• Asymptotic Notation
• Floors And Ceilings
• The Master Method
• Balls And Bins
• Overview Of Recurrences
• Proof Of The Master Theorem
• Indicator Random Variables
• The Proof For Exact Powers
• Analyzing Divide-and-conquer Algorithms
• Streaks
• The Recursion-tree Method
• The On-line Hiring Problem
• Standard Notations And Common Functions
• Probabilistic Analysis And Further Uses Of Indicator Random Variables
• Asymptotic Notation In Equations And Inequalities
• The Substitution Method For Recurrences
• Description Of Quicksort
• Heaps
• Building A Heap
• Lower Bounds For Sorting
• The Heapsort Algorithm
• Maintaining The Heap Property
• Radix Sort
• Minimum And Maximum
• Priority Queues
• Analysis Of Quicksort
• A Randomized Version Of Quicksort
• Selection In Expected Linear Time
• Performance Of Quicksort
• Counting Sort
• Bucket Sort
• Selection In Worst-case Linear Time
• Interval Trees
• Randomly Built Binary Search Trees
• Insertion And Deletion
• Representing Rooted Trees
• Querying A Binary Search Tree
• Introduction To Binary Search Tree
• Implementing Pointers And Objects
• Deletion In Red Black Tree
• Hash Tables
• Stacks And Queues
• Hash Functions
• Rotations Of Red Black Tree
• Red-black Trees
• Direct-address Tables
• Linked Lists
• Perfect Hashing
• Dynamic Order Statistics
• Insertion In Red Black Tree
• Augmenting A Data Structure
• Open Addressing
• A Task-scheduling Problem
• Bounding The Maximum Degree
• Dynamic Tables
• Mergeable-heap Operations
• Assembly-line Scheduling
• Linked-list Representation Of Disjoint Sets
• Elements Of The Greedy Strategy
• Decreasing A Key And Deleting A Node
• Analysis Of Union By Rank With Path Compression
• Deleting A Key From A B-tree
• Operations On Binomial Heaps
• Basic Operations On B-trees
• Data Structures For Disjoint Sets
• Theoretical Foundations For Greedy Methods
• Aggregate Analysis
• Binomial Heaps
• The Potential Method
• Definition Of B-trees
• Longest Common Subsequence
• Greedy Algorithms
• Overview Of Dynamic Programming
• Elements Of Dynamic Programming
• Matrix-chain Multiplication
• Fibonacci Heaps
• Huffman Codes
• Optimal Binary Search Trees
• The Accounting Method
• B-trees
• Disjoint-set Forests