runestoneinteractive / pythonds Goto Github PK
View Code? Open in Web Editor NEWProblem Solving with Algorithms and Data Structures using Python
Home Page: https://runestone.academy/runestone/static/pythonds/index.html
License: Other
Problem Solving with Algorithms and Data Structures using Python
Home Page: https://runestone.academy/runestone/static/pythonds/index.html
License: Other
Error reported in course pythonds on page index
My Username: andy1998410
My Email: [email protected]
On the page (http://interactivepython.org/runestone/static/pythonds/Trees/AVLTreePerformance.html#fig-worstavl) AVL Tree Performance, the equation Nh = Fh+2 - 1 for h >= 1 is given, which should be Nh = Fh+3 - 1 (for example, for h=2, N2= 4, f4 = 3, f5 = 5). I understand that counting can be different, depending on initial conditions, but with the numbers provided in the text, the equation does not hold and may be misleading.
Thanks for the great book and interface.
Best,
Andy
There are two files that use fillintheblank. Since the non-backward compatible changes were made to the new directive we need to update the text in the book.
Error reported in course pythonds on page InfixPrefixandPostfixExpressions by user i3rend4nv05 [email protected]
Third self check problem is cut off in chrome, showing only "5 * 3 ** (4 - " instead of "5 * 3 ** (4 - 2)".
Correct answer requires use of "^" operator despite the fact that the problem uses the "**" operator.
Found on page SortSearch/TheBinarySearch
Which group of numbers correctly shows the sequence of comoparisons used to search for the key 16?
should read Which group of numbers correctly shows the sequence of comparisons used to search for the key 16?
Is there an epub available? Or are there instructions how to produce an epub?
The BinaryTree class does not work if you are creating one with more than two layers, as the children are assigned to the wrong instance variables in the insert methods.
Method insertLeft | Line 30:
t.left = self.leftChild
should be
t.leftChild = self.leftChild
Method insertRight | Line 41:
t.right = self.rightChild
should be
t.rightChild = self.rightChild
The section titled "What Is Computer Science?" begins with the sentence:
Computer science is often difficult to define.
The word "often" detracts from the very important idea of the sentence, which would be strengthened by simply omitting it.
Missing the word "parentheses" in last sentence.
Error reported in course pythonds on page ObjectOrientedProgramminginPythonDefiningClasses by user [email protected] [email protected]
I understand the implementation of the gate classes.
However, I am struggling to see how 'source' is used in the 'setNextPin' function.
I have had a look through Codelens.
I can see how the ToGate calls the output (self.pinA/B.getfrom().getOuput()) using the Connector but I don't see how the setNextPin function calls the FromGate of the c1 as the source
Please help if you can
Frank
Error reported in course pythonds on page InfixPrefixandPostfixExpressions by user vemkiran [email protected]
In the last self check question that states "Modify the infixToPostfix function so that it can convert the following expression", the expression provides is "5 * 3 ** (4 - 2) ".
So the answer generated by the program is "5 3 4 2 - ** *"
But when I enter that answer and submit, it says incorrect. But when I replace ** with ^, it accepts it as a correct solution.
Error reported in course pythonds on page index by user thecodingconductor [email protected]
The chapter 3.7 in the pythonds book throws a 404. Love the book!
From @bnmnetp on August 14, 2016 9:16
Error reported in course Problem Solving with Algorithms and Data Structures on page http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/AnAnagramDetectionExample.html
My Username: tingRay
My Email: [email protected]
Description: In solution 1 of Anagram detection problem for strings, the output of 'anagramSolution1('abcd','dcgba')' will be True.Obviously,it is incorrect.
Copied from original issue: RunestoneInteractive/RunestoneComponents#224
Error reported in course pythonds on page GettingStartedwithData by user UPS [email protected]
In the following code when we print(A) after changing the element in myList - A shows the new value whereas if I run the same code on my local or an online REPL, it prints the same value as before for A
myList = [1,2,3,4]
A = [myList]*3
print(A)
myList[2]=45
print(A)
Output in runestone: [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
[[1, 2, 45, 4], [1, 2, 45, 4], [1, 2, 45, 4]]
Output in local: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
Cannot configure a Database URL!
Skipping all DB operations because environment variables not set up
Got the above error while trying to build. How do I get the URL to configure in the environment variable
Error reported in course pythonds on page BinaryHeapImplementation by user TheEpsylon
"To finish our discussion of binary heaps, we will look at a method to build an entire heap from a list of keys. The first method you might think of may be like the following. Given a list of keys, you could easily build a heap by inserting each key one at a time. Since you are starting with a list of one item, the list is sorted and you could use binary search to find the right position to insert the next key at a cost of approximately O(logn)O(logn) operations. However, remember that inserting an item in the middle of the list may require O(n)O(n) operations to shift the rest of the list over to make room for the new key. Therefore, to insert nn keys into the heap would require a total of O(nlogn)O(nlogn) operations. "
What you're describing is insertion sort! It has a cost of O(n^2). This is not the naive way: the naive way is to repeatedly insert for a total cost of O(n log n) (is that what you were trying to explain?).
Error reported in course FIT5211 on page Lists by user lwoo0004 [email protected]
Incorrect info on page ... pop(i) is O(k) not O(n).
e.g. popping from an indexed location from the end of a list
See python docs:
https://wiki.python.org/moin/TimeComplexity
Pop intermediate O(k)
And revised code:
popzero = timeit.Timer("x.pop(0)", "from main import x")
popend = timeit.Timer("x.pop()", "from main import x")
popend_minus = timeit.Timer("x.pop(-2)", "from main import x") . # ADDED
print("pop(0) pop() pop(-2)")
for i in range(1000000,100000001,1000000):
x = list(range(i))
pt = popend.timeit(number=1000)
x = list(range(i))
pz = popzero.timeit(number=1000)
x = list(range(i))
pe = popend_minus.timeit(number=1000)
print("%15.5f, %15.5f, %15.5f" %(pz,pt,pe))
pop(0) pop() pop(-2)
0.40309, 0.00010, 0.00015
1.20204, 0.00009, 0.00017
1.93542, 0.00009, 0.00014
2.73203, 0.00009, 0.00014
3.45721, 0.00010, 0.00015
4.21476, 0.00011, 0.00015
5.14111, 0.00010, 0.00017
Error reported in course pythonds on page http://127.0.0.1:8000/runestone/default/reportabug
This report is to test the new Github API bug report system for the Runestone textbooks. Please ignore this issue.
I believe the wording of the answer to question intro-8-2 in Chapter 1.8 Runtime Errors of How to Think Like a Computer Scientist could be improved.
The question is Who or what typically finds runtime errors?
The expected answer is The compiler/interpreter.
I would like to see the answer changed to be The interpreter.
It is my view that a compiler finds compile-time errors, not run time errors.
What Course are you in
https://runestone.academy/runestone/books/published/pythonds/Graphs/DiscussionQuestions.html
Describe the bug
The numbering of the questions is wrong (there are 2 number 1s). Also, for the current question 2, is there a goal to the breadth first search? Is it too find the shortest path, ignoring the weights?
Error reported in course pythonds on page DiscussionQuestions by user i3rend4nv05 [email protected]
Questions 3 and 5 are identical in section 2.10 Discussion Questions
Error reported in course pythonds on page InfixPrefixandPostfixExpressions by user leefoster1992 [email protected]
Hi there, just noticed the last problem has ** to indicate the exponent, but the answer only works if ** is replaced by ^
In a_proper_python_class.rst both activecodes have the same ID.
From @delimitry on July 15, 2015 12:58
Superfluous ")" parenthesis in del operatrion for Sorted List O(n))
Copied from original issue: RunestoneInteractive/RunestoneServer#606
Error reported in course pythonds on page ControlStructures by user Shashank [email protected]
At the last section of Control Structures which is 'Self check' its written "For an extra challence, see if you can figure out how to remove the duplicates"
Here challence mist be equal to challenge.
In this page:
https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheQuickSort.html
in question 4, if you select an incorect answer, it looks like this:
There shouldn't be double backticks by some of the answers. I was using Firefox.
The anagram solution 1 return true when run with print(anagramSolution1('abcd','addcb')).
I think the problem is where after running the stillOK statement that return False, upon exiting if statement, it is assigned stillOK = True, which cause it to enter the while loop even when the length does not match.
I have added an else statement after the stillOK = False and it returns the expected result.
def anagramSolution1(s1,s2):
alist = list(s2)
pos1 = 0
if len(s1) != len(s2):
stillOK = False
else:
stillOK = True
while pos1 < len(s1) and stillOK:
pos2 = 0
found = False
while pos2 < len(alist) and not found:
if s1[pos1] == alist[pos2]:
found = True
else:
pos2 = pos2 + 1
if found:
alist[pos2] = None
else:
stillOK = False
pos1 = pos1 + 1
return stillOK
Error reported in course pythonds on page InfixPrefixandPostfixExpressions by user mmarchese1 [email protected]
The third self-check problem is to convert "5 * 3 ** (4 - 2)" to postfix. The correct answer is "5 3 4 2 - ** *", but your webpage is looking for "5 3 4 2 - ^ *".
pre-order traversal code currently looks like this in the book . In-order and post-order traversals handle the case where the tree might be empty , but not pre-order. Would be nice to add a check here.
def preorder(self): print(self.key) if self.leftChild: self.leftChild.preorder() if self.rightChild: self.rightChild.preorder()
Listing 3 on this page : http://interactivepython.org/runestone/static/pythonds/Trees/TreeTraversals.html
Error reported in course pythonds on page TowerofHanoi by user belozi [email protected]
In the explanation to the Tower of Hanoi problem, the author has the pegs labelled with variable names, but discusses the problem in terms of peg numbers. This makes understanding the material confusing.
Error reported in course pythonds on page Exercises by user aw9677 [email protected]
Line 15 of the solution to activity 12.7 is missing the conversion to list, currently it reads:
keys = letter_count.keys()
And it should read:
keys = list(letter_count.keys())
Error reported in course pythonds on page TheBinarySearch by user Amresh [email protected]
The answers given are incorrect.
Q-13 - (A) 11, 5, 6, 8
Q-14 - 11, 15, 17
Error reported in course pythonds on page DijkstrasAlgorithm by user CMZ [email protected]
I copied the algorithm code and and added in some vertexes and edges like in an earlier chapter but it is always giving the response that the distance is 9223372036854775807:
from pythonds.graphs import PriorityQueue, Graph, Vertex
def dijkstra(aGraph,start):
start = Vertex(start)
pq = PriorityQueue()
start.setDistance(0)
pq.buildHeap([(v.getDistance(),v) for v in aGraph])
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
print("2")
newDist = currentVert.getDistance()
+ currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance( newDist )
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert,newDist)
g = Graph()
for i in range(6):
g.addVertex(i)
g.addEdge(0,1,1)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
start = Vertex(1)
dijkstra(g,start)
print (Vertex(2).getDistance())
Hi,
In the following text (from section 5.5.2, Collision Resolution, just before figure 11) I think the 1, 3, 5, 7... sequence should be 1, 4, 9, 16, 25, 36.
It would also be good to clarify with an equation, for example:
The ith skip will be i^2, meaning the ith probe be (h+i^2)%sizeoftable
A variation of the linear probing idea is called quadratic probing. Instead of using a constant “skip” value, we use a rehash function that increments the hash value by 1, 3, 5, 7, 9, and so on. This means that if the first hash value is h, the successive values are h+1, h+4, h+9, h+16, and so on.
Cheers,
Paul McKeown.
University of Canterbury, NZ.
Missing space before :ref: in file AnAnagramDetectionExample.rst
replacement.:ref:ActiveCode 1 <lst_anagramSolution>
Found on page: Recursion/Dynamic Programming
Paragraph with class _19002997
reads Although the algorithm in AcitveCode 3 is correct, it looks and feels like a bit of a hack.
when it should read Although the algorithm in AcitveCode 1 is correct, it looks and feels like a bit of a hack.
The idea is that in the case where the the first item in the list does not belong toward the middle of the list, the median of three will choose a better “middle” value.
http://interactivepython.org/courselib/static/pythonds/SortSearch/TheQuickSort.html
Fix .rst file to correctly link to online book
Error reported in course pythonds on page http://127.0.0.1:8000/runestone/default/reportabug
This issue is to test using Github tokens instead of standard user credentials in the Github API enabled bug reporting system. Please ignore this error.
Error reported in course pythonds on page TheMergeSort by user flavianshem [email protected]
The implementation of the merge sort makes it an unstable sort algorithm. During merging, if two elements from both halves are equal, the left element should be added to the list first before the right element.
Remove extra characters from first paragraph. trade-ÁÁ off
should be trade-off
Error reported in course pythonds on page http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html#hash-functions by user anonymous [email protected]
Hi, in 5.5.1 Hash Functions of Problem Solving with Algorithms and Data Structures using Python, last line of the 4th paragraph. I think you meant to say ..."34"+56+55+64+"10"=219... The 43 and the 01 are not reversed.
I guess the original authors might have to take a look to decide this . But In the implementation of Graphs, can we just use "weight" instead of "cost". I suppose most readers would ofcourse understand that its conceptually the same , but I guess it would be more homogenous if the book used 'weight'
def addEdge(self,f,t,cost=0):
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
```
http://interactivepython.org/runestone/static/pythonds/Graphs/Implementation.html
Error reported in course pythonds on page ObjectOrientedProgramminginPythonDefiningClasses
My Username: rb7
My Email: [email protected]
https://docs.python.org/3/library/operator.html
if I define division as truediv, it works in python 3.5.2
def truediv(self,other):
newnum = self.num * other.den
newden = self.den * other.num
common = gcd(newnum,newden)
return Fraction(newnum//common,newden//common)
However, in the course activecode, only div method definition works.
Are we dealing with python 3 or python 2 or not? I am slightly confused.
Error reported in course pythonds on page VocabularyandDefinitions by user Viktor.Palchyk [email protected]
In Definition One it is written that:
"If each node in the tree has a maximum of two children, we say that the tree is a binary tree."
Then it is stated: "Figure 3 illustrates a tree that fits definition one. The arrowheads on the edges indicate the direction of the connection."
Actually on Figure 3 I can see 3 children for node1.
Isn't it a mistake?
Error reported in course pythonds on page https://runestone.academy/runestone/books/published/pythonds/ProperClasses/make_your_class_comparable.html by user agneshe [email protected]
2.2. Making your class comparable is empty.
Listing 1 requires explicit import of operator
module to function correctly. Should this be included in the listing?
opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
Error reported in course pythonds on page GettingStarted by user navidpaya [email protected]
The progress indicators using the green color ticks and yellow bullets are wrong. It shows lessons I have never opened as completed with the green tick and then if I go to them, it shows me the mark as completed button.
Error reported in course pythonds on page ImplementinganUnorderedListLinkedLists by user anonymous [email protected]
The Complete UnorderedList Class (unorderedlistcomplete)
This active code has error in the remove function.
When you supply to a value to remove function that is not in the list, it gives a syntax error.
The condition where current becomes equal to None is not handled. Maybe there should be message like "Not found"
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.