PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT ALGORITHMS ANALYSIS AND DESIGN Download full : thuvien24/phan-tich-va-thiet-ke-giai-thuat-algorithms-analysis-and-design-98309.html TABLE OF CONTENTS Chapter 1. FUNDAMENTALS.................................................................................... 1 1.1. ABSTRACT DATA TYPE............................................................................................1 1.2. RECURSION..................................................................................................................2 1.2.1. Recurrence Relations...............................................................................................2 1.2.2. Divide and Conquer................................................................................................3 1.2.3. Removing Recursion................................................................................................4 1.2.4. Recursive Traversal.................................................................................................5 1.3. ANALYSIS OF ALGORITHMS...................................................................................8 1.3.1. Framework...............................................................................................................8 1.3.2. Classification of Algorithms....................................................................................9 1.3.3. Computational Complexity....................................................................................10 1.3.4. Average-Case-Analysis..........................................................................................10 1.3.5. Approximate and Asymptotic Results....................................................................10 1.3.6. Basic Recurrences.................................................................................................11 Chapter 2. ALGORITHM CORRECTNESS .......................................................... 14 2.1. PROBLEMS AND SPECIFICATIONS ......................................................................14 2.1.1. Problems................................................................................................................14 2.1.2. Specification of a Problem....................................................................................14 2.2. PROVING RECURSIVE ALGORITHMS..................................................................15 2.3. PROVING ITERATIVE ALGORITHMS...................................................................16 Chapter 3. ANALYSIS OF SOME SORTING AND SEARCHING ALGORITHMS........................................................................................................... 20 3.1. ANALYSIS OF ELEMENTARY SORTING METHODS.........................................20 3.1.1. Rules of the Game..................................................................................................20 3.1.2. Selection Sort.........................................................................................................20 3.1.3. Insertion Sort.........................................................................................................21 3.1.4. Bubble sort.............................................................................................................22 3.2. QUICKSORT...............................................................................................................23 3.2.1. The Basic Algorithm..............................................................................................23 3.2.2. Performance Characteristics of Quicksort............................................................25 3.2.3. Removing Recursion..............................................................................................27 3.3. RADIX SORTING.......................................................................................................27 3.3.1. Bits.........................................................................................................................27 3.3.2. Radix Exchange Sort .............................................................................................28 3.3.3. Performance Characteristics of Radix Sorts.........................................................29 3.4. MERGESORT..............................................................................................................29 3.4.1. Merging .................................................................................................................30 3.4.2. Mergesort...............................................................................................................30 3.5. EXTERNAL SORTING...............................................................................................31 3.5.1. Block and Block Access.........................................................................................31 3.5.2. External Sort-merge ..............................................................................................32 3.6. ANALYSIS OF ELEMENTARY SEARCH METHODS...........................................34 3.6.1. Linear Search ........................................................................................................34Chapter 4. ANALYSIS OF SOME ALGORITHMS ON DATA STRUCTURES36 4.1. SEQUENTIAL SEARCHING ON A LINKED LIST.................................................36 4.2. BINARY SEARCH TREE...........................................................................................37 4.3. PRIORITIY QUEUES AND HEAPSORT..................................................................41 4.3.1. Heap Data Structure..............................................................................................42 4.3.2. Algorithms on Heaps.............................................................................................43 4.3.3. Heapsort................................................................................................................45 4.4. HASHING....................................................................................................................48 4.4.1. Hash Functions......................................................................................................48 4.4.2. Separate Chaining.................................................................................................49 4.4.3. Linear Probing ......................................................................................................50 4.5. STRING MATCHING AGORITHMS........................................................................52 4.5.1. The Naive String Matching Algorithm..................................................................52 4.5.2. The Rabin-Karp algorithm....................................................................................53 Chapter 5. ANALYSIS OF GRAPH ALGORITHMS............................................ 56 5.1. ELEMENTARY GRAPH ALGORITHMS.................................................................56 5.1.1. Glossary.................................................................................................................56 5.1.2. Representation.......................................................................................................57 5.1.3. Depth-First Search................................................................................................59 5.1.4. Breadth-first Search ..............................................................................................64 5.2. WEIGHTED GRAPHS................................................................................................65 5.2.1. Minimum Spanning Tree .......................................................................................65 5.2.2. Prim’s Algorithm...................................................................................................67 5.3. DIRECTED GRAPHS..................................................................................................71 5.3.1. Transitive Closure .................................................................................................71 5.3.2. All Shortest Paths..................................................................................................73 5.3.3. Topological Sorting...............................................................................................74 Chapter 6. ALGORITHM DESIGN TECHNIQUES ............................................. 78 6.1. DYNAMIC PROGRAMMING....................................................................................78 6.1.1. Matrix-Chain Multiplication.................................................................................78 6.1.2. Elements of Dynamic Programming .....................................................................82 6.1.3. Longest Common Subsequence .............................................................................83 6.1.4 The Knapsack Problem...........................................................................................86 6.1.4 The Knapsack Problem...........................................................................................87 6.2. GREEDY ALGORITHMS...........................................................................................88 6.2.1. An Activity-Selection Problem...............................................................................89 6.2.2. Huffman Codes......................................................................................................93 6.3. BACKTRACKING ALGORITHMS...........................................................................97 6.3.1. The Knight’s Tour Problem...................................................................................97 6.3.2. The Eight Queen’s Problem................................................................................101 Chapter 7. NP-COMPLETE PROBLEMS............................................................ 106 7.1. NP-COMPLETE PROBLEMS ..................................................................................106 7.2. NP-COMPLETENESS...............................................................................................1087.3. COOK’S THEOREM.................................................................................................110 7.4. Some NP-Complete Problems....................................................................................110 EXERCISES.............................................................................................................. 112 REFERENCES.......................................................................................................... 120 Chapter 1. FUNDAMENTALS 1.1. ABSTRACT DATA TYPE It’s convenient to describe a data structure in terms of the operations performed, rather than in terms of implementation details. That means we should separate the concepts from particular implementations. When a data structure is defined that way, it’s called an abstract data type (ADT). Some examples: An abstract data type is a mathematical model, together with various operations defined on the model. A set is a collection of zero or more entries. An entry may not appear more than once. A set of n entries may be denoded {a1, a2,…,an}, but the position of an entry has no significance. A multiset is a set in which repeated elements are allowed. For example, {5,7,5,2} is a multiset. initialize insert, is_empty, delete findmin A sequence is an ordered collection of zero or more entries, denoted . The position of an entry in a sequence is significant. initialize length, head, tail, concatenate,… To see the importance of abstract data types, let consider the following problem. Given an array of n numbers, A[1..n], consider the problem of determing the k largest elements, where k ≤ n. For example, if A constains {5, 3, 1, 9, 6}, and k = 3, then the result is {5, 9, 6}. It’s not easy to develop an algorithm to solve the above problem. ADT: multiset Operations: Initialize, Insert(x, M), DeleteMin(M), FindMin(M) The Algorithm: Initialize(M); for i:= 1 to k do Insert(A[i], M); for i:= k + 1 to n do if A[i] > KeyOf(FindMin(M)) then begin DeleteMin(M); Insert(A[i],M) end; In the above example, abstract data type simplifes the program by hiding details of their implementation. ADT Implementation. The process of using a concrete data structure to implement an ADT is called ADT implementation. Abstract Data Operations Data Structured Concrete operations Figure 1.1: ADT Implementation We can use arrays or linked list to implement sets. We can use arrays or linked list to implement sequences. As for the mutiset ADT in the previous example, we can use priority queue data structure to implement it. And then we can use heap data structure to implement priority queue. 1.2. RECURSION 1.2.1. Recurrence Relations Example 1: Factorial function N! = N.(N-1)! for N ≥ 1 0! = 1 Recursive definition of function that involves integer arguments are called recurrence relations. function factorial (N: integer): integer; begin if N = 0 then factorial: = 1 else factorial: = N*factorial (N-1); end; Example 2: Fibonacci numbers Recurrence relation: F N = FN-1 + FN-2 for N ≥ 2 F0 = F1 = 1 1, 1, 2, 3, 5, 8, 13, 21, … function fibonacci (N: integer): integer; begin if N
Posted on: Sat, 17 Aug 2013 15:26:19 +0000
Trending Topics
Recently Viewed Topics
© 2015