Algorithms and Data Structures

Algorithms & Data Structures implemented in Java.

To be implemented:

Data Structures

• AVL Tree
• Binary Heap
• Binary Search Tree
• Hash Map (associative array)
• List
• Matrix
• Queue
• Stack
• Trie

Mathematics

• Division
  • using a loop
  • using recursion
  • using shifts and multiplication
  • using only shifts
  • using logarithm
• Multiplication
  • using a loop
  • using recursion
  • using only shifts
  • using logarithms
• Primes
  • is prime

Numbers

• Integers
  • to binary String
    • using divide and modulus
    • using right shift and modulus
    • using BigDecimal
    • using divide and double
  • is a power of 2
    • using a loop
    • using recursion
    • using logarithm
    • using bits
  • greatest common divisor
    • using Euclid's algorithm
  • to English (e.g. 1 would return "one")
• Longs
  • to binary String
    • using divide and modulus
    • using right shift and modulus
    • using BigDecimal

Search

• Get index of value in array
  • Linear
  • Quickselect
  • Binary [sorted array input only]
  • Optimized binary (binary until a threashold then linear) [sorted array input only]

Sequences

• Find longest common subsequence (dynamic programming)
• Find number of times a subsequence occurs in a sequence (dynamic programming)

• Find i-th element in a Fibonacci sequence
  • using a loop
  • using recursion
  • using matrix multiplication
  • using Binet's formula
• Find total of all elements in a sequence
  • using a loop
  • using Triangular numbers

Sorts

• Bubble Sort
• Counting Sort
• Heap Sort
• Insertion Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Radix Sort
• Shell's Sort

String Functions

• Permutations of a string

• Reverse characters in a string
  • using additional storage (a String or StringBuilder)
  • using in-place swaps
  • using in-place XOR
• Reverse words in a string
  • using char swaps and additional storage (a StringBuilder)
  • using StringTokenizer and additional (a String)
  • using split() method and additional storage (a StringBuilder and String[])
  • using in-place swaps
• Is Palindrome
  • using additional storage (a StringBuilder)
  • using in-place symetric element compares

• Subsets of characters in a String
• Edit (Levenshtein) Distance of two Strings

Graphs

• Find shortest path(s) in a Graph from a starting Vertex
  • Dijkstra's algorithm (non-negative weight graphs)
  • Bellman-Ford algorithm (negative and positive weight graphs)
• Find minimum spanning tree
  • Prim's (undirected graphs)
  • Kruskal's (undirected graphs)
• Cycle detection
  • Depth first search while keeping track of visited Vertices

• Topological sort

• Graph Traversal
  • Depth First Traversal
  • Breath First Traversal

Path

• Find shortest path(s) in a Graph from a starting Vertex

• Dijkstra's algorithm (non-negative weight graphs)
• Bellman-Ford algorithm (negative and positive weight graphs)

• Find minimum spanning tree

• Prim's (undirected graphs)

• Find all pairs shortest path

• Johnsons's algorithm (negative and positive weight graphs)
• Floyd-Warshall (negative and positive weight graphs)

• Cycle detection

• Depth first search while keeping track of visited Verticies
• Topological sort
• A* path finding algorithm