EECS 2011Z (Winter 2018) FUNDAMENTALS OF DATA STRUCTURES
CB 121 Tues Thurs 13:00 - 14:30
Instructor Information:
James H. Elder 0003G Lassonde 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.
To get the most of the lectures I recommend that you keep your laptops etc in your bags. Recent research has shown that students who use laptops in class get lower grades.
Slides:
- Introduction
- Asymptotic Analysis
- Linear Data Structures
- The Java Collections Framework
- Recursion
- Trees
- Priority Queues and Heaps
- Maps and Hash Tables
- Midterm Review
- Loop Invariants and Binary Search
- Search Trees
- Comparison Sorts
- Linear Sorts
- Graphs - ADTs and Implementations
- Graphs - Depth First Search
- Graphs - Breadth First Search
- End of Term Review
Camtasia Recorded Lectures
Lecture 1. Thurs, Jan 4 2018
Lecture 2. Tues, Jan 9 2018 Part 1 Part 2
Lecture 3. Thurs, Jan 11 2018
Lecture 4. Tues, Jan 16 2018
- Unfortunately the last few minutes of this lecture got cut off - my apologies.
Lecture 5. Thurs, Jan 18 2018
Lecture 6. Tues, Jan 23 2018 - Due to a technical glitch, no recording of this lecture is available.
Lecture 7. Thurs, Jan 25 2018
Lecture 8. Tues, Jan 30 2018
Lecture 9. Thurs, Feb 1 2018
Lecture 10. Tues, Feb 6 2018
Lecture 11. Thurs, Feb 8 2018
Lecture 12. Tues, Feb 13 2018
Lecture 13. Thurs, Feb 15 2018
Lecture 14. Thurs, Mar 1 2018
Lecture 15. Tues Mar 6 2018
Lecture 16. Thurs Mar 8 2018
Lecture 17. Tues Mar 13 2018 - Unfortunately the last few minutes of this lecture got cut off - my apologies.
Lecture 18. Thurs Mar 15 2018 - Due to a technical glitch, no recording of this lecture is available.
Lecture 19. Tues Mar 20 2018 - Unfortunately the last few minutes of this lecture got cut off - my apologies.
Lecture 20. Thurs Mar 22 2018
- Due to a technical glitch, no recording of this lecture is available.
Lecture 21. Tues Mar 27 2018
Lecture 22. Thurs Mar 29 2018 - Unfortunately only the first 20 minutes of this lecture got recorded - my apologies.
Lecture 23. Tues Apr 3 2018 - This includes the lecture on breadth-first search, but not the problem-solving tutorial.
Assignments:
Assignment 1 (Due Thurs Jan 25 11:59pm) Solutions Your Marks (Select 2011Z)
If you have concerns regarding the grading of Assignment 1, please contact Mahdieh Abbaszadegan, who is the lead TA for Assignment 1 grading.
Assignment 2 (Due Tues Feb 20 11:59pm) Solutions Your Marks (Select 2011Z)
If you have concerns regarding the grading of Assignment 2, please contact Amin Omidvar, who is the lead TA for Assignment 2 grading.
Assignment 3 (Due Mon Aug 13 11:59pm) Grading programs Your Marks (Select 2011Z)
If you have concerns regarding the grading of Assignment 3, please contact Amin Omidvar, who is the lead TA for Assignment 3 grading.
Assignment 4 (Due Tues Aug 21 11:59pm) Grading programs Your Marks (Select 2011Z)
If you have concerns regarding the grading of Assignment 4, please contact Amin Omidvar, who is the lead TA for Assignment 4 grading.
For help on completing the assignments (not grading), please email one of the following TAs:
Vitaliy Batusov
Hakki Karaimer (Office Hour: Tues 11:45 - 12:45 in LAS 2052)
Stanley Liang
Problem Sets (not graded):
Problem Set 1 (Asymptotic Analysis) Solutions
Problem Set 2 (Linear data structures, recursion, trees, priority queues, heaps)
Solutions
Problem Set 3 (Asymptotic analysis, hashing, BSTs, comparison sorts, linear sorts, graphs)
Solutions
Midterm Solutions Your Marks
(Select 2011Z)
Final Exam 1: Wed Apr 11 2pm - 5pm Aviva Tennis Centre
Final Exam 2 (remediation): Wed Aug 22
2pm - 5pm LAS B,C
A tutorial to help you prepare for the final exam will be held Fri Aug 17th in ACE 204 3:30pm-5:30pm. The tutorial will focus on Problem Set 3.
Announcements:
This is a stack: the most recent announcements are at the top.
- Aug 27. For those who wrote the final exam in April, final exam grades have been posted. (Select 2011Z)
- Aug 27. Grades for Assignment 4 have been posted. (Select 2011Z)
- Aug 22. Grades for Assignment 3 have been posted. (Select 2011Z)
- Aug 9. For those students who did not write the final exam in April, the remediation final exam has now been scheduled: Wed Aug 22
2pm - 5pm LAS B,C
- Aug 7. Optional labs will be held for Assignments 3 and 4 in LAS 1006. Assignment 3: Thurs Aug 9 9.:30am-11:30am. Assignment 4: Thurs Aug 16 9:30am-11:30am.
- Aug 3. For those who did not write the final exam in April: You will write the final exam at the end of the remediation period (Aug 22-31). The exact date and time will be announced shortly.
- A tutorial to help you prepare for the final exam will be held Fri Aug 17th in ACE 204 3:30pm-5:30pm. The tutorial will focus on Problem Set 3.
- Jul 30. Final due dates for Assignments 3 and 4 have now been posted - please see above.
- Jul 30. Grades for Assignment 2 have now been posted. (Select 2011Z)
- Jul 30. To all EECS 2011Z students: Thank you for your patience. We are now finalizing details of remediation process for this course. Please stay tuned for details.
- Jul 30. To our valued EECS 2011 TAs: welcome back!
- Apr 3. The solutions for Problem Set 3 have been posted.
- Apr 1. Problem Set 3. There are two typos. I have posted a corrected version. (This is not an April Fool's joke!):
- Problem8(a): "larger than the difference between any two keys" should read "maximally distant from all keys".
- Problem 17: On Line 8, deleteEdge(i) should be deleteEdge(i,j) and deleteIncidentEdges(i,j) should be deleteIncidentEdges(i).
- Mar 30. A4Q2. In the code I posted March 27th, the package A4Q2S was mistakenly imported at the top of each source file. You should delete this line, or download a fresh copy of the source code, which has now been corrected.
- Mar 30. A4Q2. Please note that you do not need the entire net.datastructures library - I have extracted the subset you need for this problem.
- Mar 28. Problem set 3 has been posted (see above). Solutions will be posted by Apr 4th. Professor Datta has also posted some suggested practice problems from the textbook here.
- Mar 27. The grading programs for Assignments 3 and 4 have now been posted (see above).
- Mar 27. Assignment 4 has been posted!
- Mar 27. A3Q2. Please use the marathon2017.csv file to test your algorithm, located here. (Some problems have been reported with another version of the data file that I inadvertentaly included in an earlier version of the posted source code package.)
- Mar 26. We have decided to extend the due dates for Assignments 3 and 4 until after the strike is over. However, for those students who have been continuing with the course, we strongly encourage you to complete the assignments according to the original schedule in order to be prepared for the final exam on Apr 11th. Please note that solutions will be discussed in class but will not be posted until the strike is over.
- We are not prepared at this time to transfer the weight of the assignments to the final exam.
- Mar 23. A3Q2. Many students have found that DoubleProbeHashMap occasionally throws an exception at apparently random times. The reason is that key.hashCode() returns an integer that can sometimes be negative. You must therefore take its absolute value before using it in your secondaryHashValue method. My comment for the method was therefore misleading. It should read: "Returns value of secondary hash function h'(k) = q - k mod q, where k is the absolute value of the hash code for key." I will extend the deadline again to this Sunday Mar 25 11:59pm to compensate for this error.
- Mar 20. The deadline for Assignment 3 has been extended to 11:59pm Saturday, Mar 24th.
- Mar 9. A3Q1. TreeMap is written so that it can be specialized to maintain a balanced binary search tree, however we are using the generic, unbalanced version. Note that you should still be able to satisfy the O(h+m) requirement without a balanced tree.
But in practice we would want to use a balanced tree for this kind of application.
- Mar 9. A3Q1. TreeMap returns a PositionalList. You should instantiate this as a LinkedPositionalList. This class has been provided to you.
- Mar 7. Assignment 3 has been posted! Due Wed Mar 21st.
- Mar 7. Test case results for Assignment 1 were (finally) emailed to you this morning. Please let me know if there are any issues with what you received.
- Mar 5. The lecture for EECS 2011Z will be held at the normal time and place tomorrow and until further notice.
- Mar 5. The midterm scores have been posted on ePost. Your graded midterm will be emailed to your @my.yorku.ca email address. The posted final score is a scaled version of the raw score written on your midterm: final score = round(6.5965 + 1.0409 x raw score).
- Feb 28. York University is hosting a Vision Science Summer School for undergraduates June 4-8, 2018. All expenses are paid. The deadline for application is March 1st. Please consider applying if you have interests in vision science. More information can be found here.
- Feb 21. A2Q2. If no patients have waited longer than the maximum waiting time and two patients are tied for the highest priority your algorithm may choose either one. Similarly, if two patients are tied for the longest wait time and this exceeds the maximum wait time, your algorithm may choose either one.
- Feb 19. The deadline for Assignment 2 has been extended to Fri Feb 23 11:59pm
- Feb 19. York University is hosting a Data Analytics & Visualization Summer School for undergraduates July 3-6, 2018. All expenses are paid. The deadline for application is March 26th. Please consider applying if you have interests in data analytics, data science, machine learning, digital media, etc. More information can be found here.
- Feb 18. A2Q2. APQ.remove should use the ArrayList remove(p) method to remove the last entry in the heap, where p is a position. (Not remove(), which does not exist).
- Feb 18. Checking your grades: There have been some technical problems with ePost. To check your grades, please log in using your EECS user ID (not Passport York), and select 2011Z (not 2011). If you have concerns regarding the grading of Assignment 1, please contact Mahdieh Abbaszadegan, who is the lead TA for Assignment 1 grading.
- Feb 17. For A2Q2: If the priority queue is empty, poll(), like peek(), should return null.
- Feb 13. The next lab for Assignment 2 will be held this Thurs Feb 15 6pm-8pm in LAS 1006.
- A tutorial to help prepare for the midterm will be held next Tues Feb 20 3:30-5:30pm in Bergeron 313
- Jan 21. A second lab for Assignment 1 will be held Tuesday Jan 23rd in LAS 1006 from 3:30-5:30pm.
- Jan 21. For conceptual help on integral images (Q2), see https://en.wikipedia.org/wiki/Summed-area_table.
- Jan 21. There was a typo in the signature for MaxStack in the file MaxStack.java for A1Q3.
There should be an <E> after Comparable. The posted file has now been corrected - please download a fresh copy.
- Jan 20. For this week only, my office hour on Thurs Jan 25 is moved from 2:30-3:30 to 12:00 - 1:00.