Data Structures and Algorithms

University of Washington, Spring 2025

Kevin Lin

he/him

kevinl@cs.uw.edu

Office Hours

Thu 10:30 AM – 12:20 PM in CSE 560

If I’m not working on this class, you can probably find me looking around for travel and restaurant deals, experiencing the latest indie movies at SIFF cinemas, introducing guests to our underwater neighbors at the Seattle Aquarium, or designing new methods to empower students through education.

Schedule a meeting

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. This 10-week course is organized around four 2-week case study projects. By the end of the course, you’ll have retraced the history of invention for 4 abstract data types, 12 implementations of them, and 7 real-world problems that they address:

  1. Deque data structures for browsing history.
  2. Autocomplete data structures and algorithms for search suggestions and DNA indexing.
  3. Priority queue data structures for web accessibility analytics and shortest paths.
  4. Shortest paths and graph data structures for seam carving and navigation directions.
  5. Finale evaluating and applying what you’ve learned over the quarter.

This course is divided into 5 modules: Deques, Autocomplete, Priority Queues, Shortest Paths, and Finale. Assignments are often due on Tuesdays and Wednesdays. Enrolled students will complete projects in CSE GitLab, but public project code is also available on GitHub.

Search to find relevant course materials.

Deques

Basic Data Structures

Mar 31
Welcome
ProjectSetup by Apr 5
Apr 2
Arrays and Nodes
Slides · Worksheet
Apr 3
Section Reference Semantics
Slides · Worksheet
Apr 4
Array Deques
Slides · Worksheet
ProjectDeques quiz by Apr 8, code by Apr 15, analysis by Apr 16

Algorithm Analysis

Apr 7
Asymptotic Analysis
Slides · Worksheet
Apr 9
Iterative Sorts
Slides · Worksheet
Apr 10
Section Algorithm Analysis
Slides · Worksheet
Apr 11
Merge Sort
Slides · Worksheet

Autocomplete

Search Trees

Apr 14
Binary Search Trees
Slides · Worksheet
Apr 16
Tries
Slides · Worksheet
ReviewPractice Exam 1 submission by Apr 22, review before class Apr 25
Apr 17
SectionRecurrences
Slides · Worksheet
Apr 18
2-3 Trees
Slides · Worksheet
ProjectAutocomplete quiz by Apr 22, code by Apr 29, analysis by Apr 30

Isomorphism

Apr 21
Left-Leaning Red-Black Trees
Slides · Worksheet
Apr 23
Quicksort
Slides · Worksheet
Apr 24
SectionIsomorphism
Apr 25
Two-Stage Exam 1

Priority Queues

Heaps and Hashing

Apr 28
Binary Heaps
Apr 30
Hash Tables
ReviewPractice Exam 2 submission by May 6, review before class May 9
May 1
SectionHeaps and Hashing
May 2
Counting Sorts
ProjectPriority Queues quiz by May 6, code by May 13, analysis by May 14

Object Composition

May 5
Affordance Analysis
May 7
Graph Data Type
May 8
SectionObject Composition
May 9
Two-Stage Exam 2

Shortest Paths

Graphs

May 12
Graph Traversals
May 14
Shortest Paths Trees
ReviewPractice Exam 3 submission by May 20, review before class May 23
May 15
SectionGraphs
May 16
Dynamic Programming
ProjectShortest Paths quiz by May 20, code by May 27, analysis by May 28

Applications

May 19
Minimum Spanning Trees
May 21
Disjoint Sets
May 22
SectionApplications
May 23
Two-Stage Exam 3

Finale

Interview Prep

May 28
Code Challenges
May 29
SectionCode Challenges
May 30
System Design

Final Review

Jun 2
Integration Questions
Jun 4
TA Panel
Jun 5
SectionFinal Review
Jun 6
Next Steps

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.1 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 something.2

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.

Our course emphasizes the following values.

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,3 the following guidelines offer a starting point for ensuring compassion toward each other.4
  • Listen with intention to understand first and form an opinion only after you fully understand.
  • Take responsibility for the 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 discussion post or appointment. 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.
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 does learning occur?

In a traditional classroom, you attend class while a teacher lectures until time is up. Then, you go home and do the important work of applying concepts toward practice problems or assignments on your own. Finally, you take an exam to show what you know.

Today, we know that there are more effective ways to learn science, engineering, and mathematics.5 Learning skills like software engineering and algorithm analysis requires deliberate practice: a learning cycle that starts with sustained motivation, then presents tasks that build on prior knowledge, and concludes with immediate, personalized feedback. Each module in the course will involve several different activities that are designed so that we can make the most of our class time together.

Before lecture, prepare for lecture by completing the assigned prework.
In Canvas, answer the prework quiz due before lecture.
During lecture and quiz section, practice applying and explaining what you learned.
Lecture participation is tracked via completion of PollEverywhere activities.
Quiz section participation is tracked via presentations and work submitted during quiz section.
After class, integrate what you learned in real-world problems through projects.
In Gradescope, complete the project quiz, project code, and project analysis assignments.
During the finale, complete the build-your-own-project to synthesize your skills and knowledge.
Show what you learned through two-stage exams during the quarter, and an individual final exam.
In Canvas, complete practice exams and analyze sample practice exam submissions with peers.
In a two-stage exam, complete a 25-minute individual exam followed by a group analysis activity.

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.

  • 8:30 AM
  • 9:00 AM
  • 9:30 AM
  • 10:00 AM
  • 10:30 AM
  • 11:00 AM
  • 11:30 AM
  • 12:00 PM
  • 12:30 PM
  • 1:00 PM
  • 1:30 PM
  • 2:00 PM
  • 2:30 PM
  • 3:00 PM
  • 3:30 PM
  • 4:00 PM
  • 4:30 PM
  • 5:00 PM

  • Monday

    • Lecture
      12:30 PM–1:20 PM
      CSE2 G20
    • Office Hours
      3:30 PM–5:20 PM
      DEN 112

  • Tuesday

    • Office Hours
      10:30 AM–12:20 PM
      SIG 226
    • Office Hours
      12:30 PM–2:20 PM
      LOW 202
    • Office Hours
      2:30 PM–4:20 PM
      BAG 108

  • Wednesday

    • Office Hours
      10:30 AM–12:20 PM
      PCAR 297
    • Lecture
      12:30 PM–1:20 PM
      CSE2 G20
    • Office Hours
      3:30 PM–5:20 PM
      DEM 004

  • Thursday

    • Sections
      8:30 AM–4:20 PM
    • Office Hours
      10:30 AM–12:20 PM
      CSE 560

  • Friday

    • Lecture
      12:30 PM–1:20 PM
      CSE2 G20
    • Office Hours
      3:30 PM–5:20 PM
      PCAR 297

Devices may be used in-class at student discretion but with the community agreement that use should generally be on-task and minimize distractions to others. We agree to common courtesy including closing laptops and significantly turning down brightness when the device is not in direct use. Students who have urgent matters that would take an extended period of time to address during class should step outside the room to use their devices—learning is not likely to happen even if you stayed in class, and the urgency of your work would distract others.

Some generative AI use is allowed with citation and caution. More generally, any concept not taught in this course or in a prerequisite course must be cited. Submitted work that is not consistent with the curriculum/citations will not be evaluated and instead returned to the student for resubmission if the opportunity is available. Repeated failure to cite sources and submissions that shortcut intended learning objectives may have further consequences—do not prompt generative AI with any substantive portion of an assigned task.

How is this course graded?

Grading in this course is determined by module completion, exam marks, and participation. 4 days of participation across lectures and quiz sections will be automatically dropped. Students who miss 5 to 10 days can make up participation by coming to office hours within 2 weeks of the missing participation to review the activity with the staff. Students who need to miss more than 10 days should make this known to the staff (ideally in the first 2 weeks) to discuss alternatives.

The following combinations of work will be guaranteed certain final grades.

1.0 or greater
Complete the Deques and Autocomplete modules.
Satisfactory mark on Exam 1.
Satisfactory participation through Exam 1.
2.0 or greater
Complete the Deques, Autocomplete, and Priority Queues modules.
Satisfactory mark on Exam 1 and Exam 2.
Satisfactory participation through Exam 2.
3.0 or greater
Complete the Deques, Autocomplete, Priority Queues, and Shortest Paths modules.
Satisfactory mark on Exam 1, Exam 2, and Exam 3.
Satisfactory participation through Exam 3.
4.0
Complete the Deques, Autocomplete, Priority Queues, Shortest Paths, and Finale modules.
Satisfactory mark on Exam 1, Exam 2, and 3.
Highest mark on the Final Exam.

These guarantees are intended to help outline expectations and help external reviewers understand what each final grade range communicates about student achievement. These guarantees do not preclude access to higher grades. Within the constraints of the course, we endeavor to provide a limited number of revision opportunities to help students work toward completion of all five modules. Similarly, the threshold for satisfactory exam marks is designed such that most students should be able to meet them with sufficient preparation and exam revisions. The final exam consists of 4 parts corresponding to Exam 1, Exam 2, Exam 3, and a final part for integrative questions: improvements demonstrated in each final exam part may be used to replace the corresponding Exam 1, Exam 2, and Exam 3 marks.

Grade weights are not available for this course because final grades are not computed as a strictly linear combination of categories. Non-linearities exist in this grading system so that grades communicate specific levels of student achievement. In practice, this means penalties will be applied to unreasonable combinations of work, such as completing all the modules (take-home work) without having any satisfactory exam marks. Non-linearity also enables counting participation toward 1.0, 2.0, and 3.0 final grades without also requiring participation for a 4.0.

Evaluating Approaches to Teaching Data Structures and Algorithms

You are being asked to participate in a research study to find out more about how pedagogical and curricular approaches affect the student experience in an undergraduate Data Structures and Algorithms course. You have been asked to participate in this study because you are a student in a class that is being studied or used as a control. The purpose of this study is to create knowledge that has the potential to improve the educational experience for students at the University of Washington and beyond.

What will you be asked to do?
If you agree to be in this study, your data from this class including surveys/evaluations, coursework, and course forum discussion may be analyzed. Your participation involves only agreeing to let us use your data in our analysis. You will not be required to do anything beyond normal educational practice.
What will happen to the information you provide?
Data from participants will be retained only for research purposes and stored using codes that provide a degree of confidentiality. Your instructor will not know whether you are participating in this study until after final grades have been posted.
What can you do if you want more information?
Talk to the study team. Kevin Lin is the lead researcher at the University of Washington for this study and can be contacted at kevinl@cs.uw.edu.
Talk to someone else. If you want to talk with someone who is not part of the study team about the study, your rights as a research subject, or to report problems or complaints about the study, contact the UW Human Subjects Division at hsdinfo@uw.edu or 206-543-0098.
What are my options for participation?
By default, you will be included in this study. No additional actions are required to participate.
Participation in this research, however, is optional. You may withdraw at any time without penalty by making a private Ed post to let us know.

Two-Stage Exams Multi-Institutional Study

You are being asked to participate in a research study to evaluate the student experience with two-stage exams across multiple institutions of higher education. You have been asked to participate in this study because you are a student in a class that is being studied or used as a control. The purpose of this study is to create knowledge that has the potential to improve the educational experience for students at the University of Washington and beyond.

What will you be asked to do?
If you agree to be in this study, your data from this class including anonymous surveys and anonymized grade data may be analyzed. Your participation involves only agreeing to let us use your data in our analysis. You will not be required to do anything beyond normal educational practice.
What will happen to the information you provide?
Data from participants will be retained only for research purposes and stored anonymously at the University of Manitoba. Your instructor will not know whether you are participating in this study until after final grades have been posted.
What can you do if you want more information?
Talk to the study team. Kevin Lin is the lead researcher at the University of Washington for this study and can be contacted at kevinl@cs.uw.edu.
Talk to someone else. If you want to talk with someone who is not part of the study team about the study, your rights as a research subject, or to report problems or complaints about the study, contact the UW Human Subjects Division at hsdinfo@uw.edu or 206-543-0098.
What are my options for participation?
During each two-stage exam, there will be anonymous surveys to evaluate our exams. The survey includes a consent form to allow us to include your anonymous survey responses in the research.
At the end of the quarter, a research assistant (not affiliated with the course) will recruit participants and distribute consent forms to allow us to anonymize your grade data and include it in the research dataset.

  1. Mark Guzdial. 2021. Computer science was always supposed to be taught to everyone, and it wasn’t about getting a job. ↩

  2. Roger Fernandes. 2012. Roger Fernandes: Artist/Storyteller/Educator. ↩

  3. Brian Arao and Kristi Clemens. 2013. “From Safe Spaces to Brave Spaces: A New Way to Frame Dialogue Around Diversity and Social Justice” in The Art of Effective Facilitation. ↩

  4. Asao B. Inoue. 2019. “Sample Charter for Compassion” in Labor-Based Grading Contracts: Building Equity and Inclusion in the Compassionate Writing Classroom. ↩

  5. Scott Freeman, Sarah L. Eddy, Miles McDonough, Michelle K. Smith, Nnadozie Okoroafor, Hannah Jordt, and Mary Pat Wenderoth. 2014. Active learning increases student performance in science, engineering, and mathematics. ↩

Explore CSE 373

  • Lessons - Learning materials and resources.
  • Projects - Project instructions and specifications.
  • Staff - All the teaching and learning assistants.