Synthesis and analysis of algorithms
This book is a precise and concise sort of a textbook which can be used in the field of synthesis and analysis of algorithms. It includes programs in Pascal and C++ to illustrate the algorithms.
Published in 2008, it is a result of many years of creating algorithms for students to understand and apply the Theory of algorithms.
Feel free to read and apply.
I will appreciate if you let me know what you think about it.
Contents
Foreword ................................................. .............................................. 5
Chapter 1. Algorithm. Recursive algorithms. Complexity ................. 9
Algorithm - concept, properties, presentation and types ................... 9
Recursive algorithms ................................................ ........................ 19
Algorithm Complexity ............................................... ....................... 23
Examples for determining the complexity of an algorithm ........................ 27
Chapter 2. Sorting algorithms ............................................ ......... 39
Digital sorting ................................................ .......................... 39
Lexicographic sorting ................................................ ................. 42
Direct insertion sorting algorithm ............................... 46
Selection algorithm by direct selection ............................................ ... 48
Direct exchange sorting algorithms .......................................... 49
Sorting by Shell's Algorithm ............................................. .......... 51
Merging Sorting Algorithm ............................................. 52
Pyramid. Pyramid operations ............................................... ....... 54
Pyramid sorting ................................................ ................... 58
Quick sort algorithm .............................................. ............ 60
Chapter 3. Search algorithms ............................................ ............. 64
Sequential and binary search in an array ... 64
Hashing ................................................. ............................................ 65
Chapter 4. Data Structures ............................................ ............ 70
Stack ................................................. .................................................. ... 70
Tail ................................................. ................................................ 72
List ................................................. ................................................ 75
Count ................................................. .................................................. .. 80
Crawl algorithm for non - oriented counting ...... 85
Crawl algorithm for non-oriented count ............ 87
Algorithm for determining the minimum skeleton of Count. 88
Daxtra algorithm for determining the shortest path in count ............ 92
Tree Structure ................................................ .................................. 93
Recording and reading in a binary tree search ........................... 99
Chapter 5. Methods for compiling algorithms ........................... 104
Method 'Divide and conquer' ............................................ ............ 104
Dynamic Programming ................................................ ............ 107
Chapter 6. Heuristic, Probable, Parallel, and Genetic
algorithms ................................ .......................................... 112
Heuristic algorithms ................................................ ...................... 112
Probability algorithms ................................................ ............ 114
Random Numbers Generators .............................................. .......... 118
Parallel algorithms ................................................ ....................... 119
Genetic Algorithms ................................................ ........................ 123
Chapter 7. Algorithms Theory ............................................ ......... 125
Turing machines ............................................... ............................. 125
Universal Turing Machine .............................................. ....... 128
Recursive functions ................................................ ....................... 129
Basic hypothesis of theory of algorithms ............................... 130
Algorithmically unsolvable tasks ............................................... 131
Tasks of NP class .............................................. .............................. 133
Algorithm Verification ............................................... .............. 135
Chapter 8. Algorithms for Arithmetic Operations ............................ 139
Counting systems ................................................ ................................. 139
Arithmetic actions in a binary system ..................................... 141
Convert numbers from one number system to another ....... 143
Representation of fixed and floating point numbers
Straight, reverse and additional code ............................................ ..... 150
Floating-point numbering algorithm .............................. 154
Multiplication algorithms ............................................... ................... 155
Algorithms for division ............................................... ....................... 158
Appendix 1. Algorithms from the top ten in Internet-
rating ................................................. ............................................ 162
Appendix 2. Examples of graph theory tasks with lower-
sophisticated algorithms (for standalone work) ........................... 162
Appendix 3. Programming with C ++ algorithms
from the textbook ................................................ 165
Literature ................................................. ....................................... 205
Alphabetical index ................................................ .............................. 207