CSE 241 Frequently Asked Questions (FAQs)

Lab 4 Related Questions:

How can I ensure that in the TaggedBinaryHeap that the tags are comparable?

Your header for the TaggedBinaryHeap should be: 
public class TaggedBinaryHeap<T extends Comparable<T>, E>
Since T is a type, T extends Comparable (versus implementing it). This header will ensure that type T has a compareTo method.

I define the HeapItem as an inner class of TaggedBinaryHeap (as defined in the above FAQ) with a header as follows: 
class HeapItem<T, E>
I get the following warning under <T, E> in the declaration of the HeapItem class: 
"The type parameter T is hiding the type T" and
"The type parameter E is hiding the type E"
But I don't understand what that means nor how to fix it.

Because HeapItem is an innerclass, the types T and E are already defined from the TaggedBinaryHeap class. So what you have done is like declaring a variable of the same name in an inner class as the outer class. The inner class is hiding the variable from the outer class. The same is happening here with the type information, and that is what this error is telling you. To fix it just change the header to: 
Class HeapItem
Java won't let me construct an array of generic type, what should I do?

When you instantiate an array in Java the type must not involve any parameterized types (generics). Instead you must use: 
   Object[] heap = new Object[8];
You will have to cast the objects in the array to their appropriate type to use them.

Can I use goldman.collection.positional.Array instead of Java's built-in array?

Yes, that would be fine.

Can I add a public minTag method for the tagged binary heap that returns the minimum tag (versus the minimum element)?

Yes, you are welcome to add that and any other reasonable public methods you feel would be helpful.

Homework 5:

In the homework, for question 7c, should we use the original heap or the heap that results from 7b?

Either way would be fine. If you already completed this problem, just specify which option you picked. If you haven't already completed it, then please use the original heap since that will make the grading easier since everyone will have the same starting point.

What did you send by email in regards to Problem 3b?

Problem 3b should read: "How would you modify your data structure design for the application described in Part (a) if n = 1,000,000,000,000?"

In your solution for this problem you should maintain that the segment with the earliest beginning time can be located in worst-case or expected case constant time. In addition, you should try to make the removal of the segment with the earliest beginning time as efficient as you can, but constant time removal may not be possible.

Lab 3:

What is the name for the google group that was created for this class?

www-cse241-spring08

I have written an equals method for the HistoricalEvent class but contains still doesn't seem to find an event when it is there?

Is the signature for your equals method: 
boolean equals(HistoricalEvent e)
If so, that is the problem. The default equals method has a signature: 
boolean equals(Object e)
and by change Object to HistoricalEvent you are creating a new equals method but not overriding the one that is used within the Collection contains method. Otherwise, look carefully at your implementation of equals.

I am having trouble importing the code from the CD into Eclipse, what is the process?

It appears that when all default options are used within the newer version of Eclipse when importing a package, that problems do occur. Here are the steps to import the code from the CD (or any other source) into Eclipse:

  1. First create a Java project for the book code.

  2. If you used the default Eclipse settings to create the Java project then you will have a folder called "src" (or "source") within the project.

  3. You must right-click on that folder (not on the project) and select import. You want to pick the import from archive option since you are importing from a zip file. If you instead right click on the project then you will run into problems unless you modify the default for the Eclipse import option to pick "Use project folder root".

  4. I'd recommend you import both the source code (src) and javadoc (doc). You might also want to import the JUnit tests.

  5. Right click, and select "Build Path", and then "Configure Build Path". Then add the Java project to "Projects."

Homework 4 Related Questions:

For the ADT design questions, can we use more than one ADT for a single problem?

Yes, you might find that necessary to satisfy the given requirements.

What is the time complexity in a red-black tree for k consecutive calls to move forward in the iteration order?

In a binary search tree you can prove that any sequence of k calls to advance (moving forward in the iteration order) or to retreat (moving backwards in the iteration order) has worst case time O(h + k) where h is the height of the tree. Thus for a red-black tree (and also for other ordered collection data structures) any sequence of k calls to advance has worst-case time O(log n + k). Most likely you will find this fact useful for the homework. You can use it without proof.

Homework 2 Related Questions:

In Problem 4, what does the variable q represent?

Both occurences of q (in lines 8 and 10) should be replaced by mid.

Homework 1 Related Questions:

In Problem 4b and 4c, should we be using pseudo-code or an English description?

I would recommend that you describe your algorithm using very high-level pseudo-code, in the same style as that used in the algorithm described for you in Problem 3b. You can keep it fairly high-level but it is important that you make it very clear exactly what recursive calls are made, including the parameters.

Return to the CSE 241 Home Page