Question: > When counting edges, does the edge that connects Vertex a with Vertex b > and the edge that connects Vertex b with Vertex a count as two > separate vertices or as one? Answer: You are given an undirected graph. So an edge connecting vertices a and b is counted as one (even though you have two distinct entries for them).
Question: > There are no paths for most of the queries in the CityPairs.dat > with a threshold of 150. What should we do? Answer: Change LENGTH_THRESHOLD to 200 instead of 150.
Question: > What is the "cost" of an edge? Answer: Cost of en edge equals its length or its weight. The length of an edge equals the Euclidean distance between its endpoints.
Question: > What is the degree of a vertex? What do you mean by the "average > degree of a vertex"? Answer: Degree of a vertex equals the number of other vertices adajacent to it (i.e., # of edges incident on it, or the same as the length of its adjacency list). For the average degree, what is required is the average degree of the graph (not of every vertex). This equals the sum of the degrees divided by the number of vertices.
Question: > Is there a typographical error in what edges to add? Answer: YES! It should read: "The edges in the graph consists of every possible edge whose length is at most LENGTH_THRESHOLD (use 150 units for this assignment)." In other words, the only vertices that are adjacent to each other are the ones that are closer than 150 units from each other.
Question: > Should we change Vertex data field from String to int? > public String name; //from this > public int name; //to this Answer: That is a reasonable change to make.
Question: > If the hash value of a word is 25 and it is inserted at location > 30, what should be reported for the word: 25 or 30? Answer: I suggest you report both values. Its hash value and the location where it was finally inserted.
Question:
> The URL given in the handout for the Macbeth text has typos.
Answer:
Yes. It should read:
http://www.cs.fiu.edu/~giri/teach/3530/s02/Prog4/MacbethActI.txt
Question: > Why are different people getting different count answers? > How can we debug? Answer: People are getting wrong answers because of bugs in their programs. These bugs arise because of incorrect handling of punctuations/spaces. To debug your program. Make a file with multiple copies of only one word -- say "play". But strew the file with punctuations in every form as it appears in the data file. Now check your answers and debug. You should not be relying on the answers give you to check your programs. You are supposed to debug it yourself! YOU WILL GET NO MORE UPDATES ON POSSIBLE CORRECT ANSWERS.
Question: > Do we insert duplicates? Weiss' code does not. Answer: What would be the purpose of inserting duplicates? Leave them out.
Question: > Is there a reason that Weiss's code does not ask for a HashCode when an > element is added? I looked at the text book and he did not do a good > job of explaining his hashing code. Answer: Not true. Method add calls findPos on line 8 (pg 702), which in turn calls hasCode() on line 10 (pg 703). The blurb at the top of Sec 20.4.1 (p 697) explains some of the logic. hashCode is a method that needs to be defined for any object that you want to create a hash table for. This paragraph also explains the algorithm used in Java's predefined hashCode() method for the String object. This is also explained in: http://java.sun.com/products/jdk/1.2/docs/api/java/lang/String.html under the description for hashCode().
Question: > HashSet extends AbstractCollection. Do i need to import this as well > or do i use the AbstractCollection from the java libraries? Also, > Hashmap extends MapImpl. Where do I find that? Answer: All these files are now downloadable from the course website. In fact you can find all the files from weiss.util and weiss.nonstandard on your course website (look under useful links).
Question: > Are "o'" and "I'" considered different from (or same as) "o" and "I"? Answer: Different.
Question: > To change the Table Size of Hamlet to 8191, do I have to change the > "DEFAULT_TABLE_SIZE" in the HashSet class or is there another way? Answer: A better way is to add another constructor to the HashSet class.
Question: > Are we supposed to use the Hashtable class or the Hashset class? In > the assignment, it says to read the story into a Hashtable, but later > on it says that we need to use the Hashset class. Answer: "Hash tables" are what these data structures are called generically. You are required to use the class called "HashSet" (or HashMap) as implemented in Weiss' book. You can download this from our course web site.
Question: > When removing all words that are capitalized, my program removes > the words "A" and "I" - is this correct, or should I make > exceptions for those words? > What about the "I" following the words SCENE and ACT? Should that "I" > be included as part of the text? Answer: "A" & "I" are valid words and should not be removed (even though they are all capitalized). So they should be treated as exceptions. However, the "I" following SCENE or ACT should not be treated as words. You could treat "ACT" or "SCENE" as special words for which you need to ignore the word following it.
Question: > Do you have answers for homework #4? Answer: (Updated but not verified!) Here are the top 10 frequencies that several of the students of your class generated for the Hamlet text. Alternate answers are also provided. [Thanks for all who emailed me. If you have different answers, email me.] the 196 (maybe 197?) of 164 to 156 (maybe 155?) and 154 I 112 (?) it 107 my 104 in 101 (not 102: you are counting in't) you 99 (maybe 97?) not 74 And 73 The Size of largest Cluster is 6 The Average Cluster size is 1.430 Load factor is 23% or 0.23
Question: > Do I need to differentiate a word with the first capital letter > and the same word written without the first uppercase letter? Answer: Ideally you should treat the words "he" and "He" as different occurrences of the same word. However, for this assignment, you may treat them as different words.
Question: > Can the code from HashSet (from Weiss' text) be changed for our programs? Answer: You can only change it in limited ways. In particular, any changes should leave the insertions in the same location.
Question:
> Are all punctuations to be ignored in words.
Answer:
After looking at the text more carefully, it seems that there should
be some exceptions. Words such as 'tis, usurp'st,
Let's, do't, to-night, bed-rid, etc.,
should be treated as one word. The apostrophe (') and the hyphen (-)are
therefore to be treated as regular alphabetical characters. Watch
out for those double hyphens, which are to be treated as
punctuations and not part of the words. For example, in As, in
their birth--wherein they are not guilty,, the words birth and
wherein are two separate words. You can leave the apostrophe or the
hyphen as characters in the stored word.
Question: > Is there an error in the FORMULA for length INCREASE when a city > is inserted? Answer: YES!!! It should read: increase = distance(a,c) + distance(b,c) - distance(a,b) Note the "-" instead of the "+" for the last term.
Question:
> I was looking at the general description of the homework and I just
> realized that trying to implement the LinkedList java class in
> order to solve for this problem is not going to be possible because
> the LinkedList class can only be implemented in situations where
> you only have to perform stacking, queueing, and dequeueing
> operations
>
> I don't think this class can be used to implement a doubly or circular
> linked list. I checked the documentation for the linked list class and
> it says and I quote "the LinkedList class provides uniformly named
> methods to get, remove and insert an element at the beginning and end
> of the list. These operations allow linked lists to be used as a stack,
> queue, or double-ended queue (deque)."
Answer:
I am not sure where your quote is from. As discussed in class, LinkedList is
particularly useful anytime there is a need to insert in the middle of an
existing list, which is the case for your assignment. LinkedList class
provides a whole host of methods to insert and delete from anywhere in the
list. These methods are clearly explained at the following website:
http://java.sun.com/products/jdk/1.2/docs/api/java/util/LinkedList.html
The right thing to do is to declare a class called Tour and have the
following field in it:
private LinkedList tour;
Now all methods in Tour can access methods such as tour.add(..) or
tour.get(..) and so on.
Question: > Do I need to use CIRCULAR linked lists? Answer: NO!!! That was a typo in the handout. You only need to use the class LinkedList defined in java.util.* As you know, this is a DOUBLY-linked list. Note that you do not need to implement any of the methods required for the linked list. You should be using only the standard methods provided by the LinkedList class.
Question: > I have been working on the homework assignment for a little while and I > am now on the part where I need to design the tour. Before I ask the > question, let me first explain the way that I am doing the assignment. > I am reading the text file into my program and am using the > information to create cities, which I then bring into a LinkedList. Answer: The cities are given in some input order. Your program needs to output an ordering of the cities that has "small" TourLength. First of all, there is no need to create a linked list that simply reads in the cities in the given input order. All you need is one linked list with the tour that your program constructs. Question (Cont'd): > What I then plan to do is to iterate through my list and create the > tour by copying cities into another LinkedList in the correct order of > the tour, then deleting cities from the original LinkedList as I > include them into the tour. what I do not understand is the > findBestInsertPoint function. If I was to use this function, wouldn't > I need to have a full tour planned out befrore I find a suitable place > to insert the city? Answer: If you already have a full tour planned, then there is no need to "insert" a city into the tour. The "insertion" is part of the planning to find a good tour. Here is a better explanation of what you need. If the input has n cities, then the program operates in n iterations. At the end of the i-th iteration the program should have constructed a "partial" tour on the first i cities it has read in. The first 3 iterations are part of the initialization. The first 3 cities are read in and an initial tour on the first 3 cities is constructed as described in the handout. All subsequent iterations follow the same scheme described below. Thus, in iteration i+1, the program reads in the coordinates of the i-th city and "inserts" it into the "partial" tour that it is maintaining on the the firsti cities. It has i different possible locations to "insert" the i+1-st city it reads in -- either between the first and second city, or between the second and the third, and so on. It picks the best of these possibilities as described in the handout (i.e., by finding which insertion location results in the minimum increase), and then inserts this city in that location in the partial tour. Therefore, at the end of this iteration, it now holds a partial tour on i+1 cities. Since you read in a city and process it immediately, you do not need a separate list holding the cities that you read in. Once a city is inserted in a certain location in the existing partial tour, its location never changes after that.
Question:
> What if 2 positions to insert a particular city results in the same
> minimal increase to the tour. How should I proceed then? Thanks.
Answer:
Pick the first of the two, assuming you always start the search from the
"home" city.
Question:
> What are the Tour Lengths for the 2 Data files
Answer:
TenPts.dat 3.242394736577974
HundredPts.dat 9.035409298071231
Question: > Please give us details on the solution for TenPts.dat. Answer: Initial Tour: 0, 1, 2 TourLength = 1.1292246164356026 Iteration 3: Tour: 0, 1, 3, 2 Inc = 0.3528549427219845, TourLength = 1.482079559157587 Iteration 4: Tour: 0, 1, 3, 4, 2 Inc = 0.41382126925007257, TourLength = 1.8959008284076595 Iteration 5: Tour: 0, 1, 3, 5, 4, 2 Inc = 0.6894131465178641, TourLength = 2.5853139749255236 Iteration 6: Tour: 0, 1, 6, 3, 5, 4, 2 Inc = 0.2027319016362315, TourLength = 2.788045876561755 Iteration 7: Tour: 0, 1, 6, 7, 3, 5, 4, 2 Inc = 0.30610510061136, TourLength = 3.094150977173115 Iteration 8: Tour: 0, 8, 1, 6, 7, 3, 5, 4, 2 Inc = 0.14458036109977285, TourLength = 3.2387313382728875 Iteration 9: Tour: 0, 8, 1, 6, 7, 3, 9, 5, 4, 2 Inc = 0.0036633983050865515, TourLength = 3.242394736577974
Question: > How many points will be taken off the program if the city list and > total tourlength is incorrect, but everything else wanted for the > program is there? Answer: Correctness is very important. I will not be able to distinguish between someone who has spent a lot of time debugging versus someone who has simply slapped together a program that runs and does something close to correct. Debugging is a special skill that you are expected to experience and learn from.