layout: minimal
title: CSE 373
has_children: true
has_toc: true
seo:
  type: Course
  name: Data Structures and Algorithms

{{ site.description }}

{: .mb-2 } {{ site.tagline }} {: .fs-6 .fw-300 }

{% assign instructors = site.staffers | where: 'role', 'Instructor' %} {% for staffer in instructors %} {{ staffer }} {% endfor %}

Husky Maps is a web app for mapping the world, searching for places, and navigating around Seattle. All these features are powered by the sociotechnical infrastructure of data structures and algorithms, programming abstractions designed by software engineers to represent data and automate processes. CSE 373 asks: How do data structures and algorithms affect the software and systems that we build?

Computer scientists historically addressed this question from a disembodied technical perspective by analyzing only the efficiency of data structures and algorithms. But in order to address society's most challenging problems around the design and use of computing, we need to learn data structures and algorithms in a deeply sociotechnical way, combining social and technical approaches. Just as machine learning and artificial intelligence is rapidly changing the world for better and for worse, the design of data structures and algorithms can raise equally important questions for the things we build.

In our first project, for example, we'll study Autocomplete, a feature of the Husky Maps search bar. Autocomplete is a feature that helps a user select valid search results by showing possible inputs as they type. Computer scientists have historically only asked questions such as, "Is this implementation of autocomplete correct?" or "How fast is this implementation?" These are important questions, but they're not the only questions. In this course, we will also ask sociotechnical questions: "Who benefits from this definition of autocomplete? Who is harmed?" and "What can we do to ensure justice?"

Although CSE 373 is designed to be taken after CSE 143 (objects, array lists, linked lists, search trees), the focus is not on programming but rather the design, analysis, and critique of the data structures and algorithms behind software's social imaginations and designs for the future.

1. Design data structures and algorithms by implementing and maintaining invariants.
2. Analyze the runtime and design values of data structures and algorithms.
3. Critique the application of data structures and algorithms toward social problems.

In this course, we'll study 3 interfaces and 6 applications of data structures and algorithms.

1. Autocomplete data structures and algorithms for search suggestions and DNA indexing.
2. Priority queue data structures for content moderation and shortest paths.
3. Graph data structures and shortest paths for seam carving and navigation directions.

In the final week, we'll wrap up by assembling a portfolio reflecting on your journey.

Deliberate practice

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.

This classroom structure isn't effective for learning science, engineering, and mathematics.¹ Think of learning computer science as learning how to ride a bike. Quite a few people know how to ride a bike. But how many of them learned to ride a bike through 50 minutes of lecture three times a week? Probably no one---learning to ride a bike requires riding an actual bike! Likewise, learning computer science requires deliberate practice.

1. Sustained motivation.
2. Tasks that build on prior knowledge.
3. Immediate, personalized feedback on tasks.
4. Repetition of all the above.

The course is organized into four modules: Autocomplete, Priority Queues, Shortest Paths, and Portfolio. Modules include multiple activities.

1. On your own before class, prepare for learning by completing the pre-class preparation.
2. In section teams during class and quiz section, collaborate on the in-class guided practice.
3. On your own after quiz section, complete the checkpoint and record your own explanation video.
4. In project teams throughout the module, apply design, analysis, and critique skills in the project.

Expect to spend 4 hours in class and 8 hours outside of class working on this course. Depending on how you plan your project work, some weeks may be more work or less work than other weeks. If you find the workload is significantly exceeding this expectation, talk to your TA.

Grading in this course encourages learning through deliberate practice by emphasizing revision and resubmission of work. All coursework is designed around feedback loops where you try something, get feedback, then try again. Grades are based on what you eventually learn through this process.

1.0 or greater : Satisfactory Autocomplete.

2.0 or greater : Satisfactory Autocomplete. : Satisfactory Priority Queues.

3.0 or greater : Satisfactory Autocomplete. : Satisfactory Priority Queues. : Satisfactory Shortest Paths.

4.0 : Satisfactory Autocomplete. : Satisfactory Priority Queues. : Satisfactory Shortest Paths. : Exemplary Portfolio.

Community of learners

Effective computer science learning involves not only deliberate practice, but also comparing multiple ways of thinking and knowing.² This means working past reductive dichotomies of "right" or "wrong" and instead appreciating all ideas as opportunities for enriching our understanding of not only course concepts, but also each other.

However, in the Euro-centric scientific worldview, learning is for individual gain to help you achieve your own goals.³ Exams, grades, and assessments are used to evaluate people---in the most literal sense, to assess the social value of a person. In today's market economy, what value does a person have if they can't generate wealth? If the purpose of learning is to help yourself, and learning is about competition, then why care about social goals for computer science? Why collaborate? Why help anyone but yourself? So far, we've discussed what we will be learning and how learning occurs, but perhaps we should also ask why learn at all?⁴

Cartesian Dualism : I think, therefore I am : Mind/body separation : Competitive : Learning for individual gain : Measures intelligence against a single norm

Cartesian dualism describes mind/body separation, or the idea that rational thinking occurs independent of your physical being. In scientific research, this dualism suggests that the position, opinions, and lived experiences of the researcher doesn't matter---that science is the same no matter who carried out the research. Whether you learn things alone or learn things collaboratively makes no difference because knowledge is standardized: it doesn't matter who, when, where, or how it was learned. If knowledge is a standardized commodity, and commodities can be purchased or exchanged, then learning a concept one way is the same as learning that same concept in any other way.

But not all traditions understand learning as dualism. 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.⁵

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.

In'lakesh is a Mayan culture that values multiple ways of knowing.⁴ In'lakesh shares several characteristics with many Indigenous and Asian ways of living.³

In'lakesh : I am you and you are me : Body/mind/spirit = integrated : Collaborative : Learning for collective benefit : Values multiple ways of knowing

We recognize that there's a practicality to standardized education---this course is a commodity that offers economic value and social mobility. Yet learning is also about more than ourselves. Society's most challenging problems are ones that can't be solved alone. It will take all of us working together, each contributing our own unique strengths, to create the socially-just worlds we need.

Values

We are responsible for each others' success : Everyone has a right to feel like they belong in this course. We'll need to work together with compassion and caring to more deeply understand social problems in our classroom and beyond. Exclusionary computer science culture compels students to tell themselves that they don't belong---that they can't do computer science, or that their computer science is not real computer science---and blames students for their own disinterest in computing and the resulting racial and gender hierarchies.⁶ We have a collective responsibility to dismantle oppressive, exclusionary culture because everyone deserves care in our classroom and beyond. : Learning requires discomfort and personal change. This class isn't truly working until everyone feels like they can take risks in learning the political dimensions of data structures and algorithms.⁷ Although achieving justice in our classroom will require 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.⁹

• 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 : Please 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. : 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 request a copy of someone else's work, don't provide your work to another student, and don't post your solutions publicly. : 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.

References