Hey there! Thanks for dropping by CS16: Algorithms and Data Structures! Take a look around and grab the RSS feed to stay updated. See you around!
It’s due 4/10 at 11:59 PM.
Write your questions here!
Note: You should be able to do problems 1, 2, and 5 right away, but you may want to wait until next Tuesday’s lecture (4/1) to do problems 3 and 4.
Shortest Paths Lecture Posted »
For Question 8.4, I’m very confused about how I should decorate the vertices with prev pointers. I tried doing vertexB.prev = vertexA based off the MyGraph class description (in mygraph.py), but this didn’t work. I also looked into Python Decorators, but don’t see the relevance. Thanks.
Are we expected to use median of medians to improve the performance on quicksort, or does it suffice to randomize the selection of the partition?
You do not have to use median of medians (unless you really want to…). Random pivot selection is just fine.
For the python radix sort, is it bad to modify the already existing array and sort in place, or should we create a new array?
The profiler will make a copy of the input list, meaning it’s fine to sort in place.
Is there a runtime requirement on the shortest path problem (8.4)?
While we don’t specify a runtime requirement, it is advised that you solve the problem efficiently (using the algorithms presented in class), instead of brute-forcing it.
For 8.2, how are the non-prereq courses connected to each other? If we have three courses, A, B, and C, and A is a prereq for B, do we assume that C is connected non-directionally to both A and B?
Courses that are not pre-reqs for each other have no relation, so they are not connected in any manner.
BEST SORTING ALGORITHM EVER:
For 8.2, do we assume that we are passed a DAG containing all of the n courses?
Hey TAs. Couple of questions:
1. Are we to assume that we will never get an empty array for the sorting question?
2. In Python, do dictionaries have to have exclusively string/integer keys and values? What about string keys and values of other types?
1. No, you can’t make that assumption. Should be pretty easy to handle though!
2. Nope, they can map an object of any type to another object of any type.
1. No. It’s not specified in the spec that you don’t need to worry about this, so you should handle the case.
2. Dictionaries are not exclusively string/integer keys. You can experiment in the python REPL to see if what you want to use works.
We can write helper methods as needed for the python problems, right?
In problem 8.2, you state that “A course may have any number of prerequisites.” Does this mean that each of the many pre-requisites must be taken, or that one of the many prerequisites must be taken (similar to choosing an introductory CS sequence)?
Each course can have however many it wants and you have to take all of them in order to take it
Just adding on to what Ardra said, there is not a case where one pre-requisite disqualifies the other prerequisites — so the introductory CS sequence analogy doesn’t really hold for Topological Sort.
In Problem 8.4 my terminal displays the path as follows: “Shortest path found: [v0:None, v1:None]” ; is there any reason for the “:None”? The code doesn’t give an assertion error so the program considers my path equal to [v0, v1]
That’s fine. It’s just the way the nodes are printed.
That’s just a quirk of the support code and visualizer because the GraphEdge function can take a second value. You should be fine.
Can we use Python’s inbuilt queue functionality in the programming problems?
Yep, after we’ve had you implement a datastructure you’re free to use the built in versions
Do we need to account for negative integers in the sorting problem?
And in the shortest path problem, do we need to account for self-loops?
How would we test for this though? In path_test.py, I just tried to connect a vertex to itself, but the terminal gives me this message. Apologies if I’m being concrete here!
Traceback (most recent call last):
File “path_test.py”, line 245, in
File “path_test.py”, line 234, in test7
g.insertEdge(v3, v3, GraphEdge(0)) #self loop
File “/Users/rfreimanmendel/Documents/Brown University ’12-’16/Spring ’14/CSCI0160/Problem Sets/hw8/python/mygraph.py”, line 184, in insertEdge
raise GraphException(“can’t have a vertex connected to itself”)
mygraph.GraphException: can’t have a vertex connected to itself
This does indeed seem to be the case. Don’t worry about self-loops, then.
You must be logged in to post a comment.