Course: CS 124: Data Structures and Algorithms
Course Level: Upper-level undergraduate
Course Description: “TThis course covers the modern theory of algorithms, focusing on the themes of efficient algorithms and intractable problems. The course goal is to provide a solid background in algorithms for computer science students, in preparation either for a job in industry or for more advanced courses at the graduate level. I strongly encourage mathematicians, biologists, physicists, and people from other concentrations to take the course as well. Besides introducing the basic language and tools for algorithm analysis, we will also cover several specific problems and general design paradigms. Toward the end of the quarter, we will also examine heuristic techniques often used in practice, even though in many cases formal theoretical results are not known.
We will focus on the theoretical and mathematical aspects in class and on the homework assignments. But because one gains a deeper understanding of algorithms from actually implementing them, the course will include a substantial programming component. In particular, most problem sets include at least one problem that requires implementing an algorithmic solution to be tested against our test data. More details will be available when the first programming assignment is given.
As you can see from the preliminary list of topics (included below), we will be covering a great deal. I expect the course to be challenging, both in terms of the workload and the difficulty of the material. You should be prepared to do a lot of work outside of class. The payoff will be that you will learn a lot of both useful and interesting things.
Module Topic: How can we design models that allocate goods and services fairly?
Module Author: Cat Wade
Semesters Taught: Spring 2019
Module Overview: In this module, we consider fairness in resource allocation. Real-world resource allocation problems, such as the problem of allocating hospital beds to patients, can be modeled as flow maximization problems by representing both resources to be allocated and potential recipients of those resources as nodes in a flow network. After demonstrating how to model resource allocation problems using flow networks, the Embedded EthiCS fellow leads a discussion of what treating people fairly requires in different kinds of real-world resource allocation problems. We then discuss how to model these ethical requirements as formal constraints on flow maximization problems.
Connection to Course Technical Material: In the leadup to the module, the course covers max flow problems and strategies for solving them algorithmically. The module builds on this technical material by (a) demonstrating how it can be used to solve real-world resource allocation problems and (b) showing how to formally model ethical constraints on these problems.
In order to stay tightly connected to the course technical material, the module focuses on modeling realistic resource allocation problems using formal machinery covered in an earlier class session. Examples discussed include the problem of allocating housing to families and the problem of allocating school enrollment slots to students.
Key Philosophical Questions:
Key Philosophical Concepts:
Sample Class Activity:
Students are given examples of three realistic resource allocation problems and asked to consider how they might be solved in a way that treats everyone concerned fairly.
Scenario (1): You are an employer trying to decide who to promote. You have 5 employees up for the position. How do you pick between them in order to make a fair decision?
Scenario (2): You are a conductor for a large orchestra with over one hundred members. Since you are new to the position, you don’t yet know any of the musicians well. You have ten tickets to an upcoming concert that you know everyone would like to go to. How do you decide fairly how to distribute the ten tickets?
Scenario (3): You and your partner have to decide who among your friends should officiate your wedding. You have different preferences. How could you resolve this fairly?
For each scenario, students are asked to discuss possible decision-making procedures they might use, as well whether those procedures would be fair or unfair. After each scenario, the Embedded EthiCS fellow leads a debrief with the full class.
This activity has three goals: (1) soliciting students’ judgments about what fairness requires in concrete cases; (2) helping them to appreciate how much those judgments can vary; and (3) laying the groundwork for subsequent discussion of different types of fairness requirements and when they apply.
The assignment for this module consists of several short-answer questions on the assigned reading (see “Assigned Readings”):