Algorithms

An implementation of various Algorithms in Java, based on the book Algorithms by Sedgewick and Wayne.

I wrote the code as I followed Sedgewick's Algorithms course, and tried to understand the various algorithms. I wanted to make the implementation clear, readable and easy to understand. I believe it's correct, but since it was my first time learning about these algorithms, so I don't guarantee that the code is bug free.

Data Structures

• HashMap
• HashSet
• Doubly-Linked List
• Bag
• Queue
• Stack
• Resizing Array Queue
• Resizing Array Stack
• MinStack
• Minimum Priority Queue

Cool Application

• Median Maintenance: keeps track of the median of a variable sequence of elements, supporting insertions

Sorting

• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort

String sorting:

• Least Significant Character Sort

Neat adaptation of quicksort

• Quick Select: efficiently find's the i-th smallest element in an unsorted array

Trees

• Binary Search Tree

Graphs

Data Structures

• Undirected Graph
• Directed Graph
• Edge Weighted Undirected Graph
• Edge Weighted Directed Graph

Algorithms

• Find the topological order
• Find cycle (if it exists)
• Find the connected components
• Depth First Search graph orderings: Post Order and Pre Order
• Depth First Search
• Find the Minimum Spanning Tree
  • Kruskal Algorithm
  • Lazy Prim Algorithm
  • Eager Prim Algorithm
• Find the shortest path from A to B:
  • Breadth First Search
  • Dijkstra's Algorithm: cannot always handle negative weights correctly
  • Bellman-Ford Algorithm: always handle negative weights correctly
  • A* Algorithm: you need to add your appropriate heuristic for your problem

Great applications:

• Union Find
• Six Degrees from Kevin Bacon

Searching

• Binary Search

Useful classes

• Stop Watch
• Statistics: computes the mean, median, mode, size and sum of an array of numbers