CSE 2011Z (W) FUNDAMENTALS OF DATA STRUCTURES

LSB 106 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:

Paria Mehrani
Email: paria.mehrani@gmail.com
Office Hour: By appointment

Alireza Moghaddam
Email: alireza@cse.yorku.ca
Office Hour: 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. Loop Invariants and Binary Search
10. Midterm Review
11. Search Trees
12. Comparison Sorts
13. Linear Sorts
14. Graphs - ADTs and Implementations
15. Graphs - Depth First Search
16. Graphs - Breadth First Search
17. End of Term Review

Assignments:

Problem Sets:

Final Exam: : Sun 13 Apr 2014, 19:00 LAS B

Your Current Grades

Announcements:

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

• Mon Apr 7. Unfortunately we were not able to schedule a review tutorial before the final exam.
• Mon Apr 7. Solutions for Problem Set 2 have been posted.
• Sun Apr 6. Grades for Assignment 3 have been posted, and solutions for Assignments 3 and 4 have been posted.
• Sat Mar 29. Problem Set 2 has been posted. The purpose of the problem set is to help you prepare for the final exam. Although it will not be graded these questions are typical of the questions I will put on the exam, so if you wish to do well you should do these problems.
• Sat Mar 29 A4Q2. In CSEPreReqs.java method printCourses, an extraneous variable course was defined. I have updated the posted .java file with this variable removed. Thanks, Simon, for pointing this out.
• Mon Mar 24: A4Q1. There was a typo in testYorkArrays: the package name should be A4Q1, not A4Q1S. I have posted a corrected version. Thanks to Ramil for pointing this out.
• Sat Mar 22: A4 is posted!!
• Sat Mar 15: A3. For Q1, to reduce your workload, I will not test your code on invalid input (e.g., null keys or positions). Thus you do not have to worry about testing for these conditions and throwing exceptions. For Q2, your method kthSmallestOfUnion should throw an exception if the rank parameter k is out of range, as described in the comment.
• Sun Mar 9: A3Q1. To access the left and right children of a position in the binary search tree, note that BSTRange extends BinarySearchTree, which extends LinkedBinaryTree, which provides left(pos) and right(pos) methods to access left and right children of pos.
• Sat Mar 8: A3Q2. SortedArrayPair is written to be generic, so that it will function for any type that is Comparable. For the test program, I elected to use type Integer, but I could have used any other Comparable type. Note that variables of type Integer are objects with methods, including a compareTo method. This would not work for variables of type int, for example, which are not objects and do not provide such methods. Note that for the test program used to grade the assignments, we could elect to use a different Comparable type.
• Fri Mar 7. Assignment 3 has been posted. Note that the due date has been extended to Tues Mar 18.
• Fri Mar 7. The midterm solutions have been posted - see above.
• Thurs Mar 6. Assignment 2 and the midterm have now been graded. Please click the link above to check your marks.
• Wed Mar 5. The final exam schedule has been posted. Our exam is Sun Apr 13 at 19:00 (7pm) in LAS B. It will be a 3-hour closed book exam.
• Sun Feb 23. The Midterm Review has been posted
• Sun Feb 23. Solutions for Assignment 2 have been posted.
• Sat Feb 22 Paria discovered an error in Problem 5 of Problem Set 1. The algorithm runs in max(m, n) time, not min(m, n) time. Thanks Paria!
• Thurs Feb 20 Solutions for Problem Set 1 have now been posted (see above).
• Thurs Feb 13: Grades for Assignment 1 have now been posted. If your code compiles, has the right output and runtime you should get 100% of the marks. If your code fails to compile we generally deduct 50% of the mark. FOR THIS ASSIGNMENT ONLY, if the compilation error was trivial (e.g., wrong package name), we corrected this error and recompiled. WE WILL NOT DO THIS FOR FUTURE ASSIGNMENTS. Please be sure that you use the package name provided (A2Q1 etc.) in the future.
• Wed Feb 12: The first problem set has been posted. The purpose of the problem set is to help you prepare for the midterm. Although it will not be graded these questions are typical of the questions I will put on the midterm, so if you wish to do well you should do these problems.
• Wed Feb 12: A2Q2. Please note that both of your priority queues are based upon heaps, which in turn are implemented as array lists, which in turn are implemented as arrays. We are using array lists only to take advantage of the automatic resizing capability. We are NOT using the add(i, e) or remove(i) methods to automatically shift later elements to the right or left when adding or removing elements in the middle of the list. These operations will NOT preserve the heap property of your heap. Instead you must use the procedures discussed in class for adding or removing an element from a heap.
• Tues Feb 11: The solutions for Assignment 1 have been posted
• Tues Feb 11: I have split the Maps, Hash Tables and Dictionaries lecture in two parts, creating a new lecture entitled Loop Invariants and Binary Search. Please makes sure you have
• the most recent version of these lectures.
• Sat Feb 8: A2Q1: Note that you may create a private method to help you solve this problem.
• Mon Feb 3: Assignment 2 has been posted!
• Sun Jan 26, A1Q2: In the comments for the test program I truncated the expected answers to 5 significant digits. However, the provided toString method you will be using prints the default (maximum) number of significant digits, and notice that there will be very small numerical round-off error. This is expected and will not result in deducted marks.
• Sun Jan 26, A1Q2: In each of the two provided files BoundaryViolationException.java and NullSubImageException.java, there was an erroneous line including the package A1Q2S.*. This line will generate a compile error for you and should be removed. I have updated the posted code for these two files if you wish to download the correct versions.
• Thurs Jan 23, A1Q1: I have specified that your sparse vectors should only have elements with non-zero values. However, I did not specify what you should do if an add(e) message is received and the element e has a zero value. The best option is to simply ignore the message, i.e., do not add the element. This will preserve the sparsity of the vector, and of course will not affect the result of the projection method. I will also accept a solution which adds the entry with zero value, although this does make the vector less sparse. (Thanks to the sharp student who pointed this out!)
• Sat Jan 18: Thanks to all who filled out the Doodle poll. Based on your responses, the lab tutorial has been scheduled for Tues Jan 21 3:00 - 4:50pm in LAS1006.
• Sat Jan 18, A1Q2: For the constructor I am giving you an O(n) memory bound, but I did not explicitly give
  you a time bound. However, you that you should only need O(n) time to run the constructor. Remember that n is the number of pixels in the input image. Clearly therefore you cannot have nested loops if each of them runs over all of the pixels in the image. However, for a 2D image it is common to have an outer loop over rows of the image and an inner loop over columns of the image. The net result is that you visit each pixel in the image once, so this is also O(n).
• Tues Jan 14: 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. If you are working with Eclipse, then all of your .java files for Q1 should be part of Package A1Q1 etc... 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.
• Tues Jan 14: Mr. Sattu has raised an important issue regarding A1Q1. Please note that in the linked list containing your sparse vector, the header and trailer are just dummies, containing no data, and you should ignore their index fields. Any entries you add should thus go BETWEEN the header and trailer. Thus, for example, if you wish to add an element with index 1, it will go immediately after the header sentinel. Similarly, if you wish to add an element with index Long.MAX_VALUE, it will go immediately before the trailer sentinel.