|
" Design and Analysis of Algorithms : "
Sandeep Sen, Indian Institute of Technology, Delhi, Amit Kumar, Indian Institute of Technology, Delhi
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
839608
|
| Main Entry
|
:
|
Sen, Sandeep
|
| Title & Author
|
:
|
Design and Analysis of Algorithms : : a contemporary perspective. /\ Sandeep Sen, Indian Institute of Technology, Delhi, Amit Kumar, Indian Institute of Technology, Delhi
|
| Publication Statement
|
:
|
[Place of publication not identified]: Cambridge University Press, 2019.
|
| Page. NO
|
:
|
1 online resource
|
| ISBN
|
:
|
1108654932
|
|
|
:
|
: 9781108654937
|
|
|
:
|
1108496822
|
|
|
:
|
1108721990
|
|
|
:
|
9781108496827
|
|
|
:
|
9781108721998
|
| Contents
|
:
|
Cover; Design and Analysis of Algorithms; Title; Copyright; Dedication; Content; Figures; Tables; Preface; Who can use it; Suggested use of the chapters; Acknowledgments; CHAPTER 1 Model and Analysis; 1.1 Computing Fibonacci Numbers; 1.2 Fast Multiplication; 1.3 Model of Computation; 1.4 Randomized Algorithms: A Short Introduction; 1.4.1 A different flavor of randomized algorithms; 1.5 Other Computational Models; 1.5.1 External memory model; 1.5.2 Parallel model; Further Reading; Exercise Problems; CHAPTER 2 Basics of Probability and Tail Inequalities; 2.1 Basics of Probability Theory
|
|
|
:
|
2.2 Tail Inequalities2.3 Generating Random Numbers; 2.3.1 Generating a random variate for an arbitrary distribution; 2.3.2 Generating random variables from a sequential file; 2.3.3 Generating a random permutation; Further Reading; Exercise Problems; CHAPTER 3 Warm-up Problems; 3.1 Euclid's Algorithm for the Greatest Common Divisor (GCD); 3.1.1 Extended Euclid's algorithm; 3.1.2 Application to cryptography; 3.2 Finding the kth Smallest Element; 3.2.1 Choosing a random splitter; 3.2.2 Median of medians; 3.3 Sorting Words; 3.4 Mergeable Heaps; 3.4.1 Merging binomial heaps
|
|
|
:
|
3.5 A Simple SemidynamicDictionary3.5.1 Potential method and amortized analysis; 3.6 Lower Bounds; Further Reading; Exercise Problems; CHAPTER 4 Optimization I: Brute Force and Greedy Strategy; 4.1 Heuristic Search Approaches; 4.1.1 Game trees; 4.2 A Framework for Greedy Algorithms; 4.2.1 Maximum spanning tree; 4.2.2 Finding minimum weight subset; 4.2.3 A scheduling problem; 4.3 Efficient Data Structures for Minimum Spanning Tree Algorithms; 4.3.1 A simple data structure for Union-Find; 4.3.2 A faster scheme; 4.3.3 The slowest growing function?; 4.3.4 Putting things together
|
|
|
:
|
4.3.5 Path compression only4.4 Greedy in Different Ways; 4.5 Compromising with Greedy; 4.6 Gradient Descent; 4.6.1 Applications; Further Reading; Exercise Problems; CHAPTER 5 Optimization II: Dynamic Programming; 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 6 Searching; 6.1 SkipLists- A Simple Dictionary; 6.1.1 Construction of skiplists; 6.1.2 Analysis
|
|
|
:
|
6.1.3 Stronger tail estimates6.2 Treaps: Randomized Search Trees; 6.3 Universal Hashing; 6.3.1 Existence of universal hash functions; 6.4 Perfect Hash Function; 6.4.1 Converting expected bound to worst case bound; 6.5 A log log N Priority Queue; Further Reading; Exercise Problems; CHAPTER 7 Multidimensional Searching and Geometric Algorithms; 7.1 Interval Trees and Range Trees; 7.1.1 Twodimensionalrange queries; 7.2 k-d Trees; 7.3 Priority Search Trees; 7.4 Planar Convex Hull; 7.4.1 Jarvis march; 7.4.2 Graham's scan; 7.4.3 Sorting and convex hulls; 7.5 Quickhull Algorithm; 7.5.1 Analysis
|
| Abstract
|
:
|
The text covers important algorithm design techniques, such as greedy algorithms, dynamic programming, and divide-and-conquer, and gives applications to contemporary problems. Techniques including Fast Fourier transform, KMP algorithm for string matching, CYK algorithm for context free parsing and gradient descent for convex function minimization are discussed in detail. The book's emphasis is on computational models and their effect on algorithm design. It gives insights into algorithm design techniques in parallel, streaming and memory hierarchy computational models. The book also emphasizes the role of randomization in algorithm design, and gives numerous applications ranging from data-structures such as skip-lists to dimensionality reduction methods.
|
| Subject
|
:
|
Algebra.
|
| Subject
|
:
|
Algorithms.
|
| Subject
|
:
|
Computer science.
|
| Subject
|
:
|
Geometry.
|
| Subject
|
:
|
Logic.
|
| Subject
|
:
|
Mathematics.
|
| Subject
|
:
|
Algebra.
|
| Subject
|
:
|
Algorithms.
|
| Subject
|
:
|
Computer science.
|
| Subject
|
:
|
Geometry.
|
| Subject
|
:
|
Logic.
|
| Subject
|
:
|
Mathematics.
|
| Dewey Classification
|
:
|
005.1
|
| LC Classification
|
:
|
QA9.58.S454 2019
|
| Added Entry
|
:
|
Kumar, Amit
|
| |