Responsible Problem Solving: course components

Focusing on the societal consequences of design choices in data structures and algorithms

A computer science student first learns problem solving in data structures and algorithms. She learns to define a problem clearly, break it into solvable components, reason about the correctness of any proposed solution, measure resources used by her solution (space and time) and how to use them efficiently.

But when computer scientists apply these problemĀ­solving skills to questions and systems that impact society, responsible problem design and solution requires that we model societal costs and resources accurately. In these curricular components, we aim to bring questions and issues from impacted societal domains into the data structures and algorithms curriculum where computer science students first learn a problemĀ­solving mindset. We aim to create computer scientists who naturally consider issues such as sustainability, racism, and community impact (e.g., of surveillance) alongside matters of data structure design and complexity.

On this site, we post the slides and assignments for curricular modules that are core components of the standard data structures and algorithms curriculum reimagined to include a focus on responsibility.

Computational Topics

Societal Topics


About Us

Criminal Justice

This assignment introduces students to the idea of risk assessments in the context of an introductory data structures assignment introducing the idea of classes.

Data Structures (CS 2) Lesson: ProPublica Machine Bias article and Object-oriented programming

Level: This lesson is designed to be one of the first assignments in a standard Java-based CS 2 course.

Topics: objects, classes, ArrayList, data structure design, reading in data

Background: We suggest that you have students prepare for this assignment by, in order, watching / reading the below:

  1. Watching this video about the ProPublica article (~1.5 min) - we recommend showing this in class.
  2. Reading the ProPublica Machine Bias article
  3. Watching this background video (~5 min) of Haverford student Steve Lee '21 describing risk assessments and the surrounding criminal justice context.
  4. Additional reference for details about the lab: Understanding the ProPublica Article (tex)
Programming Assignment Part 1 (pdf) Part 1 (tex)

Programming Assignment Part 2 (pdf) Part 2 (tex)

Cleaned data (csv)

Elections

These assignments focus on the U.S. elections process in the context of an introductory data structures course. One lesson can be found below and the other is the deduplication of voting rolls assignment that also includes a focus on sustainability and complexity.

Data Structures (CS 2) Lesson: Polling Data, Binary Trees, and Heaps

Level: This lesson is designed to be part of the introduction to data structures for binary trees and priority queues in a standard Java-based CS 2 course. Part 1 covers recursive linked binary trees and part 2 builds array-based heaps.

Topics: recursive binary tree design, array-based heaps

Programming Assignment Part 1 Part 2

Sustainability and Complexity

The goal of these lessons and assignments is to introduce students to the environmental impacts of computing.

These lessons were created with the help of Jon Wilson in Haverford College's Environmental Studies Department.

Data Structures (CS 2) Lesson: Energy Usage, Complexity, Deduplication, and Voting Rolls

Level: This lesson is designed to be part of a standard data structures curriculum where notions of complexity are being introduced for the first time. The lesson is designed to come late in the course and could even be used as a final project.

Topics: energy usage, complexity, sorting, hash tables, deduplication, voting

Programming Assignment (pdf) Programming Assignment (tex)

With thanks to Alvin Grissom II for the idea of considering deduplication of voting rolls.

Analysis of Algorithms Lesson: Energy Usage and Complexity

Level: This lesson is designed to accompany Chapter 2 of Algorithm Design by Kleinberg and Tardos, and could also generally be used as a second lesson on complexity after the initial introduction of the high level and/or formal definitions in a data structures or algorithms course.

Background: In order to determine the energyusage and CO2 emissions of a function, the Python 3 package energyusage uses methodology outlined in this paper.

Homework (pdf) Homework (tex) Slides (pptx)

Data Integrity

These materials look at how (im)mutable data structures interact with data integrity.

Thinking about Data Integrity

Level: These questions can be added to an assignment in which students are implementing both mutable and immutable versions of the same data structure.

Topics: data integrity, (im)mutable data structures

Questions (gdoc)

Social Threat Modeling

These materials expose students to techniques for identifying social threats in systems built around data structures and algorithms.

Lecture Notes: Identifying Social Threats

Level: Notes from a lecture on why and how to consider social-responsibility in data-structures and algorithms. Designed for a 2nd or 3rd semester course for CS students.

Topics: threat modeling

Lecture Notes (pdf) Modeling Framework (gdoc)

Additional Algorithms Assignments

These additional assignments are designed to supplement a traditional Algorithms curriculum. A version of these and additional assignments aligned with the Kleinberg and Tardos Algorithm Design textbook was created in collaboration with Atri Rudra and can be found here.

Analysis of Algorithms: Stable Matching

Level: This problem set is designed to align with Chapter 1 of Algorithm Design by Kleinberg and Tardos.

Topics: stable matching, human impact

Homework (pdf) Homework (tex)

Analysis of Algorithms: Greedy Algorithms

Level: This problem set is designed to align with Chapter 4 of Algorithm Design by Kleinberg and Tardos.

Topics: greedy algorithms, human impact

Homework (pdf) Homework (tex)

Considering Stakeholders of Search Algorithms

Level: These questions can be added to a search-engine implementation project in which students have implemented TF-IDF and PageRank.

Topics: search engines, non-ascii character sets, human impact

Questions (gdoc)