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

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