CSE 2011Z

CSE 2011Z (W) FUNDAMENTALS OF DATA STRUCTURES

TEL 0001 Tues Thurs 13:00-14:30

Instructor Information:

James H. Elder 0003G Computer Science and Engineering Building
tel: (416) 736-2100 ext. 66475 fax: (416) 736-5857
email: jelder@yorku.ca website: www.yorku.ca/jelder

Office Hour: Thursday 14:30-15:30

Syllabus

Lectures:

I reserve the right to make changes to the lectures up to the time of the class. Small changes may also be made after class, e.g., to correct errors. I will indicate in each set of slides the date they were last modified: please verify that you have the most recent versions.

Assignments:

Assignment 1. Due Tues Jan 24, 11:59pm

Assignment 2. Due Thurs Feb 9, 11:59pm

Exams:

Midterm: Thurs Feb 16, 2012 (In class)
Final: Tues Apr 17, 2012 19:00 - 22:00 (Tentative)

Announcements:

This is a stack: the most recent announcements are at the top.

Wed Feb 8. 2012. The assign2 directory to submit your assignments is now ready. The command is submit 2011 assign2 fname.java.
Wed Feb 8, 2012. The implementation of Positions for binary trees in net.datastructures is a bit subtle.
- BTPosition<E> is an interface in net.datastructures that represents the positions of a binary tree. This is used extensively to define the types of objects used by the LinkedBinaryTree<E> class that LinkedBinaryTreeLevel<E> extends.
- You do not have to implement BTPosition<E>: it is already implemented by BTNode<E>. Note that LinkedBinaryTree<E> only actually uses the BTNode<E> class explicitly when instantiating a node of the tree, in method createNode. In all other methods it refers to the nodes of the tree using the BTPosition<E> class (i.e., a widening cast). This layer of abstraction makes it easier to change the specific implementation of a node down the road – it would only require a change to the one method createNode.
- We use BTPosition<E> in testLinkedBinary to define the type of father, mother, daughter and son, and to cast the returned values from T.addRoot, T.insertLeft and T.insertRight. These three methods are implemented by LinkedBinaryTree and return nodes created by the createNode method.
In LinkedBinaryTreeLevel, you can use the BTPosition<E> interface to define the type of the nodes stored in your NodeQueue. These nodes will be returned from queries on your binary tree, and thus will have been created by the createNode method using the BTNode<E> Class.

Tues Feb 7, 2012 A2Q3. The remove(index) method of SparseNumericVector should return true if the sparse vector contained an element with the specified index, false otherwise. Also, it should throw an exception if the index is either less than 1 or greater than vecLen - 1.

Mon Feb 6, 2012. A2Q3. There were some minor errors in the comments for the test program testSparseNumericVector. I have fixed these - please download the corrected version.
Sun Feb 5, 2012. A2Q3. There was a typo in the assignment instructions: SparseNumericComparator should be SparseElementComparator.
Thurs Feb 2, 2012. A2Q1. Please note that you can use additional methods to solve this problem. For example, your method kPairSum could simply be a 'wrapper' that calls another recursive method with an interface that is more convenient for your recursive algorithm.
Wed Feb 1, 2012. A2Q3. The add(element) method of SparseNumericVector returns a boolean. You should simply return true. We could have designed the interface with a void return, but one advantage of the boolean return is that the code could be changed in the future to handle some unforeseen circumstance that requires a false return, without changing the interface.
Thurs Jan 19, 2012. There have been some questions about packages and java.lang.NoClassDefFoundError exceptions. I believe these are occuring for those not working within an integrated development environment (IDE) like Eclipse. I do recommend working within an IDE, taking advantage of the organization and debugging facilities provided. But if you are compiling and running from the command line, then you are likely compiling your .class files into the same directory as your .java source files. For example, for Question 1, both your .java and your .class files would now be in A1Q1. In this case, you will have to ascend to the parent directory when you run your main program, since the package A1Q1 statement at the top of each file will cause the Java runtime environment to search for all definitions in the ./A1Q1 directory. Yuen Lau has very kindly compiled a tutorial which steps you through this process.
Thurs Jan 12, 2012. A1Q3. Important. For your implementation of MinStack, all three of the operations push(e), pop() and min() must run in O(1) time.
Thurs Jan 12, 2012: A1Q2. Clarification on image clipping: use the rule top = max (0, top), bottom = min(imageHeight - 1, bottom). Similarly, use left = max(0, left) and right = min(imageWidth - 1, right).
Thurs Jan 12, 2012: A1Q1. Your sparse vectors should be able to represent non-zero elements at any location index from 1 to Long.MAX_VALUE.
Thurs Jan 12, 2012 A1 Analysis Question 5. Please specify the running times of add and remove in terms of n, the number of non-zero elements in the vector.
Thurs Jan 12, 2012 A1Q3: The comments in MinStack.java were offset. I have fixed this problem - please download the new version.
Tues Jan 10, 2012. A1Q1: We store the number of non-zero elements of a vector, but not the length of the vector itself (including zero elements.) Note the comments for the project method interface: we assume that the two vectors live in the same space, i.e., have the same dimensionality. But the number of non-zero elements might be very different.
Mon Jan 9, 2012. I have updated the package names and instructions for the programming component of Assignment 1 to be more clear. If you have already downloaded these files, please replace them with the new versions.