Abstract We study a variant of the offline Dial-a-Ride problem, where each request has a source and destination and the goal is to maximize the number of requests served within a specified time limit. We investigate this problem for the uniform metric space and show that the problem is NP-hard. We then present a 2/3 approximation algorithm called $$\textsc {twochain}$$ T W O C H A I N , which simply looks for pairs of requests that are “chained” together and serves those before serving requests that are not connected to any others. We also show that a natural generalization of this algorithm, k-chain, has an approximation ratio at most 7/9. We also analyze the longest-chain-first algorithm for the problem, characterizing graphs on which it is optimal, and showing that it has an approximation ratio no better than 5/6. Our experiments on all of these algorithms show that $$\textsc {twochain}$$ T W O C H A I N is a promising algorithm, performing nearly as well as more computationally intensive variants. We dedicate this article to the memory of Gerhard Woeginger, whose life and work greatly influenced our professional lives, as expanded upon in the Acknowledgments. Woeginger’s prolific research in scheduling, matching, bin-packing, TSP, and online algorithms in general, all served as important parts of the foundation on which our own scholarly pursuits were shaped and formed over the years. Woeginger also studied Dial-a-Ride (DARP) Problems, as DARP is a generalization both of scheduling problems and of TSP, which were two of his most active areas of research.

A typical US college student who is asked to name people who have made significant contributions to computing will likely produce a short, predictable, fairly homogeneous list. To help increase awareness of the diversity of people involved in computing, we introduced a biography project into an introductory non-majors course at a small liberal arts college. With each student exploring and presenting on the life and contributions of a less well-known contributor to computing, the class is exposed to a number of people that students likely haven't heard of previously. Moreover, with fairly open-ended requirements for the assignment, we can learn what students find interesting and noteworthy about these individuals, perhaps finding ways to more broadly increase awareness.

We use "unplugged" activities to introduce parallel concepts in a first-year seminar for Computer Science majors. Student teams explore parallel approaches to computational tasks. Pre- and post-activity surveys, and a reflection paper, measure the impact of these activities on students' views about parallel programming. Our goal is to encourage parallel thinking about programming tasks before sequential approaches become ingrained. Computer Science curricula have traditionally focused on sequential approaches to programming, which were well matched to earlier computer systems. However, current systems almost all use multiprocessor CPUs, and are frequently used in clusters or networks of multiple computers. Recent curricular guidelines from organizations such as ACM and ABET recommend exposure to parallel computing concepts.

We propose to strengthen the computer science (CS) curriculum by embedding parallel concepts in a required first-semester seminar taken by all incoming declared CS majors. We introduce students to parallel computing concepts through a series of unplugged activities so that students see parallel approaches as a natural form of solution to a task. We describe a pilot offering of the class and activities, with measurements and analysis of what students self-report and their performance on assessments.

We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.

The undergraduate computer science curriculum is ever-changing but has seen particular turmoil recently. Topics such as machine learning, data science, and concurrency and parallelism have grown in importance over the last few years. As the content of our curriculum changes, so too does the mathematical foundations on which it rests. Do our current theoretical courses adequately support these foundations or must we consider new pedagogy that is more relevant to our students' needs? In this BoF, we will discuss what a modern mathematics curriculum for computer scientists should cover and how we should go about accomplishing this in our classrooms.

Despite only a small portion of unlimited data plan users experiencing throttling each month, it is a prominent source of complaints from users and a significant concern for mobile network operators. We propose a simple mechanism that allows users to choose when they want their data transmission “fast,” and when they want it “slow.” Users still have the same cap on total high-speed transfer before being throttled, and hence may still be subject to throttling, but now they are given some control. We propose a basic model of payoffs, and demonstrate that the proposed mechanism would be preferable to the user over the throttling policies currently in place. We then consider the impacts that extend beyond a single user, and provide a framework for determining the aggregate effects of such a mechanism.

Enrollments in CS have been climbing dramatically in recent years at large schools, especially those in the top-tier for CS. This type of growth is part of the normal cycle for CS and is expected anytime that the public perceives that the job market for computing related fields is strong. It is unclear how much of this growth is currently seen on other campuses. The purpose of this BoF session is to discuss what educators at smaller campuses, and particularly liberal arts schools, are currently seeing in regards to enrollment in CS. This information could be of particular interest for those at schools considering cutting programs for economic reasons or those adjusting the number of faculty lines.

Operations research, while not traditionally taught at many small or liberal arts colleges, can be a significant asset to the offerings of a computer science department. Often seen as a discipline at the intersection of mathematics, computer science, business, and engineering, it has great interdisciplinary potential and practical appeal, allowing for recruitment of students who may not consider taking a CS0 or CS1 course. A special topics course in operations research was offered by the computer science department at Southwestern University as an upper-level elective, and it was also cross-listed as a business and mathematics elective. Not only did the course benefit computer science majors who appreciated the applications and different perspectives, but it provided a means for the department to serve a wider population, increased interdisciplinary education, and resulted in a filled-to-capacity upper-level course in computer science for the first time in recent memory. This course is now being considered as a permanent elective that will interest computer science majors and minors as well as draw in students from disciplines across campus. For departments with limited faculty resources for teaching non-major courses, offering an operations research course provides an alternative that simultaneously serves the department and the campus as a whole.