EECS 4101/5101, Summer 2020
EECS 4101/5101: Advanced Data Structures
Summer 2020
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
General Information
Instructor: Eric Ruppert
Email: [my last name]@cse.yorku.ca (Please use a York email account when sending me email, and start your subject line with "[4101]" or "[5101]".)
Lectures: Tuesdays and Thursdays 11:3013:00 via Zoom. See link to Zoom lectures on the course Moodle site.
Office Hours: Mondays 14:0015:00 and Thursdays 15:0016:00 via Zoom. See link to Zoom office hours on the course Moodle site.
Learning Outcomes
In this course, you will be invited to develop your ability to think clearly and carefully about data structures and the algorithms that operate on them, and to improve your skills in expressing those thoughts about data structures in a precise way.
Data structures are a crucial component of most computer applications. Understanding them is a key ingredient for writing correct and efficient computer programmes.
By the end of this course, you will be able to do the following things.

Describe important classes of data structures (dictionaries, priority queues, disjoint set union) and explain how they work.
Before trying to design your own data structures, it is important to be aware of a good collection of classical ones. They are useful in their own right, but the ideas that underlie them are also useful for new data structures.

Augment data structures to expand their functionality.
If one of the standard data structures doesn't work for the task at hand, it is useful to be able to tweak an existing one to fit your purpose.

Analyze the efficiency of data structures, including the use of amortized analysis and online competitive analysis.
In many cases, there are multiple data structures that could be used to solve a problem. In some cases, it is important to be able to analyze the different options and choose the one that will solve the problem most efficiently. Amortized and competitive analysis are two special types of analysis that are useful in some settings.

Demonstrate knowledge of important themes in data structure design such as persistence, selfadjustment, concurrency.
This course is not just about going through a catalogue of data structures. Certain ideas can be applied in the construction of many different data structures, and we want to understand those concepts too. Persistence deals with maintaining multiple versions of stored data so that old versions can be accessed when needed. Selfadjustment is used instead of carefully rebalancing data structures to improve the shape of the data structure in response to the sequence of operations performed on it. Concurrent data structures allow multiple threads to access the data simultaneously.

Select or design appropriate data structures to help solve problems for algorithmic applications.
The ultimate goal is to ensure that you can find (or build) the right data structure for whatever task you want to solve. You should also be able to justify your design choices and explain why the algorithms that operate on the data structures are correct.
How to Learn This Material
Much of the material in this course is in the same vein as the material of EECS3101. To develop your understanding of the material, it is important to do more than just read the textbook and attend lectures: you should work through exercises.
You can often learn by struggling with problems. However, if you get too stuck or don't know how to begin, help is available. Talk to your classmates (however; see the notes below about academic honesty regarding discussing assignment problems with others). Go to office hours; the instructor is there to help you! You also learn by making mistakes and getting feedback about those mistakes. Just make sure that you use the feedback to improve your understanding.
Groups of students can learn a lot by explaining their solutions to the suggested exercises from the textbook to one another and critiquing the solutions of others. After all, learning how to explain solutions clearly is one of the goals of this course. Seeing where other students' solutions are unclear to you helps you make your own explanations clearer. Be aware that a problem may have many different correct solutions; just because someone's solution is different from yours doesn't necessarily mean that one of them is wrong.
It takes time to build new skills, so it helps if you work on exercises regularly: don't leave all the work to the days right before a test. Similarly, some of the homework assignments will be difficult to finish if you leave them to the last minute.
Academic Honesty
The key to academic honesty for this course is simply this: Solutions that you submit should be your own work.
Although you may discuss the general approach to solving a homework problem
with other people, you should not discuss the solution in detail.
You must not take any written notes away from such a discussion.
Also, you must list on the cover page of your solutions any
people with whom you have discussed the problems.
The solutions you hand in should be your own work. While
writing them, you may look at the course textbook and your own
lecture notes but no other outside sources.
It is not acceptable to try to find the answer to a homework question on the web, put it in your own words and submit it. You may learn a little by doing this, but you will learn much, much more by working on the problem yourself, and the purpose of this course is to help you learn how to design and analyze data structures on your own.
Furthermore, the web will not be available during your exam (or during your job interview at Google), so you should learn to solve problems yourself, instead of relying on others to do your thinking for you.
As time runs out, students are sometimes tempted to get help from other students on assignments in a way that would violate the preceding policy on academic honesty. DO NOT DO THIS! If you do, I will refer the case to the Dean's Office, which will be very unpleasant for you. The assignments are worth very little, so it is not worth risking a sizable punishment. (Furthermore, I have noticed that the students who cheat on the homework assignments almost always fail the tests and exams, so even if I do not catch you cheating, you will likely fail the course if you do not do your own work on the homework assignments.)
It is important that you look at the departmental
guidelines
on academic honesty.
Marking Scheme
 EECS4101  EECS5101 
Homework exercises  30%  30% 
Midterm test  15%  10% 
Oral quiz  10%  10% 
Participation  10%  10% 
Wikipedia assignment (EECS5101 only)  0%  15% 
Exam  35%  25% 
It's a very good idea to type your solutions to homework assignments, since it allows you to edit and polish the answers, but handwritten solutions are also acceptable, as long as they are legible. If you want to type your solutions, LaTeX produces elegantly typeset documents, is available for free, and was built to handle even the most complicated mathematical notation. It can take a while to learn how to use it, but once you do, you will probably not want to type documents any other way.
You should make every effort to make your answers as brief as possible, while still being thorough. Brevity requires careful thought and editing. (Pascal once excused himself for writing a long letter, saying that he did not have enough time to write a shorter one.) Students who write copious amounts usually do not know what they want to say, or are saying it in a very disorganized way.
Usually, an answer to a homework question should fit on one sheet of paper. If you are writing much more than that, you probably have not found the best way to solve it. On tests, your answer should usually fit into the space provided for it.
Technology Used in the Course
If you have technologyrelated accomodation needs, please contact the instructor as soon as possible.
The executive committee of senate requires the following paragraph to be included in the outline of summer 2020 courses:
Several platforms will be used in this course (e.g., Moodle, Canvas, Zoom, etc.) through which students will interact with the course materials, the course director / TA, as well as with one another. Please review the syllabus to determine how the class meets (in whole or in part), and how office hours and presentations will be conducted.
Students shall note the following:
 Zoom is hosted on servers in the U.S.A. This includes recordings done through Zoom.
 If you have privacy concerns about your data, you may provide only your first name
when you join a session.
 The system is configured in a way that all participants are automatically notified when a
session is being recorded within Zoom.
Technology requirements and FAQs for Moodle can be found here.
If available, some online proctoring software or service may be used for tests and exams during this course.
Announcements
 (Aug 17) You can check your participation grade by logging into a departmental machine (like red.cs.yorku.ca) and typing "courseInfo 4101 Participation".
 (Aug 14) There is a 97% response rate for course evaluations, which is probably the best in the whole faculty. Thanks for filling them out. As promised, I'll drop your lowest assignment grade when computing final grades.
 (Aug 7) You can check the grade for your oral test by logging into a departmental machine (like red.cs.yorku.ca) and typing "courseInfo 4101 Oral".
 (July 16) Course evaluations can be filled out at this link from July 30 to August 13. If at least 80% of the students in the class fill out the evaluation, then I will drop each student's worst homework assignment when computing grades. (I can see how many students complete the evaluations, but not which students do, and I cannot see any of the evaluations until after the course is over.)
 (July 16) Btree visualization mentioned in today's class. They also have others at this link.
 (July 8) For assignment 5, before you present your algorithms, you should explain exactly how you are using a BST to represent an integer. (What is stored in the nodes of the BST, what is the key for each node, etc.)
 (July 3) I have to reschedule Monday's office hour to Tuesday July 7 at 4pm.
 (June 25) This handout gives mathematical prerequisites for EECS3101, which are also useful for this course. Mostly, it is material from EECS1019. If you're not feeling comfortable with asymptotic notation, review Chapter 3 of the textbook.
 (June 23) My office hours next week will be a bit different: there will be no office hour on June 29. Instead, there will be an office hour on June 30 starting at 15:00 that will continue until people stop asking questions.
 (May 30) See moodle discussion forum for some clarifications to assignment 2.
 (May 25) The deadline for assignment 1 has been delayed to 7:00p.m. on May 26. There is a link on the Moodle page for the course that provides a way to submit your assignment online.
 (May 23) If you want remote access to the desktop computers in the labs of the Lassonde building, they are available here. See this link for more information.
Important Dates
First class  Tuesday, May 12 
Reading week (no classes)  June 2326 
Midterm test  July 2 
Last date to drop course without receiving a grade  Friday, July 17 
Last class  Thursday, August 6 
Last date to withdraw from course (receiving W on transcript)  Wednesday, August 12 
Exam period  August 1421 
Resources
Textbook
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and
Clifford Stein, Introduction to Algorithms, 3rd edition,
MIT Press & McGrawHill, 2009. For solutions to some of the textbook's exercises and known bugs in the text, see the textbook's web page.
You can access an electronic version of the textbook through the York Library website.
Other References
 Gonzalo Navarro, Compact Data Structures, Cambridge University Press, 2016.
 Peter Brass, Advanced Data Structures, Cambridge University Press, 2008. The York library is trying to make an electronic copy of this book available.
 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete
Mathematics: A Foundation for Computer Science (2nd edition),
AddisonWesley, 1994.
 Pat Morin, Open data structures.
 Hanan Samet, Foundations of Multidimensional and Metric Data Structures, Elsevier/Morgan Kaufmann, 2006.
 Clifford A. Shaffer, Data Structures and Algorithm Analysis, edition 3.2.0.10, 2013.
 Daniel Solow, How to Read and Do Proofs (6th edition), Wiley, 2013.
Reading
This section will be filled in as the term progresses.
Don't fall behind with your reading.
Date  Topics  Reading in CLRS (3rd ed)  Suggested questions, mostly from CLRS (3rd ed) 
May 14 
Introduction 
partial notes 

May 19 
Aggregate Analysis 
17.1 
17.11 to 17.13, 172 
May 19 
Accounting Method 
17.2 
17.21 to 17.23 
May 19 
Potential Method 
17.3 
17.31 to 17.37 
May 26 
Dynamic Tables, including eager doubling/halving (not in text); Binomial Heaps 
17.4 and 19.0, Problem 192 for binomial heaps 
17.43, 192 
Jun 2 
Fibonacci Heaps 
19 
19.21, 19.32, 19.41, 19.42, 193 
Jun 9 
UnionFind Data Structures 
21 
21.21, 21.31, 21.32, 21.33, 21.34, 21.35, 211, 212, 213 
Jun 16 
Binary Search Trees (quick review from EECS2011) 
12.112.3 
12.13, 12.15, 12.24, 12.27, 12.33, 122 
Jun 30 
Random BSTs 
12.4 
12.42, 12.43, 123 
Jul 7 
Red Black Trees 
13 
13.14, 13.16, 13.17, 13.24, 13.32, 13.43, 13.46, 13.47, 133, 134, 174 
Jul 9 
Augmenting Data Structures 
14 
14.13, 14.15, 14.21, 14.22, 14.23, 14.24, 14.36, 142, 173 
Jul 16 
BTrees 
18 
18.12, 18.13, 18.14, 18.21, 18.26, 181 
Jul 21 
Hashing 
review 11.1 and 11.2; read 11.3, 11.5 
11.14, 11.31, 114 
Jul 23 
Dynamic perfect hashing and cuckoo hashing 
Paper on dynamic perfect hashing (available online via this link at York library) or see Section 1.2.5 of this chapter by Pat Morin from the Handbook of Data Structures and Applications; Notes on cuckoo hashing by Rasmus Pagh 

Aug 4 
Lockfree data structures 
Some slides (we won't cover all of them) 

Course Handouts
Updated August 17, 2020