Skip to content

aramceballos/Go

BranchesTags
 
 

Repository files navigation

The Algorithms - Go

Gitpod Ready-to-Code  Continuous Integration codecov godocmd   update_directory_md Discord chat 

Algorithms implemented in Go (for education)

The repository is a collection of open-source implementation of a variety of algorithms implemented in Go and licensed under MIT License.

Read our Contribution Guidelines before you contribute.

List of Algorithms

Packages:

ahocorasick
Functions:
  1. Advanced: Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  2. AhoCorasick: AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  3. ArrayUnion: ArrayUnion Concats two arrays of int's into one.
  4. BoolArrayCapUp: BoolArrayCapUp Dynamically increases an array size of bool's by 1.
  5. BuildAc: Functions that builds Aho Corasick automaton.
  6. BuildExtendedAc: BuildExtendedAc Functions that builds extended Aho Corasick automaton.
  7. ComputeAlphabet: ComputeAlphabet Function that returns string of all the possible characters in given patterns.
  8. ConstructTrie: ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings.
  9. Contains: Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise.
  10. CreateNewState: CreateNewState Automaton function for creating a new state 'state'.
  11. CreateTransition: CreateTransition Creates a transition for function σ(state,letter) = end.
  12. GetParent: GetParent Function that finds the first previous state of a state and returns it. Used for trie where there is only one parent.
  13. GetTransition: GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none.
  14. GetWord: GetWord Function that returns word found in text 't' at position range 'begin' to 'end'.
  15. IntArrayCapUp: IntArrayCapUp Dynamically increases an array size of int's by 1.
  16. StateExists: StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise.
Types
  1. Result: No description provided.
armstrong
Functions:
  1. IsArmstrong: No description provided.
binary
Package binary describes algorithms that use binary operations for different calculations.
Functions:
  1. Abs: Abs returns absolute value using binary operation Principle of operation: 1) Get the mask by right shift by the base 2) Base is the size of an integer variable in bits, for example, for int32 it will be 32, for int64 it will be 64 3) For negative numbers, above step sets mask as 1 1 1 1 1 1 1 1 and 0 0 0 0 0 0 0 0 for positive numbers. 4) Add the mask to the given number. 5) XOR of mask + n and mask gives the absolute value.
  2. BitCounter: BitCounter - The function returns the number of set bits for an unsigned integer number
  3. FastInverseSqrt: FastInverseSqrt assumes that argument is always positive, and it does not deal with negative numbers. The "magic" number 0x5f3759df is hex for 1597463007 in decimals. The math.Float32bits is alias to *(*uint32)(unsafe.Pointer(&f)) and math.Float32frombits is to *(*float32)(unsafe.Pointer(&b)).
  4. IsPowerOfTwo: IsPowerOfTwo This function uses the fact that powers of 2 are represented like 10...0 in binary, and numbers one less than the power of 2 are represented like 11...1. Therefore, using the and function: 10...0 & 01...1 00...0 -> 0 This is also true for 0, which is not a power of 2, for which we have to add and extra condition.
  5. IsPowerOfTwoLeftShift: IsPowerOfTwoLeftShift This function takes advantage of the fact that left shifting a number by 1 is equivalent to multiplying by 2. For example, binary 00000001 when shifted by 3 becomes 00001000, which in decimal system is 8 or = 2 * 2 * 2
  6. LogBase2: LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) See more
  7. MeanUsingAndXor: MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operations
  8. MeanUsingRightShift: MeanUsingRightShift This function finds arithmetic mean using right shift
  9. ReverseBits: ReverseBits This function initialized the result by 0 (all bits 0) and process the given number starting from its least significant bit. If the current bit is 1, set the corresponding most significant bit in the result and finally move on to the next bit in the input number. Repeat this till all its bits are processed.
  10. SequenceGrayCode: SequenceGrayCode The function generates an "Gray code" sequence of length n
  11. Sqrt: No description provided.
  12. XorSearchMissingNumber: XorSearchMissingNumber This function finds a missing number in a sequence
cache
Functions:
  1. NewLRU: NewLRU represent initiate lru cache with capacity
  2. NewLFU: NewLFU represent initiate lfu cache with capacity
  3. Get: Get the value by key from LFU cache
  4. Put: Put the key and value in LFU cache
Types
  1. LRU: Default the struct of lru cache algorithm.
  2. LFU: Default the struct of lfu cache algorithm.
caesar
Package caesar is the shift cipher ref: https://en.wikipedia.org/wiki/Caesar_cipher
Functions:
  1. Decrypt: Decrypt decrypts by left shift of "key" each character of "input"
  2. Encrypt: Encrypt encrypts by right shift of "key" each character of "input"
  3. FuzzCaesar: No description provided.
catalan
Functions:
  1. CatalanNumber: CatalanNumber This function returns the nth Catalan number
checksum
Package checksum describes algorithms for finding various checksums
Functions:
  1. CRC8: CRC8 calculates CRC8 checksum of the given data.
  2. Luhn: Luhn validates the provided data using the Luhn algorithm.
Types
  1. CRCModel: No description provided.
coloring
Package coloring provides implementation of different graph coloring algorithms, e.g. coloring using BFS, using Backtracking, using greedy approach. Author(s): Shivam
Functions:
  1. BipartiteCheck: basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartite
Types
  1. Graph: No description provided.
combination
Package combination ...
Functions: