Abstract¶
Husky Maps is a web app for mapping the world, searching for places, and navigating around Seattle. All these features are powered by data structures and algorithms, programming abstractions designed to represent data and automate processes. In your prior programming experience, you learned how to implement specifications by writing Java programs that used data structures to solve problems. In this course, you’ll learn how to answer the why question: Why did we write the specification that way in the first place?
There are many decisions to make when designing a software system, and many of these decisions have significant consequences on qualities of a system. In this course, we’ll focus on learning data structures as implementations of abstract data types. An abstract data type describes what you can do with a data type, but not how the data type is implemented; a data structure provides both a description of functionality and a specific implementation of functionality. Rather than think of problems as requiring custom algorithms that we invent from scratch each time, abstract data types help us think of problems as variations that can be addressed by adapting more general algorithm ideas.
Data Structures and Algorithms presents a selection of these ideas in a way intended to help you design, analyze, and evaluate software systems. Learning these ideas can enable fuller participation in the community of computing professionals.
| Mon, Jun 22 | Lecture | Introductions | |
| Wed, Jun 24 | Lecture | Introduction to ADTs | |
| Linked Nodes | |||
| Thu, Jun 25 | Section | Section 1 | HW1 due |
| Fri, Jun 26 | Lecture | Intro to Runtime Analysis | |
| Mon, Jun 29 | Lecture | Big O & Case Analysis | |
| Wed, Jul 1 | Lecture | Analyzing Recursive Code | |
| Merge Sort | |||
| Thu, Jul 2 | Section | Section 2 | HW2 due |
| Fri, Jul 3 | HOLIDAY — No Class | ||
| Mon, Jul 6 | Lecture | Intro to Hashing | |
| Wed, Jul 8 | Lecture | Hashing Collision Resolution | |
| Thu, Jul 9 | Section | Section 3 | HW3 due |
| Fri, Jul 10 | Lecture | No Class | |
| Mon, Jul 13 | Lecture | Trees (BSTs and AVLs) | |
| Wed, Jul 15 | Exam | Midterm 1 | |
| Thu, Jul 16 | Section | Section 4 | HW4 due |
| Fri, Jul 17 | Lecture | Trees II | |
| Left-Leaning Red-Black Trees | |||
| Mon, Jul 20 | Lecture | Tries and TSTs | |
| Wed, Jul 22 | Lecture | Binary Heaps | |
| Thu, Jul 23 | Section | Section 5 | HW5 due |
| Fri, Jul 24 | Lecture | Graph ADT | |
| Graph Traversals | |||
| Mon, Jul 27 | Lecture | Shortest Paths | |
| Wed, Jul 29 | Lecture | MSTs (Recording) | |
| Thu, Jul 30 | Section | Section 6 | HW6 due |
| Fri, Jul 31 | Lecture | Disjoint Sets (Recording) | |
| Mon, Aug 3 | Lecture | No Class | |
| Wed, Aug 5 | Exam | Midterm 2 | |
| Thu, Aug 6 | Section | Section 7 | HW7 due |
| Fri, Aug 7 | Lecture | Sorting I | |
| Quicksort | |||
| Mon, Aug 10 | Lecture | Content Review | |
| Wed, Aug 12 | Lecture | Final Exam Practice | |
| Thu, Aug 13 | Section | Section 8: Final Review | |
| Fri, Aug 14 | Exam | Final Exam (handwritten, in person) | |
| Mon, Aug 17 | Lecture | Dynamic Programming | HW8 due |
| Wed, Aug 19 | Lecture | Sorting II & Special Topics | |
| Thu, Aug 20 | Section | No Section | |
| Fri, Aug 21 | Lecture | Final Makeups (No Lecture) |
This course is designed to support students who have completed:
- CSE 123: Introduction to Computer Programming III
- Know the implementation of basic data structures such as resizing arrays, linked nodes, and trees. We will learn how effective software design is more than just about writing clear and correct code.
Why should we learn?¶
The education you receive in this course can help prepare you for programming jobs, but this isn’t the only purpose for computing education. Education is not only about yourself and your personal gain, but also about all of us and our capacity to live together as a community.
The University of Washington acknowledges the Coast Salish peoples of this land, the land which touches the shared waters of all tribes and bands within the Duwamish, Puyallup, Suquamish, Tulalip and Muckleshoot nations. Among the traditions of the Coast Salish peoples is a value for the connectedness between all living things and a recognition of the unique ways that each of us comes to know things.
Modern education has the idea that we all need to know the same thing. At the end of the lesson, everyone will know the same thing. That’s why we have tests, that’s why we have quizzes, that’s why we have homework: to ensure we all know the same thing. And that’s powerful—that’s important—within a certain context.
But for native culture, the idea that each listener divines or finds their own answer, their own meaning, their own teaching from the story is equally powerful—that each person needs to be able to look at the world and define it for themselves within their culture and then also find a way to live in that world according to the teachings of their people in their culture.
- We are responsible for each others’ success
Everyone has a right to feel like they belong in this course. We’ll need to act with compassion and caring to collaborate with each other. Although we will need more than just unexamined commitments to collaboration, listening, empathy, mindfulness, and caring, the following guidelines offer a starting point for ensuring compassion toward each other Inoue, 2022.
Listen with intention to understand first and form an opinion only after you fully understand.
Take responsibility for intended and unintended effects of your words and actions on others.
Mindfully respond to others’ ideas by acknowledging the unique value of each contribution.
You should expect and demand to be treated by your classmates and teachers with respect. If any incident occurs that challenges this commitment to a supportive, diverse, inclusive, and equitable environment, please let the instructor know so the issue can be addressed. Should you feel uncomfortable bringing up an issue with the instructor directly, meet our advisors during quick questions or contact the College of Engineering.
- We recognize everyone has unique circumstances
Do not hesitate to contact the instructor by private post or email. The sooner we are made aware of your circumstances, the more we can help. Extenuating circumstances include work-school balance, familial responsibilities, religious observations, military duties, unexpected travel, or anything else beyond your control that may negatively impact your performance in the class.
It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), activate your accommodations via myDRS so we can discuss how they will be implemented in this course. If you have a temporary health condition or permanent disability that requires accommodations, contact DRS directly to set up an Access Plan.
Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy. Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form.
- We believe everyone wants to learn
Education is about shaping your identity as much as it is about learning things. In school, the consequences of making mistakes are relatively small. But the habits you form now—repeated over days, weeks, months, or years—determine who you will be in the future. Now is the best time to practice honest habits.
We ask that you do not claim to be responsible for work that is not yours. When you receive substantial help from someone else, include a citation. Don’t post your solutions publicly. Most importantly, don’t deprive yourself or others of the learning opportunities that we’ve created in this course. Allegations of misconduct by students may be referred to the appropriate campus office for investigation and resolution.
Academic honesty reflects the trust (or the lack thereof) between students and teachers. We do our best to design the course in ways that ensure trust, but we know our systems are not perfect. If you submit work in violation of these policies but bring it to the attention of the instructor within 72 hours, you may resubmit your own work without further consequence. Rather than blame students, we want to fix or replace broken systems that compel students to lose trust.
How the course works¶
Lectures during Monday, Wednesday, and Friday. They are a space for deliberate practice and review of pre-readings linked on the course website.
Homework allows you to demonstrate your learning through quiz-like review. Each week’s assignment contains a LeetCode-style coding problem and lecture-style exercise problem, due by EOD Thursday each week. During Thursday’s section, you will have a chance to receive support and ask questions from your TAs.
Expect to spend 4 hours in class and 8 hours outside of class working on this course. Some weeks may require more or less time than other weeks. If you find the workload is significantly exceeding this expectation, talk to your TA.
Grading. Your percentage grade in this course will be weighted using these categories:
Homework, 40%. Eight assignments, weighted 5% each. Your lowest score is automatically replaced with full credit (dropped).
Midterms, 30%. Two midterms, weighted 15% each, graded on effort and accuracy as mock data structures and algorithms interviews.
Final, 30%. One cumulative, handwritten exam, taken in person.
Participation (Extra Credit). Section is optional. However, if you attend at least 7 out of the 8 sections and you earn an extra 5% added to your final grade.
Component weights may shift by up to 10% in either direction as the course evolves. Any changes will be announced on the course site and EdStem.
Late work. Homework does not have built-in late days. If something comes up, please post privately on EdStem before the deadline and we’ll consider exceptions on a case by case basis.
Regrades. If you believe something was graded incorrectly, submit your request as a private Ed post.
This course website is adapted from the CSE 373 course site created by Kevin Lin, used under CC BY-NC-SA 4.0.
- Inoue, A. B. (2022). Labor-Based Grading Contracts: Building Equity and Inclusion in the Compassionate Writing Classroom, 2nd Edition. The WAC Clearinghouse; University Press of Colorado. 10.37514/per-b.2022.1824