shady831213 / algorithms

CLRS study. Codes are written with golang.

algorithms

CLRS study. Codes are written with golang.

---

go version: 1.11

---

• Heap

  • BinaryHeap on array
  • BinaryHeap on linkedlist
  • LeftistHeap
  • FibonacciHeap

• Tree

  • binaryTree
    • BST
    • RedBlackTree
  • B-Tree
  • RS-vEB-Tree(Support single key multi value.Lazy hashtable is used to instead of array to reduce space complexity.Including Go Mixin design pattern)
  • Disjoint-Set-Tree

• Graph (including linkedMap, iterator)

  • graph
  • BFS
  • DFS(use stack)
  • StronglyConnectedComponents
  • BioConnectedComponents(vertex bcc & edge bcc, use stack)
  • eulerCircuit
  • mst(including Kruskal(disjointSet) , Prim(fibonacci heap), secondaryMst, mst reduce for Prim, linear time bottleneck spanning tree)
  • Single-Source Shortest Path (including bellmanFord, SPFA, Dijkstra, Gabow )
  • All-Pairs Shortest Path (including FloydWarshall, Johnson)
  • Max Flow (including flowGraph , preFlowGraph and allowedGraph data structure, Edmondes Karp, Push Relabel, Relabel to Front, Bipartite Graph Max Match and Hopcraft-Karp)

• HashMap(Support UpScale and DownScale)

  • OpenAddressHashMap
  • LinkedListHashMap

• DynamicProgramming (Including OOP pattern of golang)

  • Double adjustable Euclidean traveling salesman
  • Pretty Print
  • Levenshtein Distance
  • Chess Game

• GreedyAlgorithm

  • Minimum average end time scheduling

• Sort

  • CountingSort
  • HeapSort
  • InsertSort
  • MergeSort
  • QuickSort

algorithms's Issues

More sqrts than you can shake a stick at

During your TSP you continually call sqrt while calculating distances. This is fairly wasteful, since you don't actually care about the root until the end of the function.

func dist2(lhs Point, rhs Point) float64 {
  dx, dy := lhs.x - rhs.x, lhs.y - rhs.y
  return (dx*dx) + (dy * dy)
}

func find_closest_2(points []Point) (float64, *Point, *Point, error) {
  if len(points) < 2 {
    return 0, nil, nil, errors.New("must be at least 2 points")
  }
  var first, second *Point
  var shortest_dist float64 = math.MaxFloat64
  for lhs := 0; lhs < len(points) - 1; lhs++ {
    for rhs := lhs + 1; rhs < len(points); rhs++ {
      d2 := dist2(lhs, rhs)
      if d2 < shortest_dist {
        first, second = &lhs, &rhs
        shortest_dist = d2
      }
    }
  }
  return math.sqrt(shortest_dist), first, second, nil
}