Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

اینجــــا یک کتابخانه دیجیتالی است

با بیش از 100000 منبع الکترونیکی رایگان به زبان فارسی ، عربی و انگلیسی

اصطلاحنامه مجموعه ها مرورالفبایی لغت نامه دهخدا

➟

جستجو در لغت نامه

بیشتر

کتابخانه شخصی پرسش از کتابدار ارسال منبع

Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] - نسخه متنی

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

| ،

افزودن به کتابخانه شخصی

میخواهم بخوانم

درحال خواندن

خوانده شده

ارسال به دوستان

آدرس پست الکترونیک گیرنده :

آدرس پست الکترونیک فرستنده :

نام و نام خانوارگی فرستنده :

پیغام برای گیرنده ( حداکثر 250 حرف ) :

کد امنیتی را وارد نمایید

ارسال

جستجو در متن کتاب

بیشتر

تنظیمات قلم

فونت

اندازه قلم

+ - پیش فرض

حالت نمایش

روز نیمروز شب

➟

جستجو در لغت نامه

بیشتر

لیست موضوعات

Sitemap

Table of Contents

Introduction to Algorithms, Second Edition

To the professional

To our colleagues

Changes for the second edition

Acknowledgments for the first edition

Acknowledgments for the second edition

Part I: Foundations

Chapter 1: The Role of Algorithms in Computing

1.2 Algorithms as a technology

Chapter 2: Getting Started

2.2 Analyzing algorithms

2.3 Designing algorithms

Chapter 3: Growth of Functions

3.1 Asymptotic notation

3.2 Standard notations and common functions

Chapter 4: Recurrences

4.1 The substitution method

4.2 The recursion-tree method

4.3 The master method

4.4: Proof of the master theorem

Chapter 5: Probabilistic Analysis and Randomized Algorithms

5.2 Indicator random variables

5.3 Randomized algorithms

5.4 Probabilistic analysis and further uses of indicator random variables

Part II: Sorting and Order Statistics

Chapter 6: Heapsort

6.2 Maintaining the heap property

6.3 Building a heap

6.4 The heapsort algorithm

6.5 Priority queues

Chapter 7: Quicksort

7.2 Performance of quicksort

7.3 A randomized version of quicksort

7.4 Analysis of quicksort

Chapter 8: Sorting in Linear Time

8.1 Lower bounds for sorting

8.2 Counting sort

Chapter 9: Medians and Order Statistics

9.1 Minimum and maximum

9.2 Selection in expected linear time

9.3 Selection in worst-case linear time

Part III: Data Structures

Chapter 10: Elementary Data Structures

10.2 Linked lists

10.3 Implementing pointers and objects

10.4 Representing rooted trees

Chapter 11: Hash Tables

11.1 Direct-address tables

11.2 Hash tables

11.3 Hash functions

11.4 Open addressing

11.5 Perfect hashing

Chapter 12: Binary Search Trees

12.1 What is a binary search tree?

12.2 Querying a binary search tree

12.3 Insertion and deletion

12.4 Randomly built binary search trees

Chapter 13: Red-Black Trees

Chapter 14: Augmenting Data Structures

14.2 How to Augment a Data Structure

14.3 Interval Trees

Part IV: Advanced Design and Analysis Techniques

Chapter 15: Dynamic Programming

15.1 Assembly-line scheduling

15.2 Matrix-chain multiplication

15.3 Elements of dynamic programming

15.4 Longest common subsequence

15.5 Optimal binary search trees

Chapter 16: Greedy Algorithms

16.1 An activity-selection problem

16.2 Elements of the greedy strategy

16.3 Huffman codes

16.4 Theoretical foundations for greedy methods

16.5 A task-scheduling problem

Chapter 17: Amortized Analysis

17.1 Aggregate analysis

17.2 The accounting method

17.3 The potential method

17.4 Dynamic tables

Part V: Advanced Data Structures

Chapter 18: B-Trees

Data structures on secondary storage

18.1 Definition of B-trees

18.2 Basic operations on B-trees

18.3 Deleting a key from a B-tree

Chapter 19: Binomial Heaps

19.1 Binomial trees and binomial heaps

19.2 Operations on binomial heaps

Chapter 20: Fibonacci Heaps

20.1 Structure of Fibonacci heaps

20.2 Mergeable-heap operations

20.3 Decreasing a key and deleting a node

20.4 Bounding the maximum degree

Chapter 21: Data Structures for Disjoint Sets

21.2 Linked-list representation of disjoint sets

21.3 Disjoint-set forests

21.4 Analysis of union by rank with path compression

Part VI: Graph Algorithms

Chapter 22: Elementary Graph Algorithms

22.2 Breadth-first search

22.3 Depth-first search

22.4 Topological sort

22.5 Strongly connected components

Chapter 23: Minimum Spanning Trees

23.1 Growing a minimum spanning tree

23.2 The algorithms of Kruskal and Prim

Chapter 24: Single-Source Shortest Paths

Optimal substructure of a shortest path

Negative-weight edges

Representing shortest paths

Properties of shortest paths and relaxation

Chapter outline

24.1 The Bellman-Ford algorithm

24.2 Single-source shortest paths in directed acyclic graphs

24.3 Dijkstra''s algorithm

24.4 Difference constraints and shortest paths

24.5 Proofs of shortest-paths properties

Chapter 25: All-Pairs Shortest Paths

Chapter outline

25.1 Shortest paths and matrix multiplication

25.2 The Floyd-Warshall algorithm

25.3 Johnson''s algorithm for sparse graphs

Chapter 26: Maximum Flow

26.1 Flow networks

26.2 The Ford-Fulkerson method

26.3 Maximum bipartite matching

26.4 Push-relabel algorithms

26.5 The relabel-to-front algorithm

Part VII: Selected Topics

Chapter 27: Sorting Networks

27.1 Comparison networks

27.2 The zero-one principle

27.3 A bitonic sorting network

27.4 A merging network

27.5 A sorting network

Chapter 28: Matrix Operations

28.1 Properties of matrices

28.2 Strassen''s algorithm for matrix multiplication

28.3 Solving systems of linear equations

28.4 Inverting matrices

28.5 Symmetric positive-definite matrices and least-squares approximation

Chapter 29: Linear Programming

General linear programs

An overview of linear programming

Applications of linear programming

Algorithms for linear programming

29.1 Standard and slack forms

29.2 Formulating problems as linear programs

29.3 The simplex algorithm

29.5 The initial basic feasible solution

Chapter 30: Polynomials and the FFT

Chapter outline

30.1 Representation of polynomials

30.2 The DFT and FFT

30.3 Efficient FFT implementations

Chapter 31: Number-Theoretic Algorithms

31.1 Elementary number-theoretic notions

31.2 Greatest common divisor

31.3 Modular arithmetic

31.4 Solving modular linear equations

31.5 The Chinese remainder theorem

31.6 Powers of an element

31.7 The RSA public-key cryptosystem

31.8 Primality testing

31.9 Integer factorization

Chapter 32: String Matching

Notation and terminology

32.1 The naive string-matching algorithm

32.2 The Rabin-Karp algorithm

32.3 String matching with finite automata

32.4 The Knuth-Morris-Pratt algorithm

Chapter 33: Computational Geometry

33.1 Line-segment properties

33.2 Determining whether any pair of segments intersects

33.3 Finding the convex hull

33.4 Finding the closest pair of points

Chapter 34: NP-Completeness

NP-completeness and the classes P and NP

Overview of showing problems to be NP-complete

Decision problems vs. optimization problems

Chapter outline

34.1 Polynomial time

34.2 Polynomial-time verification

34.3 NP-completeness and reducibility

34.4 NP-completeness proofs

34.5 NP-complete problems

Chapter 35: Approximation Algorithms

Chapter outline

35.1 The vertex-cover problem

35.2 The traveling-salesman problem

35.3 The set-covering problem

35.4 Randomization and linear programming

35.5 The subset-sum problem

Part VIII: Appendix: Mathematical Background

Appendix A: Summations

A.1 Summation formulas and properties

A.2 Bounding summations

Appendix B: Sets, Etc.

Appendix C: Counting and Probability

C.2 Probability

C.3 Discrete random variables

C.4 The geometric and binomial distributions

C.5 The tails of the binomial distribution

List of Figures

List of Corollaries

List of Problems

List of Exercises

توضیحات

افزودن یادداشت جدید

Chapter Notes

The quicksort procedure was invented by Hoare [147]; Hoare's version appears in Problem 7-1. The PARTITION procedure given in Section 7.1 is due to N. Lomuto. The analysis in Section 7.4 is due to Avrim Blum. Sedgewick [268] and Bentley [40] provide a good reference on the details of implementation and how they matter.

McIlroy [216] showed how to engineer a "killer adversary" that produces an array on which virtually any implementation of quicksort takes Θ(n²) time. If the implementation is randomized, the adversary produces the array after seeing the random choices of the quicksort algorithm.