msambol / dsa Goto Github PK

👋 hello, thanks for this repo with the code -- I watched your videos many years ago when I was teaching myself how to code, going to UNL's libraries on the daily (I see you are a fellow Nebraskan as well).

I was reading through the code and found some discrepancies in how visited sets are represented, which could be shored up to make the code easier to follow:

1. This code uses a dictionary of node -> bool, when a set works fine.
   https://github.com/msambol/dsa/blob/master/shortest_path/dijkstras.py#L21C1-L29C26

If this code initialized an empty visited set, the line of visited[node] = False in the graph iteration could be removed.

2. This code uses an array which has O(n) access to check for visited, which makes the dfs algorithm O(n^2) instead of O(n)
   https://github.com/msambol/dsa/blob/master/search/depth_first_search.py#L18C1-L29C32

(There is a note in another part of the code that changes a list to a queue to improve time complexity, so I assume this change is in scope).
https://github.com/msambol/dsa/blob/master/search/breadth_first_search.py#L19C1-L21C20

3. This code uses a list for visited, which is probably faster than the set in this case but is another representation of a set:
   https://github.com/msambol/dsa/blob/master/maximum_flow/ford_fulkerson.py#L21C1-L21C31

Hi Mr Sambol, i just wanna say thanks to you 'cause your videos and codes help me a looooot! Appreciate!

https://github.com/msambol/dsa/blob/5579be5aff4fc005bfe6c108d2e4c2afc6ad7945/trees/b_tree.py#L46C3-L46C3
So the issue is in the lines 45-46. If y is not a leaf, we reassign y's children to y & z. We can max have 2*t children, in this case 6. Using lines 45-46, we reassign only 1,2,4,5,6 children, missing the third child due to a logic error. To prevent it, we must simply do (y.children = y.children[0: t]), unstead of (y.children = y.children[0: t - 1]), so the third child is not missing. To test that, I used Your delete example, but after all the deletions, inserted 26. With the old wersion of the code, before inserting 26, we had 18 values in our tree, after inserting 26 we have only 17 values, as 2 of them are missing, which are values 32 and 39. Using the fixed version of line 46, the code seems to be working properly, having 19 values after inserting and not missing any node.

Hi Michael,

Just studying BubbleSort and I think you might have made a mistake in your pseudo code.
In BubbleSort, you're supposed to bubble up to the most currently sorted index, whereas it seems you're iterating to the end of the loop each time.

Your current code runs as such;

for i in range(n-1):
    for j in range(n-1):
         if list[j] > list[j+1]: 
             tmp = list[j]
             list[j] = list[j+1]
             list[j+1] = tmp

    return list

Whereas, I believe it's supposed to run as the following; (where i cuts it off from iterating further)

for i in range(n-1):
    for j in range(n-i-1):
         if list[j] > list[j+1]: 
             tmp = list[j]
             list[j] = list[j+1]
             list[j+1] = tmp

    return list

Cheers,
Nathan

def delete_example():
first_leaf = Node(True)
first_leaf.keys = [1, 3,4]

second_leaf = Node(True)
second_leaf.keys = [7, 8, 14]

third_leaf = Node(True)
third_leaf.keys = [16, 17, 19]

fourth_leaf = Node(True)
fourth_leaf.keys = [26, 27, 28]

fifth_leaf = Node(True)
fifth_leaf.keys = [30,35]

sixth_leaf = Node(True)
sixth_leaf.keys = [42, 43]

seventh_leaf = Node(True)
seventh_leaf.keys = [51, 52,53]

eighth_leaf = Node(True)
eighth_leaf.keys = [65,67,68]

root_left_child = Node()
root_left_child.keys = [5,15,20]
root_left_child.children.append(first_leaf)
root_left_child.children.append(second_leaf)
root_left_child.children.append(third_leaf)
root_left_child.children.append(fourth_leaf)

root_right_child = Node()
root_right_child.keys = [40, 50,60]
root_right_child.children.append(fifth_leaf)
root_right_child.children.append(sixth_leaf)
root_right_child.children.append(seventh_leaf)
root_right_child.children.append(eighth_leaf)


root = Node()
root.keys = [29]
root.children.append(root_left_child)
root.children.append(root_right_child)

B = BTree(2)
B.root = root
print('\n--- Original B-Tree ---\n')
B.print_tree(B.root)

print('\n--- Case 1: DELETED 29 ---\n')
B.delete(B.root, 29)
B.print_tree(B.root)

if we use this delete example function when i try to delete the root it has none on level 0 and i am confused.

also during the line 142 and 147 , we should have individual calls to the delete predecessor , we should have a call at index n+1.

also in case in delete predecessor if the n th children doesnt have t keys then we merge but what if the n+1 th child has 2t-1 keys then , i am confused what will happen..

IF you could please help me resolve my doubt...

also i am confused if the delete_predecessor call at 145 should be a part of return statement.

near the end of the file it looks to me like you invoke dijkstras twice and print the results instead of invoking dijkstras and dijkstras_heap once each.