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!
Post your questions here.
« A*, KD trees, Fibonacci Heaps Lecture
Graph Posted »
In the Dijsktra python problem, we have to make our own MyGraph and HeapPriorityQueue. Both take “object” as an argument in their constructor, but I’m not sure what argument to pass it.
Is adding a decoration to vertices considered to be “modifying” the graph?
No you’re allowed to do that, just don’t add/remove vertices or edges
In 9.5, if I need to call the replaceKey function on my heap when I only have a vertex to work with, I create a new Entry to store the vertex and then take advantage of the heap’s testEntry method to find the entry corresponding to that information in order to replace the key. But creating a new entry requires storing position information. How might I go about finding the position associated with the entry associated with that corresponding vertex in the heap?
Instead of doing that, you should think about decorating your vertices. There is a point where you naturally get the entry associated with a vertex, and you should store it at that point.
Is it okay if our topological sort just(?) returns an empty list when it finds a cycle? I’ve tried messing around with Try/Except blocks and looking into Python’s assertRaises function, but I’m having trouble getting my terminal to say that an exception was actually raised. The code is working properly, because it definitely detects cycles, it just then returns an empty list. Is that okay?
Because we asked you to throw an exception you don’t need to try to catch it, go ahead and just throw the GraphCycleException.
Right, I am throwing / raising it, but I can’t get my terminal to acknowledge that–no notification of the exception happens (would that only happen if I were catching it?) and instead the topological_sort comes back as an empty list.
If I’m throwing the exception, I should see some notification, right? Or would the program just fail to execute properly, and that would explain the empty-list-return?
Never mind–I just modified my code so that the exception is actually raised in my terminal. Thanks, Mike!
For 9.5, can we assume that src is in g? Also, can we assume that there are no parallel edges in g?
If the vertex is not in G, your code should just naturally return an empty list, due to how dijkstra’s works. No, you can;t assume that there are no parallel edges.
How are we supposed to test parallel edges if the insertEdge function of myGraph doesn’t allow insertion of edges that would make the graph non-simple?
If the src exists but isn’t in the graph, what should we do? We’re returning a graph, not a list, but we can’t return an empty graph without getting an error. Should we just return the nodes that exist in the graph without any edges connecting them?
Should we assume for problem 9.1 that there is a path between nodes u and v?
Yes the problem description says “assume that there is at least one path between u and v”
When testing my topological sort, is there a way to use assert to catch the GraphCycleExeption or is just raising it good enough?
If you’re trying to intentionally cause an error in your test cases and want to know if the exception was raised, you can make use of a try/except block. See here: https://docs.python.org/2/tutorial/errors.html#handling-exceptions
Just to be clear, in prob 3, the starting point Q is ‘one of’ the town points P?
No, Q is not part of the set of points P.
Can we utilize python’s built-in stack functionality for implementing topological sort?
In problem 9.3, is there a specific runtime we’re going for, or is anything fair game?
As always, you are encouraged to come up with a solution that is as efficient as possible. If you solve it with a runtime that is suboptimal, you might lose a few points.
In problem 3, is the cost proportional to the distance between two towns?
For this problem, you don’t know the distance between the towns. You just know that you have a constant time function d(A,B) that returns the cost for a road between A and B. You don’t need to be concerned with how this function works.
For problem 9.1, is run time supposed to be linear with respect to the number of vertexes?
It can be linear with respect to vertices or edges. But if you look below, we decided that O(V*E) isn’t linear, so just watch out for that.
In Problem 9.3, are we asked to minimize the cost of building the entire road network (i.e. sum of all edge weights) or the sum of the costs of the shortest paths from each Pi to Q (e.g. say n = 3, minimize the sum of the costs of the shortest paths P1-Q, P2-Q, P3-Q)?
You need to find the “lowest cost road network.” I think any more information would give away the answer to this question.
In problem 9.1, what is considered a linear time? Can O(VE) be considered linear?
It can be linear with respect to vertices or edges, but O(VE) would not be considered linear. O(V+E) would be fine though.
How are we supposed to get the entry to use in ‘replaceKey’ for Djikstra’s python problem as We can’t get the entry from the vertex??
Look through the support code to see what the methods available to you do.
In the support code (heappriorityqueue.py) the positions of entries don’t seem to be fixed, this makes it difficult to call the replaceKey method which requires an entry as it’s first parameter. Is there any way to retrieve an entry based on it’s key in the heap? (I couldn’t find any such method in the support code)
No there isn’t a way to use a key, you need to use the entry.
How do we find the “elements attached to the edges” which are supposed to be the distances? Is there some particular function (eg: “value()”) that we have to call?
by calling .element() on the edge you need…
Thanks Surbhi! (Found it myself after seeing that GraphEdge inherits from ElementHolder)
In prob 3, are the costs positive or can they be negative as well?
In prob 1, are u and v distinct?
Not necessarily. If they are not distinct, you should return 1.
For 9.3, are we required to describe the algorithm, or can we just mention the algorithm needed to come up with the solution? Thanks!
If you’re using an algorithm from class, you can just name it. If you’re modifying an algorithm from class, you can name the algorithm and describe the modifications. If you’re making up your own algorithm, you’ll obviously need to provide more detail so we know what you have in mind.
You must be logged in to post a comment.