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!
The graph project has been posted! Questions go here. LAST PROJECT LET’S GO.
« HW9 Posted
Levenshtein Distance Lecture Posted »
As I create edges in the visualizer the earlier edges disappear seemingly at random. If I save the graph the edge still shows up in the file, as well as when I ask for incident Edges and a list of all edges.
Any help as to why these edges would show up in all of the records but not be displayed by the visualizer?
Just to confirm, for MyDecorator class,
1. If the key exists but has a ‘NULL’ value, it should return FALSE, am I right? since it does not have a decoration.
2. If the key does not exist, then it should return FALSE, as well, right?
The MyDecorator class is generic, and as such does not necessarily return a boolean. This means that you probably shouldn’t return “false” in either of these cases. It is up to you how you decide to handle those two cases, but throwing an exception might be a good idea.
(To clarify, you will not know from within the class what type of object it returns, since values are of type V. Because of this, you can’t really just have a check such as “if key is null, return false”.)
Sorry I meant for “hasDecoration” method in MyDecorator class, for the same question above. Let me know when you get a chance. Thanks.
This is your call. We tell you what the expected behavior is in the comments of the stencil.
When choosing a random source node, do I have to randomize it everytime I run it or can I hard-fix specific node? Thanks!
It’s up to you.
Hi, what’s the runtime for creating an empty array of size n in java?
Are we allowed to import data structures from java.util?
In the documentation, it says that “only vertices which are at the ‘root’ of a cloud should have a cloud decoration” and “only ‘non-root’ vertices should have a parent decoration”. Because every vertex starts off with its own cloud, should we delete cloud and parent decorations as we iterate through each node?
Additionally, I have the same problem concerning CS016AdaptableHeapPriorityQueue. Everything currently works when i use the nds4 implementation for the heap priority queue so I’m not quite sure where to look.
In the MyDecorator class I am having trouble turning the Iterableof keys into a Set to be returned in the getKeys method that is used by the optional animation. I understand that a Set is a subinterface of Collection which is a subinterface of Iterable but my program is freezing after I tried to transfer between all these interfaces. Is there an easier way to get all my keys into a Set or maybe a hint as how to do so?
It depends on what data structure you are using to store your decorations. You should take a look at the documentation for the data structure you’re using to see if there is a method that could help you.
I am getting a null pointer when trying to add a CS16Vertex to the NodeSequence in my insertVertex method. I have tried using print lines but everything looks fine. Is this a common problem?
Same here. The call stack contains only support code, with the most recent call being support.graph.GraphCanvas.trappedEdge. Would love to know if anyone else got this issue/if there is a resolution.
Just because the call stack contains only support code does not mean there is an issue with the support code. If you haven’t implemented some/any of the stencil methods this can cause issues. There are also many issues that can arise if you’ve implemented something incorrectly in the adjacency matrix, NodeSequence, etc.
Hey, should we not change the variables you declared for us in Graph either? I want to change a parameter in the generics. Should I find a different way?
Just kidding, then I would have to change a signature. But I don’t get how we’re supposed to change the element of a CS16Vertex. All the code is done in terms of CS16Vertex but only GraphVertex has a setElement method..?
I figured it out, sorry
My graph was working, then I realized I hadn’t updated to the newest cs016 jar. After updating, vertices are not appearing, and I’m getting a null pointer error at support.graph.EdgeIterator.(EdgeIterator.java:20).
There are no null pointers from my code in the stack trace, so I’m not sure what’s going wrong. Could there possibly be a bug in the support code?
Have you implemented the incidentEdges method yet? I’ve seen this error occur when that hasn’t been implemented yet.
I hadn’t, but I think I’ve implemented it correctly now. However, I’m getting a new mysterious null pointer outside my code own when I create an edge now. Maybe I should just come into hours?
You should either use the Eclipse debugger or add printlines to help narrow down what’s being called before the problem arises. If that doesn’t help, then you should go to hours.
I’m having a similar problem. I stripped the code down so I only have implementations for vertices and insertVertex (with the intention to only put vertices in the visualizer). I’m getting a NullPointerException from support.graph.GraphCanvas.trappedEdge.
I just went to hours earlier and the TA said he wasn’t sure what was wrong, so I thought I’d give the discussion thread a try.
Make sure to implement incidentEdges(). The support code calls this when adding vertices.
Exactly what I needed, thanks Julie!
What are you returning in your vertices() and edges() methods? If you return null at any point this might break the support code.
What should happen when I add one more vertex to the max allowed?
1. raise exception? In this case which one?
2. Or it adds the vertex without a problem, but problem arises when trying to connect an edge to this ‘over-added’ vertex since adjacent matrix holds edge information!
Let me know thanks!
We won’t test for that condition, so you do not need to handle it.
Sorry I’m confused. We’ve talked about it in sections, but we don’t have to implement it at all? Let me know. Thanks.
I don’t think this was discussed in most sections, but I could be wrong, since each section is slightly different. It’s possible that you’re confusing this with something else (we talked about assigning vertex numbers in section). In any case, you don’t need to handle this case, but it’s fine if you do.
What is the syntax for instantiating a CS016AdaptableHeapPriorityQueue? If I’m using Keyclass and Valueclass for K and V respectively, this throws a very strange error:
CS016AdaptableHeapPriorityQueue pq = new CS016AdaptableHeapPriorityQueue();
I imagine it has something to do with the “extends java.lang.Comparable” bit, but I can’t figure out how, nor was this something that was explained about generics.
If you look at the documentation, the class is listed as ‘Class CS016AdaptableHeapPriorityQueue<K extends java.lang.Comparable,V>’. What that means is that you should be including generics (a key-value pair) such that K implements the interface java.lang.Comparable. You can look up the Javadocs, but what that basically means is that the class you put in as the key should be well-defined with less-than, greater-than, and equal-to comparisons (,==). ‘CS016AdaptableHeapPriorityQueue pq = new CS016AdaptableHeapPriorityQueue()’ doesn’t include these generics, and so you should fix it so it does. Feel free to come to hours if you want a more in-depth explanation about generics.
Hi, so this may be an important thing to note. Yesterday I went in to TA hours, but my TA was unable to figure out what was wrong with one line in my code even after looking at the solutions and spending 40 minutes working with me. Today, I discovered the problem. In programming Prim’s algorithm, you can no longer use CS016AdaptableHeapPriorityQueue, as the replacekey method has some problems locating entry (or so I assume based on the behavior). Rather, Prim is only able to work if you use the NDS4’s HeapAdaptablePriorityQueue. Perhaps someone can check that this is the case, and update the assignment?
You can use the CS016AdaptableHeapPriorityQueue. You just need to think about how you’ll store the entry associated with each vertex.
I’m pretty sure I stored the entry correctly, since I was able to get the entire Prim’s working simply by changing the one line of instantiation code designating the specific priority queue datastructure (from CS016AdaptableHeapPriorityQueue to HeapAdaptablePriorityQueue). Maybe this was just a problem specific to my code, so I guess if others don’t run into this problem, it’s no big deal.
I also ran into the same problem and the same solution fixed it. With the CS016AdaptableHeapPriorityQueue, when I tried to run the ReplaceKey method, it said that the position was invalid. However, when I change my priority queue to type HeapAdaptablePriorityQueue, the algorithm works. The error messages say that an exception is thrown at LinkedBinaryTree’s check Position method(error goes from ReplaceKey->Upheap->isRoot->checkPosition). Did you get the same errors or was it something completely different?
Nevermind, sorry the problem I had was unrelated to the CS016AdaptableHeapPriorityQueue.
Whoops. Yeah, my advice for other people reading this problem is to read the handout very carefully.
I’m also running into this same problem. I’m kind of at a loss as to why there would be a difference at all.
Also running into the same problem.
It’s probably a good idea to step through your code with the Eclipse debugger or add a lot of print lines to help you here. Pay close attention to the vertices you’re asking to update the key on, and whether it makes sense to try updating that key. If you’re still at a loss, come to hours, but definitely take the time to try figuring it out for yourself first or the TA may send you away.
In MyPrimJarnik, are we allowed to modify the signature of the method? I was thinking of adding extra methods to MyGraph to help with Prim’s but Eclipse won’t recognize those methods because those are not methods of AdjacencyMatrixGraph. I was hoping to change AdjacencyMatrixGraph to MyGraph.
You should not change the signature of genMinSpanForest, otherwise it will no longer work with the support code. You may however create any helper methods with whatever signatures that you wish.
Is the optional animation for extra credit? It doesn’t specify.
No. The optional animation is just there to help you debug.
In context of the opposite() method in MyGraph, does it matter if the vertex we pass in is the ToVertex or FromVertex? As in the visualizer, the edges appear to be undirected after they’ve been added, so should it matter if v is To or From?
No, it doesn’t matter.
I am confused about the Prim-Jarnik algorithm for this project. From the steps listed in the project specification, it seems nearly identical to the pseudocode in class. Also, the steps mention looking at each incident edge and then updating the key if necessary. From my understanding, the O(V^2) runtime comes from the fact that adjacency matrices take O(V) to get the incident edges, but it seems as though you still need to go through each edge and potentially update the costs, meaning the runtime for this portion is still O(ElogV) (as was the case with adjacency sets). In essence, I am confused as to why the runtime is only O(V^2) and not O(V^2 + E logV).
The runtime is O(|V|^2*log|V|). The handout has been updated accordingly.
Do we need to be able to handle negative edge weights?
Don’t worry about negative edge weights.
While setting “fromVertex” and “toVertex” do we consider v1 to be the “from” or v2? Is there any set convention?
It shouldn’t matter. Just be consistent. Most people would probably choose to make v1 the “from” vertex though.
Can we assume that the runtime of CS16Edge class’ functions “getFromVertex()” and “getToVertex()” is O(1)?
Do we need to use cs016.jar or cs016NEW.jar in this project? (as external libraries)
Just the plain old cs016.jar.
You must be logged in to post a comment.