ALGORITHM

Algorithms and data structures in Golang

Data Structures

Data Structures are representations of data sets in a way which makes storage and performing of operations of data very easy.

Classification of Data Structures

• Linear

  • List : is an abstract data type that represents a finite number of ordered values, where the same value may occur more than once.
  • Set : is an abstract data type can store unique values without any particular order.
  • Tuple : is a finite ordered list (sequence) of elements. Tuple is a reference type.
  • Queue : is an abstract data type that implements a First-In-First-Out (FIFO) queue of generic items.
  • Stack : is an abstract data type that operates on the concept of the Last-In-First-Out (LIFO) principle.
  • Heap : is a specialized tree-based data structure that satisfies the heap property: for any node, the value of that node is greater than or equal to the values of its children.

• Non - Linear

  • Trees : is a data structure that consists of a set of nested nodes, each node having a value and a set of child nodes.
  • Tables : is a data structure that consists of a set of rows and columns, each row having a set of columns. The table is a two-dimensional array. The table is a reference type.
  • Containers : is a data structure that consists of a set of elements, each element having a key and a value. The container is a reference type. The container is a reference type.

• Homogeneous

  • Two Dimensional Arrays
  • Multi Dimensional Arrays

• Heterogeneous

  • Linked List: is a data structure that consists of a set of nodes, each node having a value and a reference to the next node.
    • Single Linked List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.
    • Double Linked List : is a data structure that consists of a set of nodes, each node having a value and a reference to the previous and next node. The list is a reference type.
    • Circular Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
      • Circular Single Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
      • Circular Double Linked List : is a data structure which has the last item contains link of the first element as next and the first element has a link to the last element as previous. The list is a reference type.
  • Ordered List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.
  • Unordered List : is a data structure that consists of a set of nodes, each node having a value and a reference to the next node. The list is a reference type.

• Dynamic

  • Dictionaries
  • Tree Sets
  • Sequences

Algorithms

Algorithm is a set of instructions that describes how to get something done.

Classification of Algorithms

• SORT

  • Bubble Sort : is a simple sorting algorithm that repeatedly steps through the list, compares elements and swaps them if they are in the wrong order. Bubble Sort has a time complexity of O(n2).
  • Merge Sort : is a comparison based sort that recursively splits the list into smaller sub-lists until the sub-lists are small enough to be sorted individually. Merge Sort was invented by John Von Neumman in 1945. It has a time complexity of O(n log n).
  • Comb Sort : is a sorting algorithm that uses a gap sequence to sort the array. It is a variant of the Bubble Sort algorithm. Comb Sort has a time complexity of O(n2). The algorithm is a variation of the bubble sort algorithm. It was originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980
  • Heap Sort : is a comparison based sort that uses a heap data structure to sort the list. Heap Sort has a time complexity of O(n log n).
  • Quick Sort : is a comparison based sort that uses a divide and conquer strategy to sort the list. Quick Sort has a time complexity of O(n log n).
  • Selection Sort : is a comparison based sort that finds the smallest element in the list and places it at the beginning. Selection Sort has a time complexity of O(n2).
  • Insertion Sort : is a comparison based sort that builds the final sorted array one item at a time. Insertion Sort has a time complexity of O(n2).
  • Radix Sort : is a comparison based sort that sorts the list by grouping the list into buckets. It avoids comparison by creating and distributing elements into buckets according to their radix. Radix Sort has a time complexity of O(n2). uncomplete
  • Bucket Sort
  • Shell Sort
  • Tree Sort
  • Counting Sort
  • Smooth Sort
  • Bogo Sort
  • Cycle Sort
  • Gnome Sort
  • Stooge Sort

• Recursion

  • Fibonacci : is a recursive algorithm that adds the two preceding numbers to produce the next number in the sequence.
  • Factorial : is a recursive algorithm that multiplies all the preceding numbers to produce the next number in the sequence.
  • Euclidean / GCD : is a recursive algorithm that finds the greatest common divisor of two numbers.
  • LCM : is a recursive algorithm that finds the least common multiple of two numbers.
  • Tower of Hanoi : is a recursive algorithm that moves a stack of disks from one tower to another.
  • Ackermann Function : is a recursive algorithm that finds the value of the Ackermann function. It is a total recursive function that can be defined in terms of itself.
  • McCarthy Function : is a recursive algorithm that finds the value of the McCarthy function. It is a total recursive function that can be defined in terms of itself.
  • Palindrome : is an algorithm that checks if a word is equal to its reversed.

• Search

  • Binary Search : is a search algorithm that finds the position of a target value in a sorted array. It has a time complexity of O(log n) and a space complexity of O(1).
  • Interpolation Search : is a search algorithm that finds the position of a target value in a sorted array.
  • Jump to Search : is a search algorithm that finds the position of a target value in a sorted array. It is a variation of the Binary Search algorithm. It has a time complexity of O(log n) and a space complexity of O(1).
  • Linear Search : is a search algorithm that finds the position of a target value in a sorted array. It has a time complexity of O(n) and a space complexity of O(1).
  • Ternary Search : is a search algorithm that finds the position of a target value in a sorted array.
  • Breadth-First Search : is a search algorithm that finds the position of a target value in a graph. It has a time complexity of O(n) and a space complexity of O(n).

• Cipher

  • Caesar Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).
  • Vigenere Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).
  • Hill Cipher : is a cipher that shifts each letter in a message by a certain number of places. It has a time complexity of O(n).uncomplete
  • Rot13 Cipher : is a cipher that shifts each letter in a message by 13 number of places. It has a time complexity of O(n).

• Graph

  • A* Search : is a search algorithm that finds the shortest path between two nodes in a graph. It has a time complexity of O(n) and a space complexity of O(b^d).
  • Dijkstra's Algorithm : is a search algorithm that finds the shortest path between two nodes in a graph. It has a time complexity of O(n) and a space complexity of O(n).