DataStructuresAndAlgorithms

This is a collection of algorithms and data structures which I've implemented from scratch as well as using inbuilt libraries in Java along with some famous Dynamic Programming Problems.

You can run and edit the algorithms or contribute to them using Gitpod.io, a free online development environment, with a single click.

Contributing

1. Fork it!
2. Create your feature branch: git checkout -b my-new-feature
3. Commit your changes: git commit -am 'Add some feature'
4. Push to the branch: git push origin my-new-feature
5. Submit a pull request 😄

What's been implemented:

Data Structures

• Lists
  • Arraylists
  • Singly LinkedList
  • Doubly LinkedList
  • JDK LinkedList
• Stacks
  • Array Implementation
  • LinkedList Implementation
• Queues
  • Array Implementation
  • Circular Queues
• Hashtable
  • Hashtable with Chaining
  • Hashtable with Linear Probing
  • JDK Hashtable
• Trees
  • Binary Search Trees
• Heaps
  • Max Heap
  • JDK Priority Queue

Sorts

• Bubble Sort
• Bucket Sort
• Heap Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Selection Sort
• Shell Sort

Algorithms

• Graphs

  • Graph Traversal
    • Breadth First Search
    • Depth First Seach
    • Bipartite Graph
  • Cycle detection
    • Depth first search while keeping track of visited Verticies
  • Find shortest path in a Graph from a starting Vertex
    • Dijkstra's algorithm (non-negative weight graphs)
    • DAG Shortest Path
    • Bellman-Ford algorithm (negative and positive weight graphs)
  • Topological sort
  • Find minimum spanning tree
    • Kruskal's (undirected graphs)
    • Prim's (undirected graphs)
  • Find Strongly Connected Components
    • Kosaraju's Algorithm
    • Tarjan's Algorithm
  • Maximum Flow
    • Ford Fulkerson's Algorithm
    • Minimum s-t cut in Flow Network
  • Hard Problems
    • Travelling Salesman Problem (Naive Approach)

• Searching

  • Linear Search
  • Binary Search

Dynamic Programming

• Boolean Parenthesization
• Box Stacking
• Coin Change
• Count Binary Strings Without Adjacent Ones
• Edit Distance
• Egg Dropping Puzzle
• Knapsack Problem
• Knight Probability in Chess board
• Longest Bitonic Subsequence
• Longest Common Subsequence
• Longest Increasing Subsequence
• Longest Palindromic Subsequence
• Matrix Chain Multiplication
• Maximum Length Chain Pairs
• Maximum Sum Increasing Subsequence
• Minimum Jumps to reach End
• Minimum Path Sum
• Optimal Game Strategy
• Pattern Matching
• Shortest Common Supersequence