York University

EECS 2011: Fundamentals of Data Structures (Winter 2019)

Winter 2019

EECS Department

Home (tentative grades on ePost)

Course Syllabus

Lectures and Topics

Assignments (A4 tester posted)

Additional Resources



York University

Assignments

Date Assignment Topics Comments and FAQ
Mar 20 Assignment 4
Assignment 4 tester class
The most common problems were toString() failing (NPE) when invoked from an [empty] newly created set and not returning a proper value when performing operations (e.g., if adding was successful).
NOTE: the code was often modified to handle errors caused by failures in other classes. As it was never intended to be maintained, the coding style is horrible.
Tree Sets
TreeSet vs. HashSet
Use "a4" directory to submit.
Due: Apr 3, 23:59.

Q. When implementing the add method, we have to compare the element to be added to the element of the parent, but since we are implementing it using generics, we cannot just compare the two elements, so we need to use Comparable. I was just wondering if this is okay because it was not mentioned in the assignment sheet. So it would be "public class A4Set<E extends Comparable<E>>". Is this okay, or is there another way to compare them?
A. You may just assume the elements that are put into the set are comparable and do a cast:
(Comparable<? super E>)
If the cast fails, it will generate an exception, and it's OK.

Mar 4 Assignment 3
Assignment 3 tester class
Heapsort
Comparison with quicksort
Use "a3" directory to submit.
Due: Mar 18, 23:59.

Q. As storing heap elements in the first spot of the array is inefficient, should we assume that the array we sort contains nothing in location 0?
A. No, you should be able to sort any array of integers.

Feb 2 Assignment 2
Assignment 2 grading test cases
Linked Lists
Time complexity estimates
Use "a2" directory to submit.
Due: Feb 1618, 23:00.


Q. I was wondering if the methods we need to implement in SkipList should throw all the exceptions that are specified in the API, for example,
void add(int index, E element)
throws ClassCastException, NullPointerException, IllegalArgumentException in addition to the IndexOutOfBoundsException.
A. This is not going to be taken into consideration when grading.

Q. I'm having some trouble debugging my SkipList class. There is some odd behavior in the add(int index, E element) function that I can't seem to figure out. Sometimes i get a NullPinterException but not always, it seems to be associated with the random level. I attempted to follow your solution and filled in the add() function as per the Skip List cookbook from William Pugh.
A. You might consider visualizing your list after every insertion - by printing it using the code below (you can put it in toString method temporarily). The code does not follow all the down links (only the head ones), but it might help you catch some discrepancies.
		StringBuffer sb = new StringBuffer();
                sb.append("SkipList of height: " + listHeight + " Size: "+ size +"\n");
                for (Node node = head; node != null; node = node.down){
                        for (Node node2 = node; node2 != null; node2 = node2.forward)
                                sb.append("(" + node2.item + ")-" + node2.distance + "- ");
                        sb.append("\n");
                }
                return sb.toString();
		
Q. What is the difference between the key and the data being stored in each node? Is the key just the index or span-width of the current node?
A. The nodes in our assignment will be different from those in the example in the slides. Key-data pair is used in maps. Given a key, the map Abstract Data Type is to return the data associated with that key.
However, in our case, we have to store data (obviously), and the span width. The latter, however is not treated the way the key is treated in the original. We cannot store indices either - as updating them could easily become O(n), whereas computing indices from the span-widths can be O(log n) on average.

Q. The assignment says to submit one file: SkipList.java -- does that mean we do not need a SkipListEntry class?
A. It's better to make that class a private static class within SkipList. Making it public (and thus submitting 2 classes) is acceptable, but it would be an example of bad coding practices (there is no need for others to know about SkipListEntry).

Q. I still I don’t know how to index and determine the width.
A. the width is the distance to the next element in the sublist at that level. E.g., if you have an element at index 2, and the element after it has an index 6, than the stored width in element at 2 should be 4. That width is used when you do the searching: if you're at 2 and 2+4 <= (index you are looking for) you go right, else you go to the lower level. When inserting, the width is updated (+=1) as you go back up (even if you're not inserting new elements at higher levels).

Q. For the toString() method, do you want us to print out all the elements in the SkipList like how ArrayList does, or do you want us to print out the SkipList with all the levels and nodes like “Figure 1” in the assignment page?
A. toString() should behave similarly to that of ArrayList (or LinkedList, etc.) Those levels in skip list are private - they are not directly exposed to the world in any way.

Q. For assignment 2, does the skip list have to be sorted? If so, how would we compare data of type E and what use would the method add(index, element) be if the user can easily unsort the list with it?
A. You're implementing an indexed version of the skip list.
In such a list, the values stored in the nodes do not even have to be comparable. The relative positions you store them in matter, and it should be possible to insert elements between two existing elements.

Jan 9 Assignment 1
FileContainer.java

FunctionalityCheck.java (for testing your code before submitting; do not submit this file)
Java intro
OOP
Performance measurements
Use "a1" directory to submit.
Due: Jan 25, 23:00.

Just a reminder that your list should be a List - and it should be possible to use it in place of other List-s from the java.util package (like ArrayList).

Do not modify the provided abstract class - your own FileList class will inherit (extend) it.

CORRECTION: to submit use
		submit 2011N a1 file1 file2 file2
		
(section letter N is missing in the assignment instructions)

Q. Does the output of
java ListTester 
have to look exactly like in the example on p.3 of the assignment PDF?
A. No. E.g., printing numbers one-per-line is fine. During marking we'll probably end up redirecting the output to a file:
java ListTester > file
Q. What if the file I'm trying to open already exists?
A. if you open the file in a no-parameter constructor, choose a different name (you might consider using something like System.currentTimeMillis() to name your file).
If it's the file name specified in the constructor parameter, then you should preserve the data of that file and use it as a starting state of your list. E.g., you could potentially re-use the same file when you start some application using your FileList on some future occasion, continuing all the operations from where you left off.

Q. Could you clarify Part 2?
A. (2a) For numbers N = 10, 100, ...
N = 10. Start the timer (e.g., System.currentTimeMillis()). Insert 10 random numbers ranging from 0 to 100 [such that the probability of having a specific value in your list when doing part (c) is 10%] at the end of an empty list and measure the time.
Clear the list (list.clear(); or create a new one). Do the same when inserting at the beginning.
Clear again. Then the same when inserting in random locations (1st number into random location in range 0..1; 2nd into random location in range 0..2 and so on).
Similar for N = 100, 1000. It's quite likely for larger values your list will be way to slow (more than 10-15 seconds); thus, you can stop there.
(2b, 2c). Generate a list of N items; e.g., by inserting N elements at the end of an empty list, like in part (a). Remove the first element N times (the list becomes empty). Record the time it takes to do that.
Generate a fresh list of N items again. Remove the last element N times. Measure the time...
Fresh list. Remove an element from a random location, 0..currentListSize-1.
Fresh list. Remove an element with a random value in the range 0..10N. List should have about 0.9*N elements left after that.
Overall, you can use the same methods with different indices as parameters for addding/removing to/from the beginning/end.

Q. Could you give more examples of how to read and write files in Java?
A. Several ways. Writing:
// Example 1
try{
	randomAccessFile = new RandomAccessFile(fileName, "rw");
	randomAccessFile.setLength(0); //if you want to erase the file before you continue
	}catch (FileNotFoundException x) {
		System.err.println(x);
	}catch (IOException x) {
		System.err.println(x);
}
...
try{
	randomAccessFile.writeBytes(Long.toHexString(Double.doubleToLongBits((Double)e)));
}catch (IOException x) {
	System.err.println(x);
}
//WARNING: You might want to close the file at some point.


//Example 2
try {
	Files.write(Paths.get(fileName), 
		(Long.toHexString((Double.doubleToLongBits((Double)e)))).getBytes(), 
		StandardOpenOption.CREATE, StandardOpenOption.APPEND);
}catch (IOException x) {
	System.err.println(x);
}


//Example 3
file = new File(fileName);
...
PrintWriter out = null;
try
{	out = new PrintWriter(new FileOutputStream(file,true)); //true if you want to APPEND to an existing file
    	out.println(Long.toHexString((Double.doubleToLongBits((Double)e))));
} catch (IOException x) {
	System.err.println(x);
} finally{
	if (out != null) out.close();
}
Reading:
//e.g., when implementing toString()
file = new File(fileName);
...
try {
      	reader = new Scanner(file);
      	while (reader.hasNextLine()){
		...
		doubleValue = Double.longBitsToDouble(Long.parseUnsignedLong(reader.nextLine(),16)));
		...
	}
} catch (FileNotFoundException x) {
       	System.err.println(x);
} finally{
	if (reader != null) reader.close();
}
Q. Can I use an array/ArrayList in my implementation?
A. There is nothing in the discription of the assignment preventing you to do so. However, it might negatively impact the efficiency of some operations. Also, doing so is going to cause your code to utilize more system memory (RAM) when the lists become large (moreover, when using an array, you'll have to handle the resizing of your array). But, again, there is nothing preventing you from using arrays or ArrayLists; it's just that your solution will impose a limitation on the number of elements your list could contain (since disk storage capacity is typically much larger than RAM capacity).

Q. Inserting/removing elements from the middle of the file looks really difficult. Am I doing something wrong? Can you suggest an easy algorithm to add/remove?
A. File operations are tricky and cumbersome, compared to array operations. A simple (however, not very efficient) way to add an element at position k:
create another file. Copy k-1 elements from the old file into the new one. Add the new element to the new file. Copy the rest of the elements to the new file. Remove the old file, rename the new file to use the old name, maybe do some "housekeeping" if needed.