arnauddri / algorithms Goto Github PK

Hello

I would be thankful a lot if you could add Yen's KSP to the Graphs algorithms. In general, it uses Dijkstra to find k-shortest paths and is crucial, when you need to get multiple weighted shortest paths contrary to one shortest path.

There are just a few implementations of it:
https://github.com/Pent00/YenKSP in Python
https://code.google.com/p/k-shortest-paths/ in C++/Java/C#

Having this one implemented would be a radical improvement comparing to other algorithm library implementations.

On another hand, I would be very curious to hear about other implementations, like Eppstein or Lawler

line 150:
result := MakeMatrix(make([]float64, A.cols*A.rows), A.cols, A.rows)

maybe change to:
result := MakeMatrix(make([]float64, A.cols*A.rows), A.rows, .cols)

the order of the params in not right ??? :)

Problem

The RSelect method is not returning the correct k-smallest element.

Here is an example:

arr := []int{5, 2, 6, 8, 3, 1}
x := RSelect(arr, 6, 0)

fmt.Println("Value: ", x)

The printed value is 5, when it should be 1.

Test

The test implemented for RSelect is running successfully, showing that it was implemented incorrectly.

There is an error in the applied boolean logic. The test is using && to validate the returned values, when it should be using ||.

Here is the correct test implementation:

func TestRSelect(t *testing.T) {
	arr := []int{5, 2, 6, 8, 3, 1}

	i0 := RSelect(arr, 6, 0)
	i1 := RSelect(arr, 6, 1)
	i2 := RSelect(arr, 6, 2)
	i3 := RSelect(arr, 6, 3)
	i4 := RSelect(arr, 6, 4)
	i5 := RSelect(arr, 6, 5)
	if i0 != 1 ||
		i1 != 2 ||
		i2 != 3 ||
		i3 != 5 ||
		i4 != 6 ||
		i5 != 8 {
		fmt.Println("Error: ", i0, i1, i2, i3, i4, i5)
		t.Error()
	}
}

I want to see how Treap is implemented in Go.

Hi,
I suggest implement resize in hash-table.
Like this:
https://github.com/shady831213/algorithms/blob/master/hashMap/chainedHashMap/chainedHashMap.go
https://github.com/shady831213/algorithms/blob/master/hashMap/chainedHashMap/chainedHashMap_test.go
:)

}

func (A *Matrix) add(B *Matrix) error {

• if A.cols != B.cols && A.rows != B.rows {
• if A.cols != B.cols || A.rows != B.rows {
  return errors.New("Wrong input sizes")
  }
  for i := 0; i < A.rows; i++ {
  @@ -102,7 +102,7 @@ func (A *Matrix) add(B *Matrix) error {
  }

func (A *Matrix) substract(B *Matrix) error {

• if A.cols != B.cols && A.rows != B.rows {
• if A.cols != B.cols || A.rows != B.rows {
  return errors.New("Wrong input sizes")
  }
  for i := 0; i < A.rows; i++ {

it would be nice to have PreOrder, InOrder, and PostOrder traversal methods that return nodes in the desired order in an array or slice. I guess my friend and I can work this out.

I think it should be

if parent.Left == h

n is never gonna equal to parent.Left right?, they don't have the same address. We only use n pass to function Compare to determine which way should we go in the tree.

I think this should be if l.Len() == index {
https://github.com/arnauddri/algorithms/blob/master/data-structures/linked-list/linked_list.go#L82

should be (i-1) >> 1
https://github.com/arnauddri/algorithms/blob/master/data-structures/heap/heap.go#L81