Wiener R. - Generic Data Structures and Algorithms in Go / Обобщённые структуры данных и алгоритмы в Go [2022, PDF, ENG]

Chapter 1: A Tour of Generics and Concurrency in Go
    1.1 Brief History and Description of Go
    1.2 Introducing Generic Parameters
        Adding a New Student by Name
        Adding a New Student by ID Number
        Adding a New Student by Student Struct
        Introducing Generics
        Stringer Type
        Constrained Generic Type
        Implementing an Interface
        Instantiating a Generic Type
        Unconstrained Generic Type any
        Benefits of Generics
        Using Go’s Sort Package
        Sort Type
        Map Functions
        Making MyMap Generic
        Filter Functions
        Making MyFilter Generic
    1.3 Concurrency
        Goroutine
        WaitGroup
        The Channel
        Select Statement
        Use a quit Channel to Avoid Using WaitGroup
        Channel Direction
        Race Condition
        Mutex
        Playing Chess Using Goroutines
        Fibonacci Numbers Using Goroutines
    1.4 Benchmarking Concurrent Applications
        Generating Prime Numbers Using Concurrency
        Sieve of Eratosthenes Algorithm
        Segmented Sieve Algorithm
        Concurrent Sieve Solution
    1.5 Summary.
Chapter 2: Algorithm Efficiency: Sorting and Searching
    2.1 Describing the Speed Efficiency of an Algorithm
        Working with Big O
        Determining Whether a Slice of Numbers Is Sorted
        Using Concurrency
    2.2 Sorting Algorithms
        Bubblesort Algorithm
        Quicksort Algorithm
        Big O Analysis
        Worst Case for Quicksort
        Comparing Bubblesort to Quicksort
        Concurrent Quicksort
        Mergesort Algorithm
        Concurrent Mergesort
        Conclusions
    2.3 Searching Array Slices
        Linear Searches
        Concurrent Searches
        Binary Searches
    2.4 Summary
Chapter 3: Abstract Data Types: OOP Without Classes in Go
    3.1 Abstract Data Type Using Classes
    3.2 Abstract Data Types in Go
        ADT Counter
        Creating a counter Package
        Mechanics of Creating a Package
        Another Example of Implementing an ADT
        Using Composition
    3.3 Polymorphism
        Using Interfaces to Achieve Polymorphism
    3.4 OOP Application: Simplified Game of Blackjack
    3.5 Another OOP Application: Permutation Group of Words
        Using the Standard map Data Structure
    3.6 Summary
Chapter 4: ADT in Action: Game of Life
    4.1 Game
        Rules of Grid Cell Evolution
    4.2 ADT for Grid
    4.3 Console Implementation of the Game
    4.4 GUI Implementation of the Game of Life
        Creating go.mod file
        Program Output
    4.5 Summary
Chapter 5: Stacks
    5.1 Stack ADT
    5.2 Slice Implementation of Generic Stack
        The Get Zero Function
        Why T Is Declared As Ordered
    5.3 Node Implementation of a Generic Stack
    5.4 Compare the Efficiency of Node and Slice Stacks
    5.5 Stack Application: Function Evaluation
        Postfix Evaluation
        We Walk Through Algorithm
        Evaluating Postfix Expression
    5.6 Converting Decimal Number to Binary
    5.7 Maze Application
        Efficient Strategy for Maze Path Using a Stack
        Building Infrastructure for Maze Application
        Completed Maze App
    5.8 Summary
Chapter 6: Queues and Lists
    6.1 Queue ADT
    6.2 Implementation of Slice Queue
        Iterator
    6.3 Implementation of Node Queue
    6.4 Comparing the Performance of Slice and Node Queue
    6.5 Deque
    6.6 Deque Application
    6.7 Priority Queue
    6.8 Queue Application: Discrete Event Simulation of Waiting Line
        Poisson Process
        Simulation Logic
        Implementation of System
        Table of ConTenTs
    6.9 Queue Application: Shuffling Cards
        Card Shuffling Model
    6.10 Linked Lists
    6.11 Singly Linked List
    6.12 Doubly Linked List
        Benefit of Double Linking
    6.13 Summary
Chapter 7: Hash Tables
    7.1 Map
        Hash Encryption
    7.2 How Fast Is a Map?
    7.3 Building a Hash Table
        Create an Empty Hash Table
        Insertion into Hash Table
        Collisions and Collison Resolution
        Load Factor
        Determining Whether a Key Is Present
        Comparing the Performance of Hash Table with Standard Map
    7.4 Hash Application: String Search
        Rolling Hash Computation
        Rabin-Karp Algorithm
    7.5 Generic Set
    7.6 Summary
Chapter 8: Binary Trees
    8.1 Binary Trees
    8.2 Tree Traversal
        Inorder Traversal
        Preorder Traversal
        Postorder Traversal
    8.3 Draw Tree
        Binary Tree Structure
        Infrastructure Used to Display Binary Tree
        Explanation of Code
        Implementation of ShowTreeGraph
        Creating go.mod Files in Subdirectories binarytree and main
    8.4 Summary
Chapter 9: Binary Search Tree
    9.1 Overview
        Searching
        Insertion
        Ordered Output
        Deletion
    9.2 Generic Binary Search Tree
        Type OrderedStringer
        Generic Types Needed for Binary Search Tree
        Methods for Binary Search Tree
        Discussion of Insert, Delete, and Inorder Traversal
        Support Functions
        Implementation of Tree Graphics
        Discussion of binarysearchtree Package and Main Driver
    9.3 Summary
Chapter 10: AVL Trees
    10.1 Overview: Adelson Velsky and Landis
        Tree Rotations
        Insertion
        Deletion
        Facts About AVL Trees
    10.2 Implementation of a Generic AVL Tree
        Explanation of avl Package
        Discussion of Main Driver Results
    10.3 Set Using Map, AVL, and Concurrent AVL
        Implementation of Set Using Map, AVL Tree, and Concurrent AVL Tree
        Explanation of Concurrent AVL Set
        Comparing the Three Set Implementations
        Discussion of Results
    10.4 Summary
Chapter 11: Heap Trees
    11.1 Heap Tree Construction
    11.2 Deletion from a Heap Tree
    11.3 Implementation of a Heap Tree
        Logic for Building a Heap Tree
        Package Heap
        Explanation of Package heap
    11.4 Heap Sort
        Discussion of heapsort Results
    11.5 Heap Application: Priority Queue
    11.6 Summary
Chapter 12: Red-Black Trees
    12.1 Red-Black Trees
        Definition of Red-Black Tree
        Example of Red-Black Tree
    12.2 Insertion Process
        Detailed Walk-Through of Many Insertions
    12.3 Implementation of Red-Black Tree
        Comparing the Performance of Red-Black Tree to AVL Tree
        Benchmark Conclusion
    12.4 Summary
Chapter 13: Expression Trees
    13.1 Expression Trees
    13.2 Construction of an Expression Tree
        Building a New Expression Tree
        Explanation of Function NewTree
        Function Evaluation Using Expression Tree
        Explanation of Method Evaluate
    13.3 Implementation of ShowTreeGraph
    13.4 Summary
Chapter 14: Ecological Simulation with Concurrency
    14.1 Overview  401
    14.2 Specifications
        Mackerel
        Tuna
        Shark
        Output
    14.3 The Design
    14.4 The Implementation
        Data Model for Each Species
        Discussion of Code
        Support Functions
        Discussion of Code
        Required Methods for Mackerel to Be of Type MarineLife
        Discussion of Code
        Move Method for Shark
        Discussion of Code
        Move Method for Tuna
        Output Function for the Graphical Display of Critters
        Discussion of Code
        Full Implementation of Simulation
    14.5 Summary.
Chapter 15: Dynamic Programming
    15.1 Example of Dynamic Programming: nth Fibonacci Number
        Top-Down Dynamic Programming
        Bottom-Up Dynamic Programming
        Recursive Solution
        Discussion of Code
    15.2 Another Application: 0/1 Knapsack Problem
        Brute-Force Solution
        Discussion of Code
        Dynamic Programming Solution
        Discussion of Code
        Discussion of Code
    15.3 DNA Subsequences
        Discussion of Code
    15.4 Summary 440
Chapter 16: Graph Structures
    16.1 Representing Graphs
    16.2 Traversing Graphs
    16.3 Depth- and Breadth-First Search
        Depth-First Search
        Breadth-First Search
    16.4 Single-Source Shortest Path in Graph
        Implementation
        Explanation of Solution
    16.5 Minimum Spanning Tree
        Kruskal Algorithm
    16.6 Implementation of Kruskal Algorithm
        Explanation of Kruskal Implementation
    16.7 Summary
Chapter 17: Travelling Salesperson Problem
    17.1 Travelling Salesperson Problem and Its History
    17.2 An Exact Brute-Force Solution
        Finding Permutations
        Brute-Force Computation for TSP
        Discussion of Code
        Other Solutions
    17.3 Displaying a TSP Tour
        Discussion of Code
    17.4 Summary
Chapter 18: Branch-and-Bound Solution to TSP
    18.1 Branch and Bound for TSP
        An Example
        Computation of Lower Bound
        Branch-and-Bound Algorithm
        The Priority Queue
        A Walk-Through Part of the Five-City Example Presented Earlier
    18.2 Branch-and-Bound Implementation
        Implementation of Priority Queue
        Generating Branch-and-Bound Solution
        Data for main
        Results
    18.3 Summary
Chapter 19: Simulated Annealing Heuristic Solution to TSP
    19.1 Combinatorial Optimization
        Heuristic Solutions
    19.2 Simulated Annealing
        Simulated Annealing Steps
        Problem of Convergence to Local Minimum Rather Than Global Minimum
    19.3 Implementation of Simulated Annealing
        Discussion of Code
        Results
        Displaying Final Results
        Lines Crossing
    19.4 Summary
Chapter 20: Genetic Algorithm for TSP
    20.1 Genetic Algorithm
        High-Level Description of Genetic Algorithm
        More Detailed Description of Genetic Algorithm
    20.2 Implementation of Genetic Algorithm
        Step 1 – Form an Initial Population of Random Tours
        Step 2 – Form an Elite Group of Best Tours
        Step 3 – Tournament Selection
        Step 4 – Mating of Parents
        Form Next Generation
        Putting the Pieces Together
    20.3 Summary
Chapter 21: Neural Networks and Machine Learning
    21.1 Overview of Neural Networks and Machine Learning
        Training
        Neural Networks
        Perceptron
        Schematics of Neural Networks
        A Neuron
    21.2 A Concrete Example
    21.3 Constructing a Neural Network
        Matrices That Represent Network
    21.4 Neural Network Implementation
        Estimating the Partial Derivatives of Cost with Respect to Each Weight
    21.5 Output from Neural Network
    21.6 Summary