Fixed by checking input keys as follows:

1. Raise TypeError if the key is not an instance of str
2. Raise a ValueError if the key is empty
3. Raise a TypeError if value is none

• Changed name of run.sh to automate.sh
• Added tests for Queue
• Changed a few other things around
• Removed queue for BFS, because it’s quite useless
• Removed (temporarily) MinPrioriotyQueue

I've just noticed that method search_by_value in the class Heap raises a ValueError if the input val is None.

The problem is that theoretically it's possible to add a HeapNode to the heap (either max, min or min-max) with a value None using the add method defined in the Heap class. In that same class, if the input is already a HeapNode, no further checks are performed.

Two possible solutions:

1. Allow HeapNode objects with None values to be added to the Heap.
2. Make sure that HeapNode objects with None values are not added to the heap by modifying the add method.

Note: the tests have not caught this bug!

I had already implemented BFS and DFS, even though currently they were removed temporarily from this project, since the graph data structure was also removed (because I'd to fix a few things with it), but I would like to add also other algorithms like:

• Uniform-cost search (also called cheapest-first search)

  • This is a variant of the famous Dijkstra's algorithm, where instead of starting with a queue full of nodes, it starts only with one item, and inserts new items as they are discovered. This can avoid some "decrease-key" operations.

  • Dijkstra's algorithm finds the shortest path between a source node and all nodes in a graph, whereas UCS only finds the shortest path between a source and a destination node.

• Depth-limited search

  • http://www.cs.colostate.edu/~anderson/cs440/index.html/doku.php?id=notes:week2b

• Bidirectional search

• Iterative-deepening (depth-first) search

• Best-first search

  These algorithms are usually used in path finding in combinatorial search. There's also a particular version of best-first search, i.e. a greedy version, where paths that are predicted to be closer are chosen first.

• Beam search

• A* (not a greedy version of a best-first search)

  • A (A* without admissible heuristics)

• IDA* (or iterative-deepening A*)

• Alpha-Beta pruning

Local search

• Hill climbing

• 2-opt, 2.5-opt, 3-opt, Lin–Kernighan, etc.

Interesting articles

• Iterative deepening vs depth-first search

Possibly useful resources

• Chapter 3.5 of Russell and Norvig.
• Slides of prof. Gambardella

The following methods do not check if the key is an instance of an Hashable

• [x] get
• [x] put

whereas the following do

• delete

Note: update tests to reflect changes.

For example, in the class LinearProbingHashTable, I have defined a method called __invariants, whose purpose is to check that the preconditions, postconditions and invariants of the data structure or methods of the same are maintained. This method could be defined as an external function, like I'm already doing for heaps and binary search trees.

Another example where there's this problem is in the TST class. I may also want to add a similar function to DisjointSetsForest.

When I was running all tests locally, using the script ./run_tests.sh, at a certain point, an assertion (i.e. assert is_min_max_heap(self)) in the deletion operation was not satisfied. This only occurred locally and when I run all tests, apparently.

In general, there was some strange behavior going on.

Verify that the algorithm for deleting an element from a MinMaxHeap (and also MaxHeap and MinHeap) really work, but thinking about all possible cases!!!

In some data structures, size is a property (e.g. DisjointSetsForest), and in others size is a method (e.g. BinaryHeap). Need to fix these inconsistencies.

For consistency, I should assert in all methods that accept "indices" that they are valid, i.e. by using something of the form assert self.is_good_index(my_index). Examples of functions that do not do that: _index_of_max, _index_of_min, etc.

Mare sure that this assertion is required in certain methods: it may happen that it's "ok" that in a call or recursive sub-call to a function the indices are no more valid!!!

Check also the cases for BinaryHeap, MinHeap and MaxHeap.

For example, push_down should be a private method, but its name does not start with _.

Be careful: decide well which methods are part of the public API of these heap classes. To do that, you may need to think why would you use a heap.

Currently, it seems that the implementation of DSForests assumes that the user knows about DSNode and thus can access its public fields. Is this a good thing in this case? My first intuition is that the user doesn't care about these implementations details and therefore they should be hidden. Note: if that's the case, we may need also to change the interface of certain methods, e.g. find, which instead of returning DSNode would return the original value stored in the corresponding representative.

For example, Kruskal's MST algorithm uses DSForests, but doesn't really care about implementation details, it only cares about the main functionalities and advantages that DSForests uses:

1. Find if two elements belong to the same set in amortized constant time
2. The nature of the DS, i.e. that you have a forest of disjoint sets and you can union them.

We have e.g. multiple heaps, multiple trees or multiple classes/modules related to hash tables, so it may be a good idea to place them inside a subpackage

If I type only make, I get

Poetry does not seem to be installed, but it's required. Please, install it. See https://python-poetry.org/
make: *** [poetry_check] Error 1

However, I think it would be better to just show the help message.