bradfield / algos Goto Github PK

Let's decide on a grammatical person and stick with it.

The unordered list section appears to not be rendering for some reason. It should also be in litpy with test coverage.

The index page seems to be fine, but if I move to the next chapter, it cuts off prematurely after a code example:

In the parse tree example, only expressions with single-digit integers are permitted. This is not made clear, so the example just breaks confusingly if tried with multi-digit numbers. It may be straightforward to modify the example to enable multi-digit numbers, without complicating the tokenization logic too much.

Thanks for sharing this amazing work.

I feel like the algorithm in Shortest Path with Dijkstra’s Algorithm is not correct.
Since heapq won't update(sort) automatically after you update the value.

For example,
if I rename 'Z' to be 'A', it will first pop 'X' and then pop 'Z'. However, the distance to Z now is infinite. In this case it will work, but if we add another node 'B" which the shortest path from 'X' to 'B' is 'X' -> 'Z' -> 'B', then this algorithm won't work out.

example_graph = {
    'B': {'A': 9},
    'U': {'V': 2, 'W': 5, 'X': 1},
    'V': {'U': 2, 'X': 2, 'W': 3},
    'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'A': 5},
    'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
    'Y': {'X': 1, 'W': 1, 'A': 1},
    'A': {'W': 5, 'Y': 1, 'B':9}
}
# calculate_distances(example_graph, 'X')
# => {'A': 2, 'B': inf, 'U': 1, 'V': 2, 'W': 2, 'X': 0, 'Y': 1}

From #34

In "Shortest Path with Dijkstra’s Algorithm", the implementation used "entry_lookup[neighbor][0] = distance" to change entry value in heap.

This will not work because heap will not reorganize after this modification. One correct way to reorganize this heap is using heapq._siftdown function. You can find some reference here.

Throughout the book, we should consistently consider a "section" to be a child of a "chapter". This is not currently the case.

Clicking on the "Introduction" link takes you to http://bradfield.institute instead of http://bradfield.institute/algos/analysis/introduction/.

Readers should be able to switch between languages when reading a section of the book. The language switcher should determine which languages are available for a given section and present these options to the reader. The reader's latest choice should be remembered and considered the default.

For instance, in analysis/introduction:

Currently this section is in "draft" because the code appears to be incorrect. We should fix and publish it.

From #30 (comment)

It is currently a little confusing, and doesn't seem to be fully reflected in the code samples.

Currently in the binary search tree example, handling of duplicate keys is left as "an exercise for the reader", however it may be possible to just fix the code sample, to minimize confusion.

This will allow us to add test coverage to JavaScript code samples

Perhaps in the introduction, we should have a section which:

1. References the original "Problem Solving with Algorithms and Data Structures Using Python" book and credits Brad Miller and David Ranum
2. Notes that the book is Creative Commons
3. Provides some guidance on how to report issues and make contributions
4. Lists the current contributors
5. Mentions and links to Bradfield

Currently, almost all figures have a caption. This is a vestige of the original book; most of the captions add little value so should just be removed.

It may be useful to add a section to each chapter with corresponding exercises.

I have a feeling that the representation of an empty linked list shown here is wrong.

When declaring empty Unordered List with the definition given here: https://bradfieldcs.com/algos/lists/implementing-an-unordered-list/#the-unordered-list-class

class UnorderedList(object):

    def __init__(self):
        self.head = None

along with the definition of Node here:
https://bradfieldcs.com/algos/lists/implementing-an-unordered-list/#the-node-class

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None

Declaring an UnorderedList, like so:

my list = UnorderedList()

The image seems to indicate that the item at the head is a grounded node. However, there is no notion of next when declaring self.head = None.

When adding a value to the list using add,

    def add(self, item):
        temp = Node(item)
        temp.next = self.head
        self.head = temp

This is the first time the notion of a node is introduced to the list. The type of head changes from None to Node, and my feeling is that an associated arrow is now justified.

I've sketched this out:

The push remainder pop remainder arrows, or text depending on how you see it, are inverted. The push remainder arrow should be pointing towards the base of the stack not the other way around.

https://github.com/Bradfield/algos/blob/master/book/stacks/figures/decimal-to-binary.png

I've noticed a significant performance in the hot potato problem between using the naive implementation of Queue v/s the solution that uses collections.deque.

The naive implementation of Deque has similar performance issues, with insert and remove from left/rear requiring the whole array to move over.

CPython has an implementation using double linked lists, which could be worth talking about once the "Lists" section has been covered.

The current example shows web pages linked to from Luther Computer Science, which is weird.

This is the last chapter for which the code samples need to be moved to litpy and test coverage added.

There are some assets that are currently served via a CDN. This introduces a new point of failure, and also makes it difficult to work on the book without internet access. We should move these to locally hosted copies.

Via @robertdapice in #48 :

• The Binary Heap section is described as being implemented with the ‘list’ data structure. Should this be renamed to an ‘array’ data structure, given you’ve already addressed lists as an abstract data type (that itself is not, in fact, implemented with an array)?

Via @robertdapice in #48 :

• Markdown rendering is broken in a few places. Doesn't seem to be invalid markdown; could there be a bug in the markdown -> HTML library you're using? See example of putting Hexadecimals in number coding:
  

@richardartoul

Check out /book/recursion/dynamic-programming.md for an example of chapter with both python and js source code. However the build system doesn't support "literate" js at the moment. Check out /litpy-plugin.js for what it'd take to support that style.

For consistency, ease of modification and scaling to high resolution, all of the tree and graph diagrams should be rendered with svg. There is proof-of-concept for this in the dynamic programming chapter.

See here:
https://bradfieldcs.com/algos/recursion/dynamic-programming/

This would make it easier to review changes