Data Structures and Algorithms

A data structure is the organization of data to reduce the storage space used and to reduce the difficulty while performing different tasks. Data structures are used to handle and work with large amounts of data in various fields, such as database management and internet indexing services.

In this chapter, we will focus on the definition of abstract datatypes, classifying data structures into linear, nonlinear, homogeneous, heterogeneous, and dynamic types. Abstract datatypes, such as Container, List, Set, Map, Graph, Stack, and Queue, are presented in this chapter. We will also cover the performance analysis of data structures, choosing the right data structures, and structural design patterns.

The reader can start writing basic algorithms using the right data structures in Go. Given a problem, choosing the data structure and different algorithms...

Technical requirements

Install Go version 1.10 from https://golang.org/doc/install for your operating system.

The code files for this chapter can be found at the following GitHub URL: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter01.

Check the installation of Go by running the hello world program at https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/hello_world:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main

// importing fmt package
import (
  "fmt"
)
// main method
func main() {
  fmt.Println("Hello World")
}

Run the following commands:

go build
./hello_world

The following screenshot displays the output:

Let's take a look at the classification of data structures and structural design patterns in the next...

Classification of data structures and structural design patterns

You can choose a data structure by using classification. In this section, we discuss data structure classification in detail. The design patterns related to the data structure are covered after the classification.

In the next section, we'll take a look at classification of data structures.

Classification of data structures

The term data structure refers to the organization of data in a computer's memory, in order to retrieve it quickly for processing. It is a scheme for data organization to decouple the functional definition of a data structure from its implementation. A data structure is chosen based on the problem type and the operations performed...

Representation of algorithms

A flow chart and pseudo code are methods of representing algorithms. An algorithm shows the logic of how a problem is solved. A flow chart has different representation symbols such as Entry, Exit, Task, Input/Output, Decision Point, and Inter Block. A structured program consists of a series of these symbols to perform a specific task. Pseudo code has documentation, action, and flow control keywords to visualize an algorithm. The documentation keywords are TASK and REM. SET, PUT, and GET are the action keywords.

Let's take a look at the different representations of algorithms, that is, flow charts and Pseudo code in the next sections.

Flow chart

The flow control keywords are SET, LOOP, (WHILE...

Complexity and performance analysis

The efficiency of an algorithm is measured through various parameters, such as CPU time, memory, disk, and network. The complexity is how the algorithm scales when the number of input parameters increases. Performance is a measure of time, space, memory, and other parameters. Algorithms are compared by their processing time and resource consumption. Complexity measures the parameters and is represented by the Big O notation.

Complexity analysis of algorithms

The complexity of an algorithm is measured by the speed of the algorithm. Typically, the algorithm will perform differently based on processor speed, disk speed, memory, and other hardware parameters. Hence, asymptotical complexity is...

Brute force algorithms

A brute force algorithm solves a problem based on the statement and the problem definition. Brute force algorithms for search and sort are sequential search and selection sort. Exhaustive search is another brute force algorithm where the solution is in a set of candidate solutions with definitive properties. The space in which the search happens is a state and combinatorial space, which consists of permutations, combinations, or subsets.

Brute Force algorithms are known for wide applicability and simplicity in solving complex problems. Searching, string matching, and matrix multiplication are some scenarios where they are used. Single computational tasks can be solved using brute force algorithms. They do not provide efficient algorithms. The algorithms are slow and non-performant. Representation of a brute force algorithm is shown in the following code...

Divide and conquer algorithms

A divide and conquer algorithm breaks a complex problem into smaller problems and solves these smaller problems. The smaller problem will be further broken down till it is a known problem. The approach is to recursively solve the sub-problems and merge the solutions of the sub-problems.

Recursion, quick sort, binary search, fast Fourier transform, and merge sort are good examples of divide and conquer algorithms. Memory is efficiently used with these algorithms. Performance is sometimes an issue in the case of recursion. On multiprocessor machines, these algorithms can be executed on different processors after breaking them down into sub-problems. A divide and conquer algorithm is shown in the following code:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt package
import (
    ...

Backtracking algorithms

A backtracking algorithm solves a problem by constructing the solution incrementally. Multiple options are evaluated, and the algorithm chooses to go to the next component of the solution through recursion. Backtracking can be a chronological type or can traverse the paths, depending on the problem that you are solving.

Backtracking is an algorithm that finds candidate solutions and rejects a candidate on the basis of its feasibility and validity. Backtracking is useful in scenarios such as finding a value in an unordered table. It is faster than a brute force algorithm, which rejects a large number of solutions in an iteration. Constraint satisfaction problems such as parsing, rules engine, knapsack problems, and combinatorial optimization are solved using backtracking.

The following is an example of a backtracking algorithm. The problem is to identify...

Summary

This chapter covered the definition of abstract datatypes, classifying data structures into linear, nonlinear, homogeneous, heterogeneous, and dynamic types. Abstract datatypes such as container, list, set, map, graph, stack, and queue were presented in this chapter. The chapter covered the performance analysis of data structures and structural design patterns.

We looked at the classification of data structures and structural design patterns. You can use algorithms such as brute force, divide and conquer, and backtracking by calculating the complexity and performance analysis. The choice of algorithm and the use of design patterns and data structures are the key takeaways.

In the next chapter, we will discuss data structures in Go. The following data structures will be covered:

• Arrays
• Slices
• Two-dimensional slices
• Maps

...

Questions and exercises

1. Give an example where you can use a composite pattern.
2. For an array of 10 elements with a random set of integers, identify the maximum and minimum. Calculate the complexity of the algorithm.
3. To manage the state of an object, which structural pattern is relevant?
4. A window is sub-classed to add a scroll bar to make it a scrollable window. Which pattern is applied in this scenario?
5. Find the complexity of a binary tree search algorithm.
6. Identify the submatrices of 2x2 in a 3x3 matrix. What is the complexity of the algorithm that you have used?
7. Explain with a scenario the difference between brute force and backtracking algorithms.

8. A rules engine uses backtracking to identify the rules affected by the change. Show an example where backtracking identifies the affected rules.
9. Draw a flow chart for the algorithm of the calculation of profit-loss given the cost...

Further reading

The following books are recommended if you want to find out more about Gang of Four design patterns, algorithms, and data structures:

• Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
• Introduction to Algorithms – Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Data structures and Algorithms: An Easy Introduction, by Rudolph Russell