Web page contents:

General Information

Learning Outcomes

• 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, self-adjustment, 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. Self-adjustment 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

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

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.

Announcements

• (May 2) You can check your grades on all pieces of work by logging into a departmental unix machine and typing "courseInfo 4101 2018-19 W". Come see me if you would like to view your exam or pick up assignments.
• (Apr 1) Clarification for Assignment 8: the set up for part (c) is the same as for parts (a) and (b), except for anonymity. Thus, the counter implementation is restricted to only using reads and writes of shared memory.
• (Mar 28) As mentioned in class today, there will be a bonus quiz in class on Tuesday. Any material from the whole course may be included. For the quiz, you may bring one 8.5-by-11-inch sheet of paper with handwritten notes on both sides.
• (Mar 28) For the exam, you will also be allowed one 8.5-by-11-inch sheet of paper with handwritten notes on both sides.
• (Mar 27) The Mar 13 announcement below about the bug in the Delete code has been updated to also recognize that the problem could occur on line 72.
• (Mar 21) Please fill out a course evaluation online at this link. They are available from March 21 to April 4.
• (Mar 21) Typo in solutions to assignment 6. The upper bound is correct, but we could make it tighter: In 4(d), the rightmost column for line 74 should be 2-a and 2-2a (instead of 3-a and 3-2a). This means that we could choose smaller constants a=1 and b=4 in part (e), yielding an amortized bound of 13 per insert in (f).
• (Mar 14) I will have a "review session" on Friday, April 5 in Room 105 of Founders College, starting at 2pm. This optional session is a chance for you to ask questions prior to the exam and listen to other students' questions.
• (Mar 13) Due to popular demand, the deadline for Assignment 6 will be extended to 11:30 on Tuesday, March 19.
• (Mar 13) A student found the bug I inserted into the code for DELETE(k) of Assignment 6. The problem occurs when line 72 or 74 moves key k from current into the current's child next. If this happens, found will no longer point to the node containing k. To repair the bug, we should update found to be next if the key moved in line 72 or 74 is k.
• (Mar 11) Alumni series: Nima Shahbazi will give a talk on March 25 at 1pm in BRG125 on his use of machine learning to win a million dollars. For more details, see this link.
• (Mar 11) Bug contest update: A student has identified a bug in the code for Assignment 6: on line 71, "more than" should be replaced by "at least".
• (Mar 8) There was a (big) mistake in my solution to question 2(a) of Assignment 5 that I handed out yesterday. Revised solutions will be handed out in the next class.
• (Mar 7) I will have an extra office hour on Mar 18 at 13:00-14:00 since there is a test on Mar 19. (The office hour on Mar 19 will be cancelled because I have to go to a meeting.)
• (Mar 1) For assignment 5, question 2, intepret "between ymin and ymax" in the inclusive sense: i.e., an object whose y value is equal to ymin or ymax is a candidate to be returned for a QUERY operation.
• (Mar 1) For the test on Mar 19, you are permitted to bring one 8.5-by-11-inch sheet of paper with handwritten notes on one side of the paper.
• (Feb 21) I'm cancelling today's office hour too, because I'm sick this week.
• (Feb 19) Today's office hour is cancelled. Sorry for the short notice.
• (Feb 12) The university is closed on Feb 12 due to the snowstorm. The test that was scheduled for Feb 12 will instead be held in class on Thursday, Feb 14.
• (Feb 9) For assignment 4, question 2, assume that the graph representing the initial highway network is provided in an adjacency list representation. In other words, the nodes are labelled 1..n and for each node i, there is a list E[i] of edges of the form (i,j), sorted by j.
• (Jan 25) For the test on Feb 12, you are permitted to bring one 8.5-by-11-inch sheet of paper with handwritten notes on one side of the paper.
• (Jan 24) The deadline for assignment 3 has been changed to 11:30 am on Thursday, Jan 31.
• (Jan 21) If you are interested in research opportunities this summer, see this link. Some of the deadlines are coming up soon.
• (Jan 10) Typo on assignment 1, question 1(f): "heap" should be "priority queue".
• (Jan 10) For assignment 1, question 1(e), you may assume as a precondition for the {\sc Insert} operation that the item being inserted is not already in the priority queue.
• (Jan 8) There will be no office hour on Thursday, January 17.
• (Jan 8) The date of Test 1 has been moved to February 12 so that you can attend Richard Stallman's colloquium

Important Dates

First class	Thursday, January 3
Test 1	Thursday, February 14 (revised date)
Reading week (no classes)	February 18-22
Last date to drop course without receiving a grade	Friday, March 8
Test 2	Tuesday, March 19
Last class	Tuesday, April 2
Last date to withdraw from course (receiving W on transcript)	Wednesday, April 3
Exam period	April 5-20

Resources

Textbook

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press & McGraw-Hill, 2009. For solutions to some of the textbook's exercises and known bugs in the text, see the textbook's web page. Copies of the text are on reserve at the Steacie Library. You can also 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.
• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 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

Course Handouts

• Notes from first class on ADT specification.
• Test 1 from a previous year for practice
• Test 2 from a previous year for practice
• Exam from a previous year for practice

Updated May 2, 2019