bonaert / algorithms

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

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