Algorithms

This respository is a collection of various useful algorithms and data structures along with their Java implementations, intended for educational use. This is a work in progress, so some algorithms may not be included. All files that have been added have been tested extensively and should be accurate, readable, and efficient. Feel free to suggest any algorithms that you'd like to see implemented in the future. Don't hesitate to contact me with any questions, concerns, or feedback (my contact information is at the bottom of this file). If you found this repository helpful, I'd love to know :)

Table of Contents

• Algorithms
  • Graph
  • Dynamic Programming
  • Sorting
  • Searching
  • Strings
  • Math
  • Computational Geometry
  • Optimization
  • Miscellaneous
  • Data Structures
  • Project Euler
  • Google Code Jam
  • USACO
• Resources
  • Books
  • Websites
  • Courses
  • Online Judges
  • Github Libraries

Graph

• Graph Traversal
  • Breadth-First Search
  • Depth First Search
• Shortest Path
  • Dijkstra's Algorithm
  • Bellman-Ford
  • Floyd-Warshall
  • Johnson's Algorithm
• Minimum Spanning Tree
  • Kruskal's Algorithm
  • Prim's Algorithm
• Network Flow
  • Karger's Algorithm
  • Push-Relabel
  • Edmonds-Karp
  • Ford-Fulkerson
• Tarjan's Algorithm
• Topological Sort
• Strongly Connected Components

Dynamic Programming

• 0-1 Knapsack
• Edit (Levenshtein) Distance
• Longest Increasing Subsequence
• Longest Common Subsequence
• Maximum Subset Sum

Sorting

• Timsort
• Radix Sort
• Counting Sort
• Quicksort
• Heapsort
• Mergesort
• Insertion Sort
• Bubble Sort
• Selection Sort
• Bogosort

Searching

• Linear
• Binary
• ith Order Statistic
  • Sort Select
  • Randomized Select
  • Heapselect
  • Quickselect

Strings

• String Searching
  • Aho-Corasick
  • Z Algorithm
  • Knuth-Morris-Pratt
  • Boyer-Moore
  • Rabin-Karp
  • Brute Force

Math/Number Theory

• Fibonacci
  • Binet's Formula
  • Iterative
  • Recursive (DP)
  • Matrix Exponentiation
  • Fast Doubling
• Euclid's Algorithm
• Fast Fourier Transform
• Primality Testing
  • Naive
  • Sieve of Erastothenes
  • Miller-Rabin
• Karatsuba's Algorithm
• Fast Exponentiation
• Strassen's Algorithm

Computational Geometry

• Convex Hull
  • Graham Scan
  • Jarvis March

Optimization

• Naive Optimization
• Simplex (LP)
• Simulated Annealing
• Genetic Algorithms
• Combinatoric Algorithms

Miscellaneous

• Fisher-Yates Shuffle
• Kadane's Algorithm
• Subarray Inversions

Data Structures

• Graph
• Tree
• Binary Tree
• Fenwick Tree (Binary Indexed Tree)
• Red-Black Tree
• AVL Tree
• B-Tree
• Suffix Tree
• Trie
• Hash Table
• Hash Map
• Stack
• Queue
• List
• LinkedList

Project Euler

Interesting math problems that can be solved computationally; full problem set available here. The Project Euler folder contains the full inventory of problems I've implemented with it's own table of contents here.

Google Code Jam

Competitive programming style problems from previous competitions. The Google Code Jam folder contains the full inventory of problems I've implemented with it's own table of contents here.

USACO

Algorithmic problems from past USA Computing Olympiad contests, check out the full problem database. The USACO folder contains the full inventory of problems I've implemented with it's own table of contents here.

Developed By

• Joel P. Abraham - [email protected]