Poised Solutions Tech Library

Introduction to Algorithms

Introduction to Algorithms Author: Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein Publisher: MIT Press Published: 2009 Pages: 1292

Introduction to Algorithms is one of the best books on Algorithms. Algorithms are at the heart of all computer programs, they are the basic building blocks of an application. An algorithm is a self contained problem that can be solved in a number of ways but for which an optimum solutions exists in relation to the overall system. Introduction to Algorithms is a classic text on Algorithm produce by MIT press and so often used in Computer Science Degrees at MIT (Massachusetts Institute of Technology) to teach Algorithms, the book is often revised through the years, and of course it is best to get hold of the latest copy, though Algorithms much like Platonic forms don't tend to change too much from year to year.

Introduction to Algorithms Chapters

Introduction to Algorithms Chapters

1. The Role of Algorithms in Computing
   • Algorithms
   • Algorithms as a Technology
2. Getting Started
   • Insertion Sort
   • Analyzing Algorithms
   • Designing Algorithms
3. Growth of Functions
   • Asymptotic Notation
   • Standard Notations and Common Functions
4. Divide and Conquer
   • The Maximum-Subarray Problem
   • Strassen's Algorithm for Matrix Multiplication
   • The Substitution Method for Solving Recurrences
   • The Recursion-Tree Method for Solving Recurrences
   • The Master Method for Solving Recurrences
   • Proof of the Master Theorem
5. Probabilistic Analysis and Randomized Algorithm
   • The Hiring Problem
   • Indicator Random Variables
   • Randomized Algorithms
   • Probabilistic Analysis and Further Uses of Indicator Random Variables
6. Heapsort
   • Heaps
   • Maintaining the Heap Property
   • Building a Heap
   • The Heapsort Algorithm
   • Priority Queues
7. Quicksort
   • Description of Quicksort
   • Performance of Quicksort
   • A Randomised Version of Quicksort
   • Analysis of Quicksort
8. Sorting in Linear Time
   • Lower Bounds for Sorting
   • Counting Sort
   • Radix Sort
   • Bucket Sort
9. Medians and Order Statistics
   • Minimum and Maximum
   • Selection in Expected Linear Time
   • Selection in Worst-Case Linear Time
10. Elementary Data Structures
    • Stacks and Queues
    • Linked Lists
    • Implementing Pointers and Objects
    • Representing Rooted Trees
11. Hash Tables
    • Direct-address Tables
    • Hash Tables
    • Hash Functions
    • Open Addressing
    • Perfect Hashing
12. Binary Search Trees
    • What is a Binary Search Tree?
    • Querying a Binary Search Tree
    • Insertion and Deletion
    • Randomly Built Binary Search Trees
13. Red-Black Trees
    • Properties of Red-Black Trees
    • Rotations
    • Insertions
    • Deletion
14. Augmenting Data Structures
    • Dynamic Order Statistics
    • How to Augment a Data Structure
    • Interval Trees
15. Dynamic Programming
    • Rod Cutting
    • Matrix-chain Multiplication
    • Elements of Dynamic Programming
    • Longest Common Subsequence
    • Optimal Binary Search Trees
16. Greedy Algorithms
    • An Activity-Selection Problem
    • Elements of the Greedy Strategy
    • Huffman Codes
    • Matroids and Greedy Methods
    • A Task-Scheduling Problem as a Matroid
17. Amortized Analysis
    • Aggregate Analysis
    • The Accounting Method
    • The Potential Method
    • Dynamic Tables
18. B-Trees
    • Definition of B-trees
    • Basic Operation on B-Trees
    • Deleting a Key From a B-Tree
19. Fibonacci Heaps
    • Structure of Fibonacci Heaps
    • Mergeable-heap Operations
    • Decreasing a Key and Deleting a Node
    • Bounding the Maximum Degree
20. van Emde Boas Trees
    • Preliminary Approaches
    • A Recursive Structure
    • The van Embde Boas Tree
21. Data Structures for Disjoint Sets
    • Disjoint-set Operations
    • Linked-list Representation of Disjoint Sets
    • Disjoint-set Forests
    • Analysis of Union by Rank with Path Compression
22. Elementary Graph Algorithms
    • Representations of Graphs
    • Breadth-First Search
    • Depth-First Search
    • Topological Sort
    • Strongly Connected Components
23. Minimum Spanning Trees
    • Growing a Minimum Spanning Tree
    • The Algorithms of Kruskal and Prim
24. Single-Sources Shortest Paths
    • The Bellman-Ford Algorithm
    • Single-Source Shortest Paths in Directed Acyclic Graphs
    • Dijkstra's Algorithm
    • Difference Constraints and Shortest Paths
    • Proofs of Shortest-Paths Properties
25. All-Pairs Shortest Paths
    • Shortest Paths and Matrix Multiplication
    • The Floyd-Warshall Algorithm
    • Johnson's Algorithm for Sparse Graphs
26. Maximum Flow
    • Flow Networks
    • The Ford-Fulkerson Method
    • Maximum Bipartite Matching
    • Push Relabel Algorithms
    • The Relabel-to-Front Algorithm
27. Multithreaded Algorithms
    • The Basics of Dynamic Multithreading
    • Multithreaded Matrix Multiplication
    • Multithreaded Merge Sort
28. Matrix Operations
    • Solving Systems of Linear Equations
    • Inverting Matrices
    • Symmetric Positive-Definite Matrices and Least-Squares Approximation
29. Linear Programming
    • Standard and Slack Forms
    • Formulating Problems as Linear Programs
    • The Simplex Algorithm
    • Duality
    • The Initial Basic Feasible Solutions
30. Polynomials and the FFT
    • Representing Polynomials
    • The DFT and FFT
    • Efficient FFT Implementations
31. Number-Theoretic Algorithms
    • Elementary Number-Theoretic Notions
    • Greatest Common Divisor
    • Modular Arithmetic
    • Solving Modular Linear Equations
    • The Chinese Remainder Theorem
    • Powers of an Element
    • The RSA Public-Key Cryptosystem
    • Primality Testing
    • Integer Factorization
32. String Matching
    • The Naive String Matching Algorithm
    • The Rabin-Karp Algorithm
    • String Matching with Finite Automata
    • The Knuth-Morris-Pratt Algorithm
33. Computational Geometry
    • Line Segment Properties
    • Determining Whether Any Pair Segments Intersects
    • Finding the Convex Hull
    • Finding the Closest Pair of Points
34. NP-Completeness
    • Polynomial Time
    • Polynomial Time Verification
    • NP-Completeness and Reducibility
    • NP-Completeness Proofs
    • NP-Complete Problems
35. Approximation Algorithms
    • The Vertex Cover Problem
    • The Traveling Salesman Problem
    • The Set Covering Problem
    • Randomization and Linear Programming
    • The Subset-Sum Problem

Introduction to Algorithms Appendices

1. Summations
   • Summations Formulas and Properties
   • Bounding Summations
2. Sets, Etc.
   • Sets
   • Relations
   • Functions
   • Graphs
   • Trees
3. Counting Probability
   • Counting
   • Probability
   • Discrete Random Variables
   • The Geometric and Binomial Distributions
   • The Tails of the Binomial Distribution
4. Matrices
   • Matrices and Matrix Operations
   • Basic Matrix Properties
5. Bibliography
6. Index