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

TAs:

Ron Tal
Tel: (416) 736-2100 ext. 66117
Email: rontal@cse.yorku.ca
Office Hour: Tuesday 14:30-15:30 in CSEB 2013, or by appointment

Paria Mehrani
Tel: (416) 736-2100 ext. 66117
Email: paria.mehrani@gmail.com
Office Hour: Wednesday 13:00 – 14:00 in CSEB 2013, or by appointment

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.

1. Introduction
2. Asymptotic Analysis
3. Linear Data Structures
4. The Java Collections Framework
5. Recursion
6. Trees
7. Priority Queues and Heaps
8. Maps, Hash Tables and Dictionaries
9. Search Trees
10. Sorting
11. Graphs
12. End of Term Review

Announcements:

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

• Sun Apr 29. There was an error in the correspondence between CSE numbers and grades posted on ePost. This problem was fixed at 10:20pm Sun Apr 29. The posted grades should now be correct.
• Sun Apr 29. There was an error in the marks posted for the assignments. This error was fixed at 12:30pm Sun Apr 29.
• Sun Apr 29. I have posted all unofficial recorded marks for the assignments, midterm and final. The marks are posted using ePost: you must enter your CSE username and password for access. All marks are out of 100. I have not posted the final grades, as we are still finalizing these. If you notice any errors in the posted marks, please contact me immediately. Have a great summer!
• Sat Apr 14. For the final exam, you are responsible for all material up to and including all material on unweighted graphs (i.e., up to Slide 171 in the Graphs lecture). You are not responsible for the later material on weighted graphs.
• Sat Apr 14. Final Exam Practice Problem R-10.21b) The solution shown is the solution only after the search for key = 1. Thanks to Jonathan Lebon for catching this.
• Tues Apr 10. The solutions for the final exam practice questions have been posted (see above).
• Tues Apr 3. Practice Questions for the final exam have been posted.
• Tues Apr 3. Solutions for Assignment 4 have been posted.
• Tues Mar 27. The assign4 submit directory has been posted.
• Sun Mar 25. A4Q1. There was a typo in the last line of the test program testYorkArrays - the wrong array was being printed after sorting with QuickSort. I have posted a corrected version.
• Sun Mar 25. A4Q1. If your input array is empty (length 0), your sorting methods should return an empty array (length 0).
• Sat Mar 24. A4Q1. The test program testYorkArrays contained a testcase where it called mergeSort with a null input. That should have been placed in a try/catch clause so that the test program would complete. I have fixed this and posted the updated version. Please use this new version of the test program to validate your code.
• Thurs Mar 15. Assignment 4 has been posted (see above).
• Thurs Mar 15. Solutions for Assignment 3 have been posted (see above).
• Sat Mar 10. A3Q1. Bhanu Bandaranayake has raised an important point. It can be argued that the implementation of BinarySearchTree<K,V> in net.datastructures is not perfect. It would be better implemented as BinarySearchTree<K extends Comparable, V>. If one tried constructing a binary search tree with a non-comparable K, it would lead to an exception down the line. In my test cases, I only use keys K that are comparable. So it is ok to assume comparable K for this question.
• Wed Mar 7. Unfortunately I will have to cancel my office hour this Thurs Mar 7. Please email me with any questions, or to make an appointment.
• Tues Mar 6, 2012 A3Q1.Note that there may be no nodes in the tree with keys that match k1 and/or k2, but findAllInRange should still report all keys between these two values. I have updated the description of findLowestCommonAncestor to be more clear:  "findLowestCommonAncestor returns the lowest position in a subtree that is a common ancestor to all positions with keys between k1 and k2, inclusive.
• Wed Feb 29, 2012(Leapday!) A3Q2. We were missing the definition of the UnmatchedArrayPairException. I have now included it. I've also eliminated the unnecessary import of net.datastructures.
• Sat Feb 25 2012 I have posted the midterm solutions - see above.
• Mon Feb 20 2012 Assignment 3 has been posted (see above). Happy Family Day!
• Sat Feb 18, 2012 My office hour for Thurs Mar 1 is cancelled. Please email me to make an appointment if you need to see me that week.
• Tues Feb 14, 2012. I have posted solutions to the midterm practice questions (see above).
• Tues Feb 14, 2012. Those of you who lost 2.5 marks on Q5 of the Analysis component of Assignment 1 for using big-Oh notation instead of Theta-notation: Please bring your assignment to the midterm Thursday and give it to Paria, Ron or I before the midterm starts. Alternatively you can see Paria during her office hour Wed. We will restore these marks.
• Mon Feb 13, 2012. I have posted some practice questions for the midterm (see above).
• Mon Feb 13, 2012. The Assignment 2 solutions have now been posted (see above).
• Thurs Feb 9, 2012. The Assignment 1 solutions have now been posted (see above).
• 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 testLinkedBinaryTreeLevel 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.