dansackett/computer-science

A collection of data-structures and algorithms in Golang

Computer Science - Practice and Exploration

This repository will be a place to practice computer science and crytpography principles in Golang. The following items are going to be examined:

Notes

• Asymptotic Notation
• Powers of 2 Reference
• Bit Manipulation

Data Structures

• Linked List
• Binary Search Tree
• Red-Black Tree
• AVL Tree
• Treap
• B-Tree
• Hash Tables
• Matrix
• Heap (Max / Min)
• Trie
• Suffix Array

Abstract Data Types

• Set
• Deque
• Stack
• Queue
• Priority Queue
• Graph (Directed, Undirected)

Graph algorithms

Shortest path:

• Dijkstra
• Floyd–Warshall

Sorting:

• Topological Sort

Searcing:

• Breadth First Search
• Depth First Search

Math algorithms

• Binary GCD algorithm
• Closest pairs
• FastPower
• Fibonacci
• Fisher-Yates Shuffle
• Erastothenes Sieve
• Extented GCD algorithm
• Karatsuba's Multiplication
• Newton's Square Root
• Permutations Count
• Strassen's matrix multiplication
• Randomized Selection

Sorting algorithms

Bad:

• Bubble Sort

Basic:

• Insertion Sort
• Selection Sort
• Shell Sort

Fast:

• Quick Sort
• Merge Sort
• Heap Sort

Other

• Bucket Sort
• Radix Sort

Searching algorithms

• Binary Search
• Linear Search

String Matching

• Knuth-Morris-Pratt
• Rabin-Karp

Common Interview Questions

• Run-length Encoding / Decoding
• Check if string is a substring

Misc

• Recursive Palindromes
• Towers of Hanoi
• Recursive Powers

Design Patterns

• Factory
• Singleton
• Adapter
• Decorator
• Observer
• Iterator
• MVC

Cryptography (Terms)

Symmetric-Key

• Stream Ciphers (RC4, Salsa20, SOSEMANUK, FISH)
• Block Ciphers (AES, DES, Triple DES, Blowfish)

Public Key Cryptography

• RSA Algorithm
• DSA Algorithm

Misc

• Hash Functions (MD5, SHA1, SHA2, HMAC)
• PGP