CSE 241 Frequently Asked Questions (FAQs)

Homework 6 Related Questions:

For problem #4, when you wrote "n = 5" in the figure, did you mean "b = 5"?

Yes, it should have been "b=5".

For problem #7, do I need to build the graph?

No, you do not. Likewise, you do not need to find the optimal solution in part (b), just describe how you could compute it.

For problem 2b, should the top-level DFS start at A?

This was my intention which is why I said to visit the vertices in the top-level DFS method in alphabetical order. I've heard that some students thought that the intention was that the top-level DFS starts at S, and then continues in alphabetical order after that. If you made this assumption, that is fine. Please just make a note of this on your solution.

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 Related Questions:

For Problem 7a, are you asking us to also prove a lower bound?

No, when I ask for an algorithm and ask you to make it as efficient as you can, I'm just asking you to try and come up with the best algorithm you can. I am not asking you to prove it is optimal. Some of the points will be associated with you coming up with an efficient algorithm.

Lab 3 Related Questions:

In the assignment there is a method containsDate(int date) but in the provided drivers the call made is contains(date), which should it be?

If you are just starting, please just use the the method name contains instead of containsDate. However, if you prefer to change the three calls of the form contains(date) in the interactive driver to containsDate that is also fine. But it wil be less work to just use contains for the method name. (There is another contains method that takes a String as a parameter. This is fine.)

When using the interactive driver, I get an java.util.InputMismatchException. How do I fix this?

This seems to be an error with some systems. Currently there is a line (about line 44) that has:

      Scanner sc = new Scanner(System.in).useDelimiter("\\n");

Change it to:

       Scanner sc = new Scanner(System.in);

The only problem that occurs for not setting the delimeter, is that you will not be able to enter the description of the event to remove an event through the interactive driver. To make this feature work you'll need to use whatever delimiter is consistent with your system for the end-of-line character.

Can I pass a comparator to use for the bucket creation for the TaggedBucketCollectionWrapper?

The updated version of the TaggedBucketCollectionWrapper provides a constructor with a third argument that is a comparator to pass to the bucket constructor when a bucket is created. This constructor requires that the class used for the bucket has a single-parameter constructor where the parameter is a Comparator. If such a constructor does not exist, it can be easily added.

Can I access the comparator defined over the tags that is used by a TaggedCollection?

While this is not necessary, you might find it useful. To do this, in the TaggedCollection interface (goldman.collection.tagged.TaggedCollection.java) add the method

     public Comparator getTagComparator();

Then in goldman.collection.tagged.TaggedCollectionWrapper.java add the method

     public Comparator getTagComparator() {return pairs.getComparator();}

Then for any tagged collection, you can call getTagComparator() to get the comparator that is used to compare the tags.

In my implementation I plan to use a TaggedBucketCollection and would like to use Java generics to specify a more specific type of Collection for the bucket. Is there a way, that I can do this?

If you want to use some specific Collection class (e.g., DynamicArray) in the type information of Java Generics instead of Collection when creating a TaggedBucketCollection, you can allow this by making the following two minor changes to the TaggedCollectionBucketWrapper constructors. (Note: There is no need to do this to complete the lab, but some of you may prefer to do so.) In TaggedCollectionBucketWrapper just replace

     TaggedCollection<T,Collection<E>> 

by

     TaggedCollection<T, ? extends Collection<E>>

So the headers for the two constructors would be as shown below.

     public TaggedBucketCollectionWrapper(
              TaggedCollection<T, ? extends Collection<E>> tc, BucketFactory<E> factory)

and

     public TaggedBucketCollectionWrapper(
              TaggedCollection<T, ? extends Collection<E>> tc, final Class bucketType)

The updated version of the TaggedBucketCollectionWrapper includes this change.

Homework 4 Related Questions:

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

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.

Lab 2 Related Questions:

How should I pick m (the table size) for the Bloom filter?

You should do this exactly the same what as it is done for the provided open addressing bucket mapping. I'll now describe how that is done and the reason for it. For this genomics application, an estimated value (really an upper bound) for the number of elements to insert is provided to the constructor, and also a desired load is provided (as an argument or using a default value). Let capacity be the estimated value for n (i.e., it is the desired capacity for which you are designing the hash table.) Recall that the actual load alpha = n/m (when d = 0), and solving for m yields that m = n/alpha. So setting m = capacity/load where load is the target load is the size needed for the hash table so the actual load matches the target load when n = capacity. The open addressing bucket mapping sets m to be the nearest power of 2 that is at least as big as capacity/load.

What should I use for the target load for the Bloom filter?

Please use 0.25 as the default value for the target load. In particular, for Part II of the lab, please use 0.25. As with open addressing, you also want to allow the application to provide a value for the target load in the constructor. In Part III you are asked to perform tests with target loads of 0.25 and 0.125. You can look at the provided code for the open addressing bucket mapping to guide you. (The only difference is that for open addressing 0.5 is used as the default value, and 0.25 should be used for the Bloom filter.)

Do I need to including resizing the Bloom table in my implementation?

No, you do not. In fact, with just the Bloom filter itself, it would not be possible to resize the table, since the elements are not stored. The only way that you could resize the Bloom filter, would be to have access to the open addressing bucket mapping so that you could iterate through all elements and reinsert them in the Bloom filter. However, you are not expected to do this for the lab.

For Parts I and III, do I need to do any computations by hand?

No, let the computer do your work. As discussed in the lab, you will want to add some methods to the open addressing bucket mapping implementation to support this (e.g., a method to return the actual load, a method to reset and get the value of a probe counter). For Part III, you will also want to add a method to return the actual load. The lab does talk about this, so perhaps it would be good to reread the assignment.

Homework 3 Related Questions:

In Problem 4, what are n and k?

There are n elements to sort each which is an integer in {0, 1, ...., k-1}. So you can think of k as the base when the element is just a single digit. In radix sort, counting sort is applied d times where d is the number of digits.

Homework 2 Related Questions:

In Problem 5, from questions of the form x < A[i], can't we just determine which array elements are greater than x?

Yes, that is correct. There is now way to distinguish whether an element is less than or equal to x. The problem should be asking for a lower bound for the problem of computing which elements are greater than x. Alternatively, you could allow the algorithm to ask if x > A[i].

I think the intention of the problem was clear, but technically one of those two changes is needed.

Lab 1 Related Questions:

Isn't it possible for there to be more than one pair of points that are a closest pair?

Yes. (Part 3 in the lab does discuss this.) You need only output some closest pair. You can break ties arbitrarily.

Are we required to output all the possible solutions?

No. In fact, the divide-and-conquer algorithm could not possibly guarantee that all possible solutions would be found. Why is this?

Return to the CSE 241 Home Page