Algorithms (with Go)

I wrote about data structures in my previous article. Those are basic abstract data structures that every programmer must know and how to implement them in Go.

There are also operations and algorithms that every programmer must know. An algorithm is a set of instructions designed to perform a specific task. Here, let me show you what operations they are and a few of the basic algorithms.

I updated my article about Big-O Notation. Before getting started, feel free to get to know about the big-O (O) notation. Those notations describe the time and space complexity of an algorithm. It is important to understand the complexity of an algorithm. So, we can optimize it.

Bitwise Operations

I already explained about Bitwise Operations or Bit / Binary Manipulation. I only want to remind it once again here and operate them in Go.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

import (
    "fmt"
)

func main() {
    fmt.Printf("%d = %08b | NOT %d = %d = %08b\n", 7, 7, 7, ^byte(7), ^byte(7))
    fmt.Printf("%d (%08b) & %d (%08b) = %d (%08b)\n", 5, 5, 3, 3, 5&3, 5&3)
    fmt.Printf("%d (%08b) | %d (%08b) = %d (%08b)\n", 5, 5, 3, 3, 5|3, 5|3)
    fmt.Printf("%d (%08b) ^ %d (%08b) = %d (%08b)\n", 5, 5, 3, 3, 5^3, 5^3)
    fmt.Printf("%d = %08b | %d >> %d = %d (%08b)\n", 7, 7, 7, 1, 7>>1, 7>>1)
    fmt.Printf("%d = %08b | %d << %d = %d (%08b)\n", 7, 7, 7, 1, 7<<1, 7<<1)
    fmt.Printf("%d = %08b | %d >> %d = %d (%08b)\n", -105, 256-105, -105, 1, -105>>1, 256+(-105>>1))
    fmt.Printf("%d = %08b | %d << %d = %d (%08b)\n", 23, 23, 23, 1, 23<<1, 23<<1)
}

We have NOT (~) symbol in C, but not in Go. To achieve NOT, we can use XOR (^). We XOR the number to itself.

There is no negative decimal in binary. To achieve a negative decimal, we calculated by 256 minus the number.

Regular Expressions

A regular expression (shortened as regex or regexp) is a sequence of characters that define a search pattern. Maybe you already know that. Here is how we implement it in Go. I brought some examples.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

package main

import (
    "fmt"
    "regexp"
)

func main() {
    re := regexp.MustCompile(`Hell.?`)
    fmt.Printf("%q\n", re.Find([]byte(`Hello World!`)))
    re = regexp.MustCompile(`Hell.?`)
    fmt.Println(re.Match([]byte(`Hello World!`)))
    re = regexp.MustCompile(`Hell.?`)
    fmt.Printf("%s\n", re.ReplaceAll([]byte("Hello World!"), []byte("Hi")))
    re = regexp.MustCompile(` `)
    subs := re.Split("Hello World!", -1)
    fmt.Println(subs)
    for _, s := range subs {
        fmt.Println(s)
    }
}

Take a look at the regexp package for more details.

Sortings

A sorting algorithm is an algorithm that puts elements of a list in a certain order. There are many sorting algorithms. Some of the popular sorting algorithms are Insertion Sort, Selection Sort, Bubble Sort, and Merge Sort. We don't cover any of those sorting algorithms here. But I brought some sorting examples with Go instead.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

package main

import (
    "fmt"
    "sort"
)

type person struct {
    name string
    age  int
}

type byAge []person

// Len ...
func (a byAge) Len() int { return len(a) }

// Less ...
func (a byAge) Less(i, j int) bool { return a[i].age < a[j].age }

// Swap ...
func (a byAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

func main() {
    people := []person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Sort(byAge(people))
    fmt.Println(people)

    sort.Slice(people, func(i, j int) bool {
        return people[i].name < people[j].name
    })
    fmt.Println(people)
}

Take a look at the sort package for more details.

Binary Search

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

package main

import "fmt"

func search(nums []int, target int) int {
    left, right, middle := 0, len(nums)-1, len(nums)/2

    for left <= right {
        switch {
        case nums[middle] == target:
            return middle
        case nums[middle] < target:
            left = middle + 1
        default:
            right = middle - 1
        }

        middle = (right-left)/2 + left
    }

    return -1
}

func main() {
    fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 9))
}

Recursion

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. It has a base state. It minimizes the problem recursively by calling itself. It simplifies the source code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

package main

import "fmt"

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }

    return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
    fmt.Println(fibonacci(7))
}

Dynamic Programming

Dynamic Programming is an optimization to the recursion method. The concept stores the results of subproblems to avoid recomputation and optimizes or reduces the complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package main

import "fmt"

var numbers map[int]int

func fibonacciMemoization(n int) int {
    if numbers[n] != 0 {
        return numbers[n]
    }

    if n <= 2 {
        numbers[n] = 1
    } else {
        numbers[n] = fibonacciMemoization(n-1) + fibonacciMemoization(n-2)
    }

    return numbers[n]
}

func main() {
    numbers = make(map[int]int)
    fmt.Println(fibonacciMemoization(7))
}

Divide and Conquer

The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into subproblems, to solve them in turn, and to compose their solutions to solve the given problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

package main

import "fmt"

func merge(leftNumbers []int, rightNumbers []int) []int {
    left, right, current := 0, 0, 0
    result := make([]int, len(leftNumbers)+len(rightNumbers))

    for left < len(leftNumbers) && right < len(rightNumbers) {
        if leftNumbers[left] < rightNumbers[right] {
            result[current] = leftNumbers[left]
            left++
        } else {
            result[current] = rightNumbers[right]
            right++
        }

        current++
    }

    for left < len(leftNumbers) {
        result[current] = leftNumbers[left]
        current++
        left++
    }

    for right < len(rightNumbers) {
        result[current] = rightNumbers[right]
        current++
        right++
    }

    return result
}

func mergeSort(numbers []int) []int {
    if len(numbers) <= 1 {
        return numbers
    }

    middle := len(numbers) / 2
    left := mergeSort(numbers[:middle])
    right := mergeSort(numbers[middle:])

    return merge(left, right)
}

func main() {
    fmt.Println(mergeSort([]int{5, 2, 3, 1}))
}

Backtracking

Backtracking is a general algorithm for finding solutions to some computational problems, which incrementally builds candidates to the solution and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package main

import "fmt"

func backtrack(result *[][]int, tmp []int, numbers []int) {
    for i := 0; i < len(numbers); i++ {
        start := append([]int{}, numbers[:i]...)
        newNumbers := append(start, numbers[i+1:]...)
        tmp := append(tmp, numbers[i])

        backtrack(result, tmp, newNumbers)
    }

    if len(numbers) == 0 {
        *result = append(*result, tmp)
    }
}

func permutation(numbers []int) [][]int {
    result := [][]int{}

    backtrack(&result, nil, numbers)

    return result
}

func main() {
    fmt.Println(permutation([]int{1, 2, 3}))
}

Closing

In short, I implemented those operations and algorithms in Go. Maybe later I will explain every single algorithm in detail. For now, feel free to visit my references for further explanation, The source code can be found here, https://github.com/aristorinjuang/go-algorithms.

References

Related Articles

Comments

comments powered by Disqus