Algorithms and data structures

The most important element of the process of creating a good computer program is the proper selection of algorithms and data structures - especially in terms of their effectiveness.
The book is a great introduction to this problem. Provides an overview of the main algorithmic issues. By using it, the reader will learn the methods of creating and analyzing algorithms. Thanks to them, he will be able to design effective algorithms for problems appearing in his programming practice or research work.
Algorithms and data structures are the subject of one of the basic subjects in any IT studies. The book is tested didactically. It was created on the basis of a script with the same title and notes for lectures conducted by the Authors at the Faculty of Mathematics, Computer Science and Mechanics of the University of Warsaw.

Table of Contents

Preface

1. Basic principles of analyzing algorithms

1.1. Computational complexity
1.2. Recursive equations
1.3. Creating functions
1.4. Semantic correctness
1.5. Basic data structures
1.5.1. List
1.5.2. Collection
1.5.3. count
1.5.4. Functional notation for object attributes
1.5.5. Tree
1.6. Elimination of recursion
1.7. The cost of amortized operation in the data structure
1.8. Methods of arranging algorithms
1.8.1. The "divide and conquer" method
1.8.2. Dynamic programming
1.8.3. Greedy method
1.8.4. Other methods
Works

2. Sorting

2.1. Selectionsort - sorting by selection
2.2. Insertionsort - insertion sorting
2.3. Quicksort - quick sorting
2.4. Lower limit on the complexity of the sorting problem
2.5. Positional sorting
2.6. Priority queues and heapsort algorithm
2.7. Tournament trees and selection tasks
2.8. Fast algorithms for determining the k th major element in the sequence
2.9. Merge ordered sequences
2.10. External sorting
2.10.1. Multiphase merging with 4 files
2.10.2. Multiphase merging with 3 files
Works

3. Dictionaries

3.1. Unplanned list implementation
3.2. Listed order implementation
3.3. Binary search trees
3.3.1. AVL trees
3.3.2. Self-organizing BST trees
3.4. Mixing
3.4.1. Selection of the mixing function
3.4.2. Data structures used to solve the collision problem
3.5. Positional search
3.5.1. RST trees
3.5.2. TRIE trees
3.5.3. PATRICIA trees
3.6. External search
3.6.1. Unordered files
3.6.2. Files with hash function
3.6.3. Sequential indexed files
3.6.4. B-tree as a multilevel rare index
3.6.5. B-tree as a multi-level dense index
Works

4. Complex data structures for element sets

4.1. The problem of adding disjoint sets
4.1.1. Letter implementation
4.1.2. Tree implementation
4.2. Connectable priority queues
Works

5. Text algorithms

5.1. The pattern search problem
5.1.1. N ("naive") algorithm
5.1.2. The KMP (Knuth-Morris-Pratt) algorithm
5.1.3. Linear algorithm for the problem of finding a two-dimensional pattern,
that is Baker's algorithm
5.1.4. GS 'algorithm (version of Galil-Seiferas algorithm for a certain class of patterns)
5.1.5. The KMR algorithm (Karp-Miller-Rosenberg)
5.1.6. The KR algorithm (Karpa-Rabina)
5.1.7. BM (Boyer-Moore) algorithm
5.1.8. FP (Fisher-Paterson) algorithm
5.2. Suffix trees and subheading graphs
5.2.1. Unfavorable representation of the suffix tree
5.2.2. Creating a suffix tree
5.2.3. Creating a pie graph
5.3. Other text algorithms
5.3.1. Calculation of the longest common underlayment
5.3.2. Calculation of the longest common substring
5.3.3. Search for double words
5.3.4. Search for symmetric words
5.3.5. Cyclic equivalence
5.3.6. Huffman algorithm
5.3.7. Lexical calculation of the maximum suffix
5.3.8. Unambiguous coding
5.3.9. Counting the number of pods
Works

6. Parallel algorithms

6.1. Parallel calculation of expressions and simple sequential programs
6.2. Parallel sorting
Works

7. Graph algorithms

7.1. Consistent components
7.2. Dual-component components
7.3. Strongly consistent components and strong orientation
7.4. Euler's cycles
7.5. 5-coloring of planar graphs
7.6. The shortest paths and the minimum spanning tree
Works

8. Geometric algorithms

8.1. Elemental geometric algorithms
8.2. The problem of belonging
8.3. Convex shell
8.4. Sweeping method
8.4.1. The least distant pair of points
8.4.2. Couples of intersecting episodes
Works

Bibliography
Index