The text introduces readers to different paradigms of computing in addition to the traditional approach of discussing fundamental computational problems and design techniques in the random access machine model. Alternate models of computation including parallel, cache sensitive design and streaming algorithms are dealt in separate chapters to underline the significant role of the underlying computational environment in the algorithm design. The treatment is made rigorous by demonstrating new measures of performances along with matching lower bound arguments.
Additional Info
  • Publisher: Cambridge University Press
  • Language: English
  • ISBN : 9781108721998
  • Chapter 1

    Introduction

    Introduction to Design and Analysis of Algorithms - A Contemporary Perspective

  • Chapter 2

    Contents

    Contents

  • Chapter 3

    Figures

    Figures

  • Chapter 4

    Tables

    Tables

  • Chapter 5

    Preface

    Preface

  • Chapter 6

    Acknowledgements

    Acknowledgements

  • Chapter 7

    Chapter 1 - Model and Analysis Price 0.14  |  0.14 Rewards Points

    • 1.1 Computing Fibonacci Numbers
    • 1.2 Fast Multiplication
    • 1.3 Model of Computation
    • 1.4 Randomized Algorithms: A Short Introduction
    • 1.5 Other Computational Models
    • Further Reading
    • Exercise Problems
  • Chapter 8

    Chapter 2 - Basics of Probability and Tail Inequalities Price 0.14  |  0.14 Rewards Points

    • 2.1 Basics of Probability Theory
    • 2.2 Tail Inequalities
    • 2.3 Generating Random Numbers
    • Further Reading
    • Exercise Problems
  • Chapter 9

    Chapter 3 - Warm-up Problems Price 0.14  |  0.14 Rewards Points

    • 3.1 Euclid’s Algorithm for the Greatest Common Divisor (GCD)
    • 3.2 Finding the kth Smallest Element
    • 3.3 SortingWords
    • 3.4 Mergeable Heaps
    • 3.5 A Simple Semi-dynamic Dictionary
    • 3.6 Lower Bounds
    • Further Reading
    • Exercise Problems
  • Chapter 10

    Chapter 4 - Optimization I Brute Force and Greedy Strategy Price 0.14  |  0.14 Rewards Points

    • 4.1 Heuristic Search Approaches
    • 4.2 A Framework for Greedy Algorithms
    • 4.3 Efficient Data Structures for Minimum Spanning Tree Algorithms
    • 4.4 Greedy in Different Ways
    • 4.5 Compromising with Greedy
    • 4.6 Gradient Descent*
    • Further Reading
    • Exercise Problems
  • Chapter 11

    Chapter 5 - Optimization II Dynamic Programming Price 0.14  |  0.14 Rewards Points

    • 5.1 Knapsack Problem
    • 5.2 Context Free Parsing
    • 5.3 Longest Monotonic Subsequence
    • 5.4 Function Approximation
    • 5.5 Viterbi’s Algorithm for Maximum Likelihood Estimation
    • 5.6 Maximum Weighted Independent Set in a Tree
    • Further Reading
    • Exercise Problems
  • Chapter 12

    Chapter 6 - Searching Price 0.14  |  0.14 Rewards Points

    • 6.1 Skip-Lists – A Simple Dictionary
    • 6.2 Treaps: Randomized Search Trees
    • 6.3 Universal Hashing
    • 6.4 Perfect Hash Function
    • 6.5 A log log N Priority Queue*
    • Further Reading
    • Exercise Problems
  • Chapter 13

    Chapter 7 - Multidimensional Searching and Geometric Algorithms Price 0.14  |  0.14 Rewards Points

    • 7.1 Interval Trees and Range Trees
    • 7.2 k–d Trees
    • 7.3 Priority Search Trees
    • 7.4 Planar Convex Hull
    • 7.5 Quickhull Algorithm
    • 7.6 Point Location Using Persistent Data Structure
    • 7.7 Incremental Construction
    • Further Reading
    • Exercise Problems
  • Chapter 14

    Chapter 8 - String Matching and Finger Printing Price 0.14  |  0.14 Rewards Points

    • 8.1 Rabin–Karp Fingerprinting
    • 8.2 KMP Algorithm
    • 8.3 Tries and Applications
    • Further Reading
    • Exercise Problems
  • Chapter 15

    Chapter 9 - Fast Fourier Transform and Applications Price 0.14  |  0.14 Rewards Points

    • 9.1 Polynomial Evaluation and Interpolation
    • 9.2 Cooley–Tukey Algorithm
    • 9.3 The Butterfly Network
    • 9.4 Schonage and Strassen’s Fast Multiplication*
    • 9.5 Generalized String Matching
    • Further Reading
    • Exercise Problems
  • Chapter 16

    Chapter 10 - Graph Algorithms Price 0.14  |  0.14 Rewards Points

    • 10.1 Depth First Search
    • 10.2 Applications of DFS
    • 10.3 Path Problems
    • 10.4 Computing Spanners for Weighted Graphs
    • 10.5 Global Min-cut
    • Further Reading
    • Exercise Problems
  • Chapter 17

    Chapter 11 - Maximum Flow and Applications Price 0.14  |  0.14 Rewards Points

    • 11.0.1 Max-Flow Min-Cut
    • 11.0.2 Ford and Fulkerson algorithm
    • 11.0.3 Edmond–Karp augmentation strategy
    • 11.0.4 Monotonicity lemma and bounding the number of iterations
    • 11.1 Applications of Max-Flow
    • Further Reading
    • Exercise Problems
  • Chapter 18

    Chapter 12 - NP Completeness and Approximation Algorithms Price 0.14  |  0.14 Rewards Points

    • 12.1 Classes and Reducibility
    • 12.2 Cook–Levin Theorem
    • 12.3 Common NP-Complete Problems
    • 12.4 Proving NP Completeness
    • 12.5 Other Important Complexity Classes
    • 12.6 Combating Hardness with Approximation
    • Further Reading
    • Exercise Problems
  • Chapter 19

    Chapter 13 - Dimensionality Reduction Price 0.14  |  0.14 Rewards Points

    • 13.1 Random Projections and the Johnson–Lindenstrauss Lemma
    • 13.2 Gaussian Elimination
    • 13.3 Singular Value Decomposition and Applications
    • Further Reading
    • Exercise Problems
  • Chapter 20

    Chapter 14 - Parallel Algorithms Price 0.14  |  0.14 Rewards Points

    • 14.1 Models of Parallel Computation
    • 14.2 Sorting and Comparison Problems
    • 14.3 Parallel Prefix
    • 14.4 Basic Graph Algorithms
    • 14.5 Basic Geometric Algorithms
    • 14.6 Relation between Parallel Models
    • Further Reading
    • Exercise Problems
  • Chapter 21

    Chapter 15 - Memory Hierarchy and Caching Price 0.14  |  0.14 Rewards Points

    • 15.1 Models of Memory Hierarchy
    • 15.2 Transposing a Matrix
    • 15.3 Sorting in External Memory
    • 15.4 Cache Oblivious Design
    • Further Reading
    • Exercise Problems
  • Chapter 22

    Chapter 16 - Streaming Data Model Price 0.14  |  0.14 Rewards Points

    • 16.1 Introduction
    • 16.2 Finding Frequent Elements in a Stream
    • 16.3 Distinct Elements in a Stream
    • 16.4 Frequency Moment Problem and Applications
    • 16.5 Proving Lower Bounds for Streaming Model
    • Further Reading
    • Exercise Problems
  • Chapter 23

    Appendix A Recurrences and Generating Functions

    • A.1 An Iterative Method – Summation
    • A.2 Linear Recurrence Equations
    • A.3 Generating Functions
    • A.4 Exponential Generating Functions
    • A.5 Recurrences with Two Variables
  • Chapter 24

    Bibliography

    Bibliography

  • Chapter 25

    Index

    Index