prakhar1989 / algorithms Goto Github PK

The "tests/edges.txt" file is missing for "graph_algorithms_test.py"

Hi I want to contribute to this project by adding some python algorithme.This is my first contribution so let me know if I did something wrong!

The Queue implementation, as it currently stands uses a list and then does a self.items.insert(0, item) to insert an item in the Queue.
This is inefficient. A better approach is to modify Queue to use a deque under the hood, instead of a list for increased efficiency.
Please let me know if you agree with the above approach so that I can send a pull request with the appropriate changes.

Adding fractional knapsack .

I would like to implement bubble sort in sorting and basics, could you assign the issue for me?

@prakhar1989
Is bubblesort in sorting.py actually bubble sort?
The code gives correct end result but according to standard bubblesort, for each iteration the largest element is moved to n-1th index

for i in range(len(a)):
        for j in range(i, len(a)):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]
        print a  # print array after each iteration

The result of this for a=[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

[1, 10, 9, 8, 6, 4, 2]  # element 10 is not moved to last index
[1, 2, 10, 9, 8, 6, 4]
[1, 2, 4, 10, 9, 8, 6]
[1, 2, 4, 6, 10, 9, 8]
[1, 2, 4, 6, 8, 10, 9]
[1, 2, 4, 6, 8, 9, 10]
[1, 2, 4, 6, 8, 9, 10]

# gives the desired result
for i in range(len(a)-1):
        for j in range(0, len(a)-1-i):
                    if a[j+1] < a[j]:
                            a[j+1], a[j] = a[j], a[j+1]
        print a

I'm getting this error:

  File "test.py", line 42
    print dijkstra (graph, 1)
                 ^
SyntaxError: invalid syntax

when I use this code

from heapq import heappush, heappop
graph = {
    's' : {'t':6, 'y':7},
    't' : {'x':5, 'z':4, 'y':8 },
    'y' : {'z':9, 'x':3},
    'z' : {'x':7, 's': 2},
    'x' : {'t':2}
}

def read_graph(file):
    graph = dict()
    with open(file) as f:
        for l in f:
            (u, v, w) = l.split()
            if int(u) not in graph:
                graph[int(u)] = dict()
            graph[int(u)][int(v)] = int(w)
    return graph

inf = float('inf')
def dijkstra(graph, s):
    n = len(graph.keys())
    dist = dict()
    Q = list()

    for v in graph:
        dist[v] = inf
    dist[s] = 0

    heappush(Q, (dist[s], s))

    while Q:
        d, u = heappop(Q)
        if d < dist[u]:
            dist[u] = d
        for v in graph[u]:
            if dist[v] > dist[u] + graph[u][v]:
                dist[v] = dist[u] + graph[u][v]
                heappush(Q, (dist[v], v))
    return dist

print dijkstra(graph, 1)

All I did was omit the read file line and uncomment the graph.

In the longest sequence code, the algorithms fails for this test

seq = [5,0,1,2,3,4,5,6,7,8,9,10,11,12, 2, 8, 10, 3, 6, 9, 7]

The output is (13, [0, 1, 2, 3, 4, 5, 6, 7]), when there is clearly a longer sequence.

Just to let you know!

Is get_max_spacing getting the min space in the code?

a = BinarySearchTree()
a.insert(12)
a.insert(1)
a.insert(10)

raises error

Traceback (most recent call last):
  File "binarysearchtree.py", line 147, in <module>
    a.insert(1)
  File "binarysearchtree.py", line 109, in insert
    if node.value == value:
AttributeError: 'NoneType' object has no attribute 'value'