|
EECS Department
Home
Course Syllabus
Lectures and Topics
Assignments (A3 is posted, monitor FAQs)
Additional Resources
|
Assignments
| Date |
Assignment |
Topics |
Comments and FAQ |
| June 5 |
Assignment 1 |
Arrays
Doubly-linked lists
Performance measurements
|
Use "a1" directory to submit.
Due: June 19, 19:00.
You only have to provide no-parameters constructors in your implementations.
E.g., new A1ArrayList() - constructs an empty list of some initial capacity.
Part 2c: in case the description was not clear, you need to use a boolean remove(Object o) method.
Part 2b: the lists at the beginning can be any lists of N items. To remove from a random location in the middle of the list,
generate a random number between 0 and [current list size - 1] and use it in your remove method (just as you would for the corresponding random position insertion stage in part a).
Overall, you can use the same methods with different indices as parameters for addding/removing to/from the beginning/end.
Q. Do we generate measurement table by manually making the table or make a table via System.out.println?
A. via System.out.println
Q. Can we have a public default constructor or it should be private?
A. Yes, your classes' costructors should be public (just like in the existing classes ArrayList or LinkedList).
Q. How can I determine if my code is going to compile correctly on your system?
A. If you can compile your submission by executing "javac *.java" and run it via "java ListTester" you should be fine.
Part 2c: you ATTEMPT to remove N items with random values. Only with some of the values will the action be successful. Thus, the list will not be empty at the end (as in Part 2b, for example).
Q. My source code compiles and runs fine, but it just seems not terminating for super sufficiently large N >= 100000. (actually not only my list but Java's provided lists also don't work)
Therefore, will there be any mark deduction if the program doesn't terminate within certain amount of times? let's say, an hour?
A. To simplify marking, please either modify the testing class to not run for certain larger values of N or limit the time to 15 or 30 s per measurement (In Notes section: In case the operations for larger N numbers take too long (e.g., more than 30 s) you
may reduce the number to a smaller one or eliminate it (so that you will have a range from, say, 1 10 to 100000).
Just a reminder that each of your lists should be a List - and it should be possible to use them in place of other List-s from the java.util package (like ArrayList).
|
| July 6 |
Assignment 2
starting code
|
Trees
AVL Trees
Performance measurements
|
Use "a2" directory to submit.
Due: July 20, 23:59.
Q. For the binary search tree, does it have to be able to add duplicate elements?
A. Yes. I suggest having a simple counter at each node to account for duplicates. Implement the code without duplicates, and then add that functinality later.
Q. And for the implementation of both trees, do we have to stick with TreeSet class? Can we use our own structure to build these trees?
A. The TreeSet references were only put there to illustrate how your code should behave, as Java Collections use balanced trees underneath.
You should definitely use your own structures. You will notice that the behaviour of your implementation will closely resemble the behaviour of the Java's TreeSet.
Regardless, you should not use that code (developed by Sun/Oracle).
Q. In my code I made the generic type in my trees extend the Comparable
interface so that the compareTo method can easily be used to compare the
values. And this also guaranties that only trees of types that are
comparable can be created. But in the SortTester, you used the Number type
and Number doesn't implement Comparable. I was wandering if I could use a
Comparable type like Integer instead in the SortTester
A. I thought about that when I released the assignment, and considered how trees are implemented in Java library.
Basically, you do not want to prevent people from inserting non-Comparable items IF you provide a separate Comparator
( this is not something I required in the assignment).
The way to solve the problem in your case, is to have a brute casting into Comparable:
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
The casting is going to fail (generate an exception) if you try to work with anything non-Comparable.
More on issue: https://stackoverflow.com/questions/480632/why-doesnt-java-lang-number-implement-comparable.
Q. I think I'm doing everything correctly, but everything fails (crashes, exceptions, hangs)...
A. Debugging trees is not trivial. Start with simple BST trees and make sure things work there. Then move to insertion into AVL trees. When that works, finish with AVL remove.
Note that you can start testing sorting (trivial implementation) as soon as BST insert (moderate diff.) works and you have an in-order traversal working (easy-moderate).
To ease debugging, I'm including some code here (feel free to add it as private or as temporary non-private methods in your trees):
/*
This method checks if tree is an AVL Tree
*/
public boolean isAVL(){
return ifAVL(root);
}
protected boolean ifAVL(Node t){
if (t==null) return true;
return isBST() && (Math.abs(height(t.right)-height(t.left))<=1)
&& ifAVL(t.right) && ifAVL(t.left);
}
/*
* This method prints the tree in infix order.
* It indents 3 spaces for every level past the root.
* Used for testing
*/
public void print() {
infixPrint(root, 0);
}
/*
* this method implements print
*/
protected void infixPrint(Node t, int levelCount) {
if(t == null)
return;
infixPrint(t.right, levelCount+1);
for(int i=0; i < levelCount; i++)
System.out.print(" ");
System.out.println("put here whatever fields you want to print from your nodes");
infixPrint(t.left, levelCount+1);
}
Possible result of printing during debugging (tilt your head sideways to the left to visualize the tree):
Array:
[3, 4, 0, 2, 2, 4, 3, 0, 1, 1]
In-order traversal of the tree:
[0][0][1][1][2][2][3][3][4][4]
Tree structure (numbers-keys: height of the subtree, count of duplicate keys):
4:h=0c=2
3:h=3c=2
2:h=1c=2
1:h=0c=2
0:h=2c=2
TreeHeight: 3
Finally, a couple of functions to test if the tree is a valid tree:
/*
* This method exchanges the left and right children of root.
* Note: it breaks the BST property!!!
* It is provided to help test isBST.
*/
public void mirrorRoot() {
Node temp;
temp= root.left;
root.left= root.right;
root.right= temp;
}
/*
* this method returns true if the tree IS a Binary Search Tree
*/
public boolean isBST() {
if (root==null) return true;
Node minAllowed= smallestItem(root);
Node maxAllowed= largestItem(root);
return ifBST(root, minAllowed, maxAllowed);
}
/*
* implements algorithm for previous method
*/
@SuppressWarnings("unchecked")
private boolean ifBST (Node t, Node minAllowed,
Node maxAllowed){
if (t==null) return true;
boolean right, left; //intermediate results
if (t.left==null) left=true;
else if (((Comparable)(t.left.item)).compareTo(t.item)<0 &&
((Comparable)(t.left.item)).compareTo(minAllowed.item)>=0)
left= ifBST(t.left, minAllowed, t);
else left= false;
if (t.right==null) right=true;
else if (((Comparable)(t.right.item)).compareTo(t.item)>0 &&
((Comparable)(t.right.item)).compareTo(maxAllowed.item)<=0)
right= ifBST(t.right, t, maxAllowed);
else right= false;
return left && right;
}
|
| July 24 |
Assignment 3 (updated July 27: typos/clarifications) |
Maps
|
Use "a3" directory to submit.
Due: July 31, 23:59 EDT.
Q. What should I do in Part 1??
A. - generate 2*N random numbers and put them into an array
- insert the first half of the numbers into one map (and take measurements)
- insert the same first half of the numbers into another map (and take measurements)
(after that you can measure the containsXXXX() timings, the first half of the number will be in the maps, and the second one will not).
similar for Strings
Q. In the first part of the Assignment 3, it says that we have to measure the time that each operation takes, which is the total time for
10 operations (10 integer inputs) divided by number of operations (10 in this case). However, since the answer is in milliseconds, all of the
results end up being zero. should I live the answers zero?
A. No, convert them to smaller units (us or ns). Or use non-integer times (like 0.012 ms). us (micro-) = 1/1000 ms, ns (nano-)= 1/1000 us.
(Greek "mu" is usually replaced with a lowercase U whenever Greek characters are unavailable).
Q. I was wondering whether we need to create two different maps to put Integer and String into. Or if we are supposed to place both in the same HashMap, for example.
A. Yes, there should be separate Map objects for Strings and Integers.
|
|
