Algorithms and Data Structures

A collection of algorithms and data structures implemented in Go

Algorithms

Sorting

• Elementary sorts
  • Linear sort - O(n)
  • Selection sort - O(n^2)
  • Insertion Sort
  • Shell sort
• Mergesort - O(nlogn)
  • Bottom-up mergesort - O(nlogn)
• Quicksort - O(nlogn)

Searching

• Binary search - O(logn)
• Breadth-first search (BFS) - O(e+v)
• Depth-first search (DFS) - O(e+v)

Greedy

• Interval Scheduling
• Dijkstra's Algorithm
• Kruskal's Algorithm
• Prim's Algorithm

Dynamic Programming (DP)

• Fibonacci Sequence - O(n)
• Kadane's Algorithm - O(n)
• Weighted Interval Scheduling - O(n)
• Knapsack Problem - O(nW)
• Longest Common Substring - O(nm)

Other

• Gale-Shapeley

Data Structures

Fundamental

• Stack
• Queue
• Bag

Tree

• Priority Queue

Graph

• Undirected Graph
• Directed Graph
• Edge-Weighted Graph