Introduction to the Design and Analysis of Algorithms

by Anany V. Levitin

Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, "Introduction to the Design and Analysis of Algorithms" presents the subject in a coherent and innovative manner. Written in a student-friendly style, the book emphasizes the understanding of ideas over excessively formal treatment while thoroughly covering the material required in an introductory algorithms course. Popular puzzles are used to motivate students' interest and strengthen their skills in algorithmic problem solving. Other learning-enhancement features include chapter summaries, hints to the exercises, and a detailed solution manual.

Features
Employs an innovative and more comprehensive taxonomy of algorithm design techniques.
Covers mathematical analysis of both nonrecursive and recursive algorithms, as well as empirical analysis and algorithm visualization.
Discusses limitations of algorithms and ways to overcome them.
Treats algorithms as problem-solving tools and develops algorithmic thinking by using puzzles and games.
Contains over 600 exercises with hints for students and detailed solutions for instructors.
New chapter! Iterative improvement algorithms: the simplex method, maximum network flows, maximum matching in bipartite graphs, and the stable marriage problem.
New! Revised section on approximation algorithms for TSP.

Table Of Contents
1.Introduction
1.1 What is an Algorithm?
1.2 Fundamentals of Algorithmic Problem Solving
1.3 Important Problem Types 1.4 Fundamental Data Structures
2. Fundamentals of the Analysis of Algorithm Efficiency
2.1 Analysis Framework
2.2 Asymptotic Notations and Basic Efficiency Classes
2.3 Mathematical Analysis of Nonrecursive Algorithms
2.4 Mathematical Analysis of Recursive Algorithms
2.5 Example: Fibonacci Numbers
2.6 Empirical Analysis of Algorithms
2.7 Algorithm Visualization
3. Brute Force
3.1 Selection Sort and Bubble Sort
3.2 Sequential Search and Brute-Force String Matching
3.3 Closest-Pair and Convex-Hull Problems by Brute Force
3.4 Exhaustive Search
4. Divide-and-Conquer
4.1 Mergesort 4.2 Quicksort
4.3 Binary Search
4.4 Binary Tree Traversals and Related Properties
4.5 Multiplication of Large Integers and Strassen’s Matrix Multiplication
4.6 Closest-Pair and Convex-Hull Problems by Divide-and-Conquer
5. Decrease-and-Conquer
5.1 Insertion Sort
5.2 Depth-First Search and Breadth-First Search
5.3 Topological Sorting
5.4 Algorithms for Generating Combinatorial Objects
5.5 Decrease-by-a-Constant-Factor Algorithms
5.6 Variable-Size-Decrease Algorithms
6. Transform-and-Conquer
6.1 Presorting
6.2 Gaussian Elimination
6.3 Balanced Search Trees
6.4 Heaps and Heapsort
6.5 Horner’s Rule and Binary Exponentiation
6.6 Problem Reduction
7. Space and Time Tradeoffs
7.1 Sorting by Counting
7.2 Input Enhancement in String Matching
7.3 Hashing
7.4 B-Trees
8. Dynamic Programming
8.1 Computing a Binomial Coefficient
8.2 Warshall’s and Floyd’s Algorithms
8.3 Optimal Binary Search Trees
8.4 The Knapsack Problem and Memory Functions
9. Greedy Technique
9.1 Prim’s Algorithm
9.2 Kruskal’s Algorithm
9.3 Dijkstra’s Algorithm
9.4 Huffman Trees
10. Iterative Improvement
10.1 The Simplex Method
10.2 The Maximum-Flow Problem
10.3 Maximum Matching in Bipartite Graphs
10.4 The Stable Marriage Problem
11. Limitations of Algorithm Power
11.1 Lower-Bound Arguments
11.2 Decision Trees
11.3 P, NP, and NP-complete Problems
11.4 Challenges of Numerical Algorithms
12. Coping with the Limitations of Algorithm Power
12.1 Backtracking
12.2 Branch-and-Bound
12.3 Approximation Algorithms for NP-hard Problems
12.4 Algorithms for Solving Nonlinear Equations

Genres: Computer Science, Algorithms, Programming, Reference, Textbooks, Nonfiction, Science

544 pages, Paperback

First published January 1, 2002

Reviews

[Abbie · Rating 4 out of 5]

Pretty good introduction to algorithms. The writing style wasn't overly dry or boring. The explanations usually made sense, but occasionally felt lack in details. Some of the problem questions were quite difficult and sometimes seemed unrelated to the on page instruction material. The solutions manual helped me understand most of the difficult problems, but some were still ambiguous. This is a good textbook for use with a class, but perhaps not so great for self-learning unless you can find a community to further explain concepts and problems.

[Pramod · Rating 5 out of 5]

This book is the greatest written book on algorithmic thinking. Among hundreds of topics taught in Computer Science program, I fell madly in love with one topic and that is because of this book. The book introduced me to my girlfriend -- algorithms or algorithmic thinking. I went to Ph.D. in Algorithms because of this love. I credit this book in teaching me the art and science of algorithmic thinking to nail real-life problems.

[Marian · Rating 5 out of 5]

Concise chapters, engaging writing style, and fun historical asides. I appreciated the pseudocode throughout the book and the exercise hints in the back of the book. I did have to resort to internet videos for some of the concepts, so this book is not a one-stop shop. However, it's still one of the better computer science textbooks out there.

[John Smith · Rating 4 out of 5]

Pretty good. Difficult subject but good book. Pretty clearly presented.

[Jason · Rating 3 out of 5]

I would give this a 3.5-4.0 rating as it isn't the most crystal-clear book. It impressively uses the most straightforward, casual language possible to describe a very complex topic. The exercises are challenging, though, and I don't feel the text adequately scaffolded them. Algorithms is one of those courses you have to revisit repeatedly, so I suspect I will have to dig into more sources.

[Rohan · Rating 3 out of 5]

The questions in the book are interesting but when approaching them with just the explanation from the book it requires some serious thinking - explanations are okay from the book though. Good for students and interview prep

[J.T. · Rating 1 out of 5]

Wish the book took a more straight forward approach to each algorithm. Feels like it jumps around.

[Jyotiprakash Mishra · Rating 4 out of 5]

good

[Mochammad · Rating 5 out of 5]

Buku yang sangat menarik...haha *fingercrossed*
Untuk ukuran texbook kuliah, ini termasuk buku yg sangat mudah dipahami, penjelasanya bagus dan sederhana

[Pradeep Prajapati]

Study

[Delhi Irc]

Location: GG6 IRC
Accession no: DL026768

[Abdul Rub]

best book

[Mayur · Rating 5 out of 5]

k

[Su Myat · Rating 4 out of 5]

Very good book for algorithms and analysis for programming. Included lots of exercise