Generic Data Structures and Algorithms in Go: An Applied Approach Using Concurrency, Genericity and Heuristics

✍ Scribed by Richard Wiener

• Publisher: Apress
• Year: 2022
• Tongue: English
• Leaves: 590
• Category: Library

✦ Synopsis

Advance your understanding of generic data structures and algorithms and their applications using Go and the effective use of concurrency. You are invited on a journey that aims to improve your programming and problem-solving skills. This book takes you to the next step by showing how to get your programs to work efficiently as well as correctly.
As you explore many data structures and the algorithms and applications associated with them, you'll focus on the trade-offs between speed and storage and the benefits of deploying concurrency when appropriate. This book will demonstrate the huge increases in application performance that are possible. The presentation of classic data structures and techniques of algorithm design (greedy, divide and conquer, branch-and-bound to name a few) provides an essential foundation and toolkit for problem solving. But this book goes further by presenting heuristic algorithms and their implementations for solving computationally intractable combinatoric optimization problems such as the travelling salesperson problem. Ant colony optimization and simulated annealing are among the techniques used.

The consistent style of coding used throughout this book exploits Go’s ability to implement abstract, generic and constrained generic data types without the use of classes. Although some familiarity with Go is assumed, this book should advance your ability to use Go to tackle server-side applications, games, machine learning, information retrieval and other application domains where speed and storage efficiency is essential.

What You'll Learn
Explore classical data structures and algorithms aimed at making your applications run faster or require less storage
Use the new generic features of Go to build reusable data structures
Utilize concurrency for maximizing application performance
See the power of heuristic algorithms for computationally intractable problems
Enhance and improve your Go programming skills

Who This Book Is For
Practicing Go software developers and students who wish to advance their programming and problem-solving skills and experience the excitement and see the benefits of using generic data structures and algorithms that utilize concurrency whenever possible.

✦ Table of Contents

Table of Contents
About the Author
About the Technical Reviewer
Acknowledgments
Introduction
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
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
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
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
Index