CSE 241 Frequently Asked Questions (FAQs)

Homework 4 Related Questions:

Why does the practice problem like problem 1 include different information in each B-tree node?

In the text book it discusses included a parent pointer and a bit indicating if the node is a leaf node, and this node configuration is used for the practice problem that is like problem 1. In my presentation of B-trees, I didn't include either since they aren't really needed. I choose to include them in the practice problem so that it wasn't too similar to Problem 1 in Homework 4.

For the homework problem, you should include in each B-tree node exactly what is stated in the assignment.

For Problem 3c, should we use the original binary heap (before the insertions), or the binary heap obtained after the insertions?

If you've already completed this problem, whichever binary heap you used is fine. If you haven't already done the problem, please perform the extractMin on the original binary heap (before the insertions).

Lab 3 Related Questions:

In the sample output provided for Part 5, is there an event missing?

Yes, the output shown was based on an earlier version of the allEvents data set that did not include events from the WU Sesquicentennial web page. In particular, the following event that was added from the WU Sesquicentennail web page does include the word "last".

1963: The last streetcar serving the campus of Washington University ended its run

Lab 1 Related Questions:

Could you clarify what we are to do for Part 2?

You are to compute the average number of probes used by the marked get method call made at the end of FastMatch and compare it to the expected number of probes derived in the text. Please see item number 5 for "What to Submit" for more details.

The definition of a probe given in the lab assignment, just discusses the contain method (which was called containsKey). Each time you examine an entry in the hash table with the get method, it is also called a probe. (If it helps you, feel free to replace contains in the description of Part 2 with get.)

The provided code contains the line:

static final MappingRecord DELETED = new MappingRecord("");     // sentinels for deleted

Where is the MappingRecord class defined?

It is your job to define this class. Since the deleted sentinel is a MappingRecord, it must be the type for the object referenced by each element of the hash table that should encapsulate the key and the bucket holding all items that have a mapping from the key. (Your are welcome to replace the line shown above by whatever you would like.)

How do I increase the memory avaialble with Java?

Use the command line arguments -Xms150m -Xmx150m. This will work up until about 2,500,000, if you want you can use a larger value (200m, 300m, 400m, 500m, ..) up until the memory you have on your computer. If you are using Eclipse, under the Run menu pick "run..." and then put this under the VM arguments under the arguments tab.

When doing part 3, it is taking a long time to start with n=25 and increase n in increments of 500. Is this necessary?

No, you do not need to do that many runs. Please pick a larger increment for n. All I ask is that your graph include at least 10 values of n for each algorithm and goes to a value of n in which the brute force algorithhm at least takes a couple of minutes.

Could you go over what I should submit for Lab 1?

All of the below information is in the Lab 1 assignment but it may be easier for some to have it stated separtely in html form. Here is a detailed list of what must be submitted for each portion. In addition all of the files required to compile your program (including the makefile for those using C++) must be uploaded.

What is the constant built into Java for the largest integer?

Use either java.lang.double.MAX_INTEGER or java.lang.double.POSITIVE_INFINITY.

I can't figure out how to set the command line arguments to get a transcript file from my Java program. Until I figure out how to do this, is there any other way for me to proceed with this lab?

Yes, to create a transcript that is saved in the file transcript.txt, add the following line at the start of main:

Terminal.startTranscript("transcript.txt");

Similary, if you want the data to be read from the file sample-pointfile then replace the portion of the driver that generates the random point set by:

points = PointReader.readXYPoints("sample-pointfile");

The the closest pair has distance zero when there are two identical points. Is this correct answer or should the closest two points with distance at least zero be returned?

If there are two different points with the same x and y coordinates then the correct answer is to return such a pair of points (that will have distance 0).

Return to the CSE 241 Home Page