Algorithms, data structures and programming techniques. Edition IV

Basic textbook for learning algorithms

An affordable introduction to algorithms
No unnecessary theory
Ready solutions in C ++


This is the next edition of a well-tested and valued by programmers, lecturers and students of the book, which is the basic textbook for learning algorithms. First, the author will familiarize you with the elementary issues in this field and explain where the rapid progress in this discipline is made. During further reading, you will learn concepts such as recursion, complexity analysis and sorting and searching algorithms or numerical algorithms. You will quickly master algorithm optimization methods, coding and data compression methods, and graph algorithm elements. The algorithms presented in the book are illustrated with examples of source codes in C ++, facilitating understanding of the issues covered. Transparent form, practical examples and accessible language make this book a quick and painless way to master algorithms as well as data structures and the best programming techniques.

The history of algorithms
The use of recursion
Analysis of the complexity of algorithms
Sorting algorithms
Search algorithms
Searching for texts
Data structures and their implementation
Optimization of algorithms
Advanced programming techniques
The use of graphs
Introduction to artificial intelligence
Data coding and compression
Numeric algorithms
A guide to compile and run programs (GCC, DevC ++, Microsoft Visual C ++ Express Edition).

Quickly and painlessly master all algorithmics!

Table of contents Preface (9)
Chapter 1. Before we start (17)

• As it used to be, exceptions from the history of algorithmic machines (18)
• How has it recently happened, that is, who "invented" the programming methodology (21)
  
• Program concepts process (22)
• Abstraction levels of the description and the choice of language (23)
• The correctness of algorithms (24)

Chapter 2. Recursion (27)

• Definition of recursion (27)
• Illustration of the recursion concept (28)
• How do recurrent programs work? (thirty)
• Danger of recursion (31)
• Fibonacci sequence (31)
• Stack overflow! (33)
• Traps continued (34)
• From here to eternity (34)
• Definition correct, but ... (35)
• Types of recursive programs (36)
• Recursive thinking (38)
• Example 1: Spiral (38)
• Example 2: Squares "even" (40)
• Practical remarks on recursive techniques (41)
• Tasks (42)
• Task solutions and tips (44)

Chapter 3. Analysis of the complexity of algorithms (49)

• Definitions and examples (50)
• Once again, the function of the engine (53)
• Resetting the array fragment (57)
• We fall into a trap (58)
• Different types of computational complexity (59)
• New task: simplify calculations! (61)
• Analysis of recursive programs (62)
• Terminology and definitions (62)
• Illustration of the method on the example (63)
• Logarithmic distribution (64)
• Conversion of the field of recursive equation (66)
• Ackermann function, meaning something for gourmets (66)
• Computational complexity is not a religion! (68)
• Software optimization techniques (68)
• Tasks (69)
• Task solutions and tips (70)

Chapter 4. Sorting algorithms (73)

• Sorting by insertion, class O algorithm (N2) (74)
• Bubble sorting, class O algorithm (N2) (75)
• Quicksort, class O algorithm (N log N) (77)
• Heap Sort - sorting by mounds (80)
• Merging sorted sets (82)
• Sorting by merging (83)
• External sorting (84)
• Practical considerations (87)

Chapter 5. Types and data structures (89)

• Basic and complex types (89)
• Strings and captions in C ++ (90)
• Abstract data structures (92)
• One-way lists (93)
• Array implementation of lists (115)
• Stack (119)
• FIFO queues (123)
• Heap and priority queues (125)
• Trees and their representations (131)
• Collections (143)
• Tasks (145)
• Task solutions (146)

Chapter 6. Derekursywacja and optimization of algorithms (147)

• How does the compiler work? (148)
• A bit of formalism will not hurt! (150)
• A few examples of algorithmic derekursive (151)
• Stacking Derekursive (154)
• Elimination of local variables (154)
• The opposite function method (156)
• The classic derekursive patterns (158)
• While type (159)
• If-else scheme (160)
• Diagram with a double recursive call (162)
• Summary (163)

Chapter 7. Searching algorithms (165)

• Linear search (165)
• Binary search (166)
• Key transformation (hashing) (167)
• In search of H functions (169)
• The most known H functions (169)
• Handling access conflicts (171)
• Return to sources (172)
• Once again boards! (173)
• Linear sampling (173)
• Double keying (175)
• Applications of key transformation (176)
• Summary of key transformation methods (176)

Chapter 8. Searching the texts (179)

• Brute-force algorithm (179)
• New search algorithms (181)
• The KMP algorithm (182)
• Algorithm of Boyer and Moore (185)
• Algorithm of Rabin and Karp (187)

Chapter 9. Advanced programming techniques (191)

• Divide and Conquer Programming (192)
• Finding the minimum and maximum in the number table (193)
• Multiplying matrix size N (N (195)
• Multiplying whole numbers (197)
• Other known "divide and conquer" algorithms (198)
• The "voracious" algorithms, or to eat something, it's time ... (199)
• Rucksack problem, or the walker's tourist life is not easy (200)
• Dynamic programming (202)
• Fibonacci sequence (203)
• Equations with many variables (204)
• The longest common subsequence (205)
• Other programming techniques (208)
• Bibliographic notes (210)

Chapter 10. Elements of graph algorithms (211)

• Definitions and basic concepts (212)
• Cycles in graphs (214)
• Ways of graph representation (217)
• Table representation (217)
• Dictionaries of nodes (218)
• Lists versus collections (219)
• Basic operations on graphs (220)
• Total graphs (220)
• Graph composition (220)
• The power of the graph (220)
• Roy-Warshall algorithm (221)
• Floyd-Warshal algorithm (224)
• Dijkstra's algorithm (227)
• Bellman-Ford algorithm (228)
• Minimal spanning tree (228)
• Kruskal's algorithm (229)
• Prima algorithm (230)
• Graph searching (230)
• Deep down strategy (top-down search) (231)
• The "breadth" strategy (232)
• Other search strategies (234)
• The problem of proper selection (235)
• Summary (239)
• Tasks (239)

Chapter 11. Numerical algorithms (241)

• Search for zero places of the function (241)
• Iterative calculation of function values (243)
• Interpolation of a Lagrange function (244)
• Differentiation of functions (245)
• Integration of the Simpson method (247)
• Solving systems of linear equations using the Gaussian method (248)
• Final remarks (251)

Chapter 12. Can computers think? (253)

• Review of areas of interest of Artificial Intelligence (254)
• Expert systems (255)
• Neural networks (256)
• Problem representation (257)
• Exercise 1 (258)
• Twin games and games trees (259)
• The mini-max algorithm (260)

Chapter 13. Data coding and compression (265)

• Data coding and arithmetic of large numbers (267)
• Symmetrical coding (267)
• Asymmetric coding (268)
• Primitive methods (274)
• Breaking of ciphers (275)
• Data compression techniques (275)
• Compression through mathematical modeling (277)
• RLE compression (278)
• Huffman data compression (279)
• LZW encoding (283)
• The concept of dictionary coding on examples (284)
• GIF Format Description (286)

Chapter 14. Various tasks (289)

• Task texts (289)
• Solutions (291)

Appendix A: Meet C ++ in five minutes! (295)

• Elements of the C ++ language on examples (295)
• The first program (295)
• Directive #include (296)
• Subprograms (296)
• Procedures (296)
• Features (297)
• Arithmetic operations (298)
• Logic operations (298)
• Indicators and dynamic variables (299)
• References (300)
• Complex types (300)
• Boards (300)
• Records (301)
• Switch instruction (301)
• Iterations (302)
• Recursive structures (303)
• Main program parameters (303)
• File operations in C ++ (303)
• Object-oriented programming in C ++ (304)
• Terminology (304)
• Objects on the example (305)
• Static members of classes (308)
• Constant class methods (308)
• Inheritance of ownership (308)
• Conditional code in C ++ (311)

Appendix B: Calculation systems at a glance (313)

• Several definitions (313)
• Binary system (313)
• Arithmetic operations on binary numbers (315)
• Boolean operations on binary numbers (315)
• Eight system (317)
• Hexadecimal (317)
• Variables in the computer's memory (317)
• Character encoding (318)

Appendix C: Compiling sample programs (321)

• Contents of the ZIP archive on ftp (321)
• Free C ++ compilers (321)
• Compilation and startup (322)
• GCC (322)
• Visual C ++ Express Edition (323)
• Dev C ++ (327)

Literature (329)
List of tables (331)
List of illustrations (333)
Index (339)