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 must 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). Use the 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.
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 use course materials 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 or using AI tools (such as LLM-based software), 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, AI tools and the web will not be available during your exam (or during your job interviews), 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 is unpleasant for everyone. 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 senate policy on academic honesty and the faculty's academic integrity resources.
EECS4101 | EECS5101 | |
Homework exercises | 15% | 15% |
Test 1 | 20% | 17.5% |
Test 2 | 20% | 17.5% |
Wikipedia assignment (EECS5101 only) | 0% | 10% |
Exam | 45% | 40% |
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.
First class | Monday, January 6 |
Test 1 | Monday, February 10 in CLH K |
Reading week (no classes) | February 17-21 |
Last date to drop course without receiving a grade | Friday, March 14 |
Test 2 | Monday, March 17 in CLH K |
Last class | Wednesday, April 2 |
Last date to withdraw from course (receiving W on transcript) | Friday, April 4 |
Exam period | April 8-25 |
Date | Topics | Reading in CLRS (4th ed) | Suggested questions, mostly from CLRS (4th ed) | Equivalent reading in CLRS (3rd ed) | Equivalent questions in CLRS (3rd ed) |
Jan 6 | Introduction | partial notes | |||
Jan 8 | Aggregate Method of Amortized Analysis | 16.1 | 16.1-1 to 16.1-3, 16-2 | 17.1 | 17.1-1 to 17.1-3, 17-2 |
Jan 13 | Accounting Method | 16.2 | 16.2-1 to 16.2-3 | 17.2 | 17.2-1 to 17.2-3 |
Jan 15 | Potential Method | 16.3 | 16.3-1 to 16.3-6 | 17.3 | 17.3-1 to 17.3-7 |
Jan 15 | Dynamically sized tables, including eager doubling/halving (not in text) | 16.4 | 16.4-4 | 17.4 | 17.4-3 |
Jan 20 | Binomial Heaps | Chapter 19 of 2nd edition | from this link: 19.1-2, 19.2-1 to 19.2-4 | ||
Jan 27 | Fibonacci Heaps | 19 in removed material | from removed chapter: 19-2, 19.2-1, 19.3-2, 19.4-1, 19.4-2, 19-3 | 19.0 | 19-2, 19.2-1, 19.3-2, 19.4-1, 19.4-2, 19-3 |
Feb 3 | Union-Find Data Structures | 19 | 19.2-1, 19.3-1, 19.3-2, 19.3-3, 19.3-4, 19.3-5, 19-1, 19-2, 19-3 | 21 | 21.2-1, 21.3-1, 21.3-2, 21.3-3, 21.3-4, 21.3-5, 21-1, 21-2, 21-3 |
Feb 5 | Binary Search Trees (quick review from EECS2011) | 12.1-12.3 | 12.1-3, 12.1-5, 12.2-4, 12.2-7, 12.3-3, 12-2 | 12.1-12.3 | 12.1-3, 12.1-5, 12.2-4, 12.2-7, 12.3-3, 12-2 |
Feb 12 | Random BSTs | 12.4 in removed material (Randomly Built BSTs) | 12.4-2, 12.4-3, 12-3 | 12.4 | 12.4-2, 12.4-3, 12-3 |
Feb 24 | Red Black Trees | 13 | 13.1-4, 13.1-6, 13.1-7, 13.1-8, 13.2-4, 13.3-2, 13.3-3, 13.4-4, 13.4-7, 13.4-8, 13.4-9, 13-3 | 13 | 13.1-4, 13.1-6, 13.1-7, 13.2-4, 13.3-2, 13.3-3, 13.4-3, 13.4-6, 13.4-7, 13-3, 13-4, 17-4 |
Feb 26 | Augmenting Data Structures | 17 | 17.1-3, 17.1-5, 17.2-1, 17.2-2, 17.2-3, 17.3-5, 17-1, 17-2, 16-3 | 14 | 14.1-3, 14.1-5, 14.2-1, 14.2-2, 14.2-3, 14.2-4, 14.3-6, 14-2, 17-3 |
Mar 3 | Interval trees, treaps, persistence, split and join in RBTs | 17.3, treaps reference | 13-1, 18-2 | ||
Mar 5 | B-Trees | 18 | 18.1-2, 18.1-3, 18.1-4, 18.2-1, 18.2-6, 18-1 | 18 | 18.1-2, 18.1-3, 18.1-4, 18.2-1, 18.2-6, 18-1 |
Mar 12 | Hashing | review 11.1 and 11.2; read 11.3; read old Section 11.5 from removed material (Perfect Hashing) | 11.1-1, 11.2-2, 11.2-5, 11.1-4, 11.3-1, 11-4 | review 11.1 and 11.2; read 11.3, 11.5 | 11.1-4, 11.3-1, 11-4 |
Mar 26 | Lock-free data structures | Some slides (we won't cover all of them) |
Updated April 16, 2025