Chuyên Đề Phân tích và thiết kế giải thuật algorithms analysis and design

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 34
3.6.2. Binary Search 35
Chapter 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 .108
7.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 operationsperformed, 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 typeis a mathematical model, together
with various operations defined on the model.
A setis a collection of zero or more entries. Anentry 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 multisetis a set in which repeated elements are allowed. For example, {5,7,5,2} is a
multiset.
initialize
insert,
is_empty,
delete
findmin
A sequenceis an ordered collection of zero or more entries, denoted<a1, a2, ,an>. 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 problemof 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:= 1to kdo

REFERENCES
[1] Sedgewick, R., Algorithms, Addison – Wesley, 1990.
[2] Cormen, T. H., Leiserson,C. E., and Rivest, R.L., Introduction to Algorithms, The MIT
Press, 1997.
[3]Kingston, J. H., Algorithmsand DataStructures– Design, Correctness, Analysis,
Addison – Wesley, 1990.
[4] Kruse, R. L. and Ryba, A. J., DataStructures and Program Design in C++, Prentice
Hall, 1999.
[5] Aho, A. V., Hopcroft, J. E., and Ullman, J. D., Data Structures and Algorithms, Addison
– Wesley, 1987.