Algorithms and Data Structures

This project is a java-codebase containing various algorithms, data-structures and other things that are somehow related to the general topic. The project has educational and training purposes.

Chapters:

• classic algorithms - a collection of well-known algorithms and several algorithmic puzzles made in form of junit5-based demonstration system

  content

  • Algorithms for raising a real number to a natural power :

    • Simple iterative algorithm
    • Iterative algorithm with optimization
    • Fast algorithm

  • Fibonacci number calculation:

    • Simple recursive algorithm
    • Simple iterative algorithm
    • Using golden ration
    • Matrix solution

  • Primes number calculation:

    • Iterative algorithm with some optimizations
    • Sieve of Eratosthenes algorithm
    • Sieve of Eratosthenes With Linear Complexity algorithm

  • Greatest common divisor algorithms:

    • Recursive Binary GCD algorithm

  • Sorting algorithms:

    • Bubble sort
    • Insertion sort
    • Selection sort
    • Shell sort
    • Heap sort
    • Quick sort
    • Simple merge sort
    • Radix sort
    • Bucket sort
    • Counting sort
    • External sort

  • String algorithms:

    • Naive full-scan algorithm to search substring
    • Boyer–Moore–Horspool algorithm to search substring
    • Boyer–Moore algorithm to search substring, wiki variant
    • Boyer–Moore algorithm to search substring, ssz variant
    • Knuth-Morris-Pratt algorithm to search substring, naive prefix function
    • Knuth-Morris-Pratt algorithm to search substring, classic prefix function

  • Bitboard algorithms:

    • King walk problem
    • Bishop walk problem
    • Rook walk problem
    • Queen walk problem
    • Knight walk problem

  • Miscellaneous recursion and dynamic programming tasks

    • Happy tickets problem
    • Sum of fractions
    • Pyramid problem: searching the maximum "garland" in the "digital christmas tree"
    • Counting two-digit numbers with exclusion of three consecutive digits series ("5x8 problem")
    • Matrix islands: find all 1-digit islands from square matrix consisting of 0 and 1
    • Calculation the maximum possible shed area on a fixed rectangular area with some obstacles
      • A brute-force solution with O(N^4) complexity
      • An optimized solution with O(N^3) complexity
      • An optimal solution with O(N^2) complexity

• data structures - a collection of different data-structures with JMH-based demonstration.

  content

  • Dynamic Arrays:

    • A naive one-item-a-time-grown implementation
    • An implementation with fixed growth-factor (so called "vector")
    • An implementation with dynamic growth-factor
    • A matrix-based dynamic array
    • A wrapper for JDK java.util.List implementations

  • Priority Queues:

    • A priority heap based implementation (wrapper for java.util.PriorityQueue)
    • A java.util.TreeSet-based implementation
    • A java.util.Map-based implementation

  • Maps (Key-Value Dictionaries):

    • Trees:
      • Simple Binary Search Tree Map implementation without any rebalance
      • AVL Binary Search Tree Map implementation
      • Treap - a Cartesian Binary Search Tree Map implementation
      • B-Tree - a self-balancing multi-node Search Tree Map implementation
    • Hash-tables:
      • A hashtable separate-chaining implementation
      • A hashtable open-addressing implementation
    • Wrappers to compare:
      • Simple wrapper for JDK java.util.Map implementations
      • A wrapper for java.util.Map with Bloom-Filter optimization

  • Misc data-structures: Bloom Filter:

    • Simplest Bloom Filter impl
    • Guava-based wrapper

  • Graph algorithms

    • Demucron's algorithm (topological sorting)
    • Kosaraju's algorithm (strongly connected component searching)
    • Borůvka's algorithm (optimized Kruskal's algorithm, a searching of minimum spanning tree)
    • Dijkstra's algorithm (an algorithm for finding the shortest paths in weighted graph)

• data compression algorithms - a simple command-line utility to encode/decode files using different approaches.

  content

  • Standard JDK's Zip compressor
  • Standard JDK's GZip compressor
  • Apache Commons Zip compressor
  • Apache Commons SevenZip compressor
  • Naive RLE compressor
  • Optimized RLE compressor

• algorithmic puzzles - another attempt to systematize puzzles for coding interviews

Requirements:

• Git
• Java 11+
• Maven 3+