bradfield / algos Goto Github PK
View Code? Open in Web Editor NEWAlgorithms and Data Structures book
Home Page: http://bradfieldcs.com/algos
License: Creative Commons Zero v1.0 Universal
Algorithms and Data Structures book
Home Page: http://bradfieldcs.com/algos
License: Creative Commons Zero v1.0 Universal
It may be useful to add a section to each chapter with corresponding exercises.
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.
Clicking on the "Introduction" link takes you to http://bradfield.institute instead of http://bradfield.institute/algos/analysis/introduction/.
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.
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.
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.
Let's decide on a grammatical person and stick with it.
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.
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
Via @robertdapice in #48 :
It is currently a little confusing, and doesn't seem to be fully reflected in the code samples.
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.
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:
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.
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}
Via @robertdapice in #48 :
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
Throughout the book, we should consistently consider a "section" to be a child of a "chapter". This is not currently the case.
The current example shows web pages linked to from Luther Computer Science, which is weird.
From #34
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.
Currently this section is in "draft" because the code appears to be incorrect. We should fix and publish it.
This would make it easier to review changes
Perhaps in the introduction, we should have a section which:
The unordered list section appears to not be rendering for some reason. It should also be in litpy with test coverage.
From #30 (comment)
This is the last chapter for which the code samples need to be moved to litpy and test coverage added.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.