CSE 2011Z (W) FUNDAMENTALS OF DATA STRUCTURES

ROSS N203 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 will generally post the slides for each lecture the night before class. However, 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. Midterm Review
10. Search Trees
11. Sorting
12. Graphs
13. End of Term Review

Assignments:

All questions of Assignment 2 has now been posted. There are only 4 questions.

• Assignment 1
• Assignment 2

Exams:

• Practice Problems for Midterm
• Solutions for Midterm Practice Problems
• Midterm Solutions
• Final Exam: 2:00-5:00 pm Fri Apr 16 CSE B
• Final Exam Practice Problems
• Solutions for Final Exam Practice Problems

Click here to see your unofficial grades for the course! 

Announcements:

• Thurs Apr 22 Please click on the link above to get your unofficial grades for the course. Have a great summer!
• Sun Apr 11 There was an error in the solution to R-10.10 in the final exam practice questions. I have corrected it and posted the corrected version of the solution set. Thanks to Alex Naumov and Doug Scheurich for spotting this.
• Sat Apr 10 The Search Tree slides that were posted were out of date. I have updated them with the correct version. Thanks to Doug Scheurich for noticing this.
• Sat Apr 10 Solutions for the final exam practice problems have been posted!
• Mon Apr 5 The final exam practice problems have been posted!
• Mon Apr 5 In Thursday's class, Doug asked a question about binary search trees, where every internal node has two children, which may be either internal nodes or external nodes. In my answer, I confused the terms 'complete' and 'proper'. So let me set the record straight here:
  • A binary tree is said to be complete when there are no gaps or holes. In other words, all levels except the bottom level are full, and in the bottom level, all the nodes are on the left. The rightmost node of the bottom level may have only one child, but it must be a left child. Heaps have this property, and thus are complete.
  • A binary tree is said to be proper when every node has either 0 or 2 children.
  • Thus a binary search tree (as we implement it, with external nodes) is always proper, but is not necessarily complete.
• Wed Mar 1Final Exam: 2:00-5:00 pm Fri Apr 16 CSE B
• Tues Mar 9 Assignment 2: Your programs should handle unusual input in a reasonable fashion:
  • Q1: findAllInRange
    • If k2<k1, should return a null list
    • If k1<min(k) or k2> max(k), should return list of entries from [min(k)...k2] or [k1...max(k)], respectively.
  • Q4: kthSmallestOfUnion should throw a RankOutOfRangeException if k is less than 1 or more than twice the length of the arrays.
  • Mon Mar 8 Assignment 2: All questions have now been posted. There are only 4 questions.
• Sat Mar 6: Assignment 2 Q1: There was a mixup in the name of the new class (rangeBST vs BSTRange). This has now been fixed. Thanks to Michael Larin for pointing this out.
• Fri Mar 5: The first question of Assignment 2 has been posted!
• Thurs Mar 4: The midterm solutions have been posted.
• Thurs Mar 4: Office hours for Ron Tal on Tues Mar 9 have been cancelled. Please email him if you wish to make an appointment at another time.
• Thurs Feb 4: The midterm will be Tues Feb 23 1:00-2:15 in Vari Hall C
• Mon Feb 1: Both TAs (Ron Tal and Serene Wong) will be present in the PRISM lab (CSEB 1006) tomorrow, Tues Feb 2 from 14:30-16:30 for the scheduled practice lab. So you will NOT find Ron in CSEB 2013 during his office hour (Tues 14:30-15:30) this week.
• Mon Feb 1: Assignment 1. I have updated the comments for the test programs for each question to indicate the correct output.
• Mon Feb 1: Assignment 1, Question 2: Clarification on error-checking. Your implementation need only support operands that are one-character lower-case letters (no numeric constants), and the operators +, -, * and /, as well as round brackets ( and ).  Spaces between characters in the infix expression should be ignored. Any other symbol should generate an InvalidInfixExpressionStringException. However, you do NOT have to detect other kinds of invalid infix expression strings:  you can assume the expressions are valid.
• Sun Jan 31: Assignment 1, Question 5: The interface for push in Class minStack is public E push(E element). This is different from the push ADT defined by the book and in my slides, which does not return anything (i.e., public void push(E element)). I am following here the Stack class provided by java.util. Here, push returns the element just pushed onto the stack, i.e., element in push(E element). Please follow this convention.
• Thurs Jan 28: The statement of Assignment 1, Question 2 was a bit misleading. The last expression should read z x y + *, not x y + z *.
• Thurs Jan 28: The method project of Assignment 1, Question 1 should run in O(m+n) time, where m and n are the number of non-zero elements in the two vectors.
• Thurs Jan 28: The method kPairSum of Assignment 1, Question 3 should run in O(n) time, where n is the number of elements in the array.
• Wed Jan 27: TA Ron Tal will hold an office hour tomorrow Thurs Jan 28 3:30-4:30 in CSEB 2013, to make up for the office hour cancelled on Tues.
• Tues Jan 26: there was a bug in the constructor for SparseNumericVector, in file SparseNumericVector.java for Assignment 1. The second call to SparseNumericElement should be SparseNumericElement(1, 0) NOT SparseNumericElement(-1,0). The posted code has been fixed.
• Mon Jan 25: due to illness, TA Ron Tal's office hour for Tues Jan 26 is cancelled.