Discrete mathematics and probability theory contain foundational material for computer scientists. Despite their importance, instructors often worry that students will find these courses to be too abstract and seemingly disconnected from their future careers. For this experience report, we introduced homework questions throughout our introductory theory courses based on real world applications of the course content. Areas of application included a court case, code correctness, and machine learning ethics. We surveyed students at the beginning and end of the term on their attitudes toward the relevance of the course material. Our results, surprisingly, indicate that a small minority of students (less than 7%) expected the material to be irrelevant to them at the start of the term, and a similarly small number believed that at the end of the term. Our surveys and qualitative feedback also indicate students enjoyed having the problems and wanted them to continue being offered in future iterations of the courses.

Helping struggling students succeed can be one of the most time consuming parts of education, but also has a significant impact on students. This is particularly true in introductory courses like discrete mathematics where students can be rusty on prerequisite content and lack intrinsic motivation for the course material. We evaluate an intervention to help struggling students catch up on material and gain confidence in the course. The intervention involved optional 30 minute one-on-one sessions with a course TA to review content from earlier in the course. The intervention was performed at a large R1 institution in the discrete math course for four academic quarters. We found that while the intervention increased TA workload, there was a notable decrease in DFW-rate for quarters where the intervention was offered, and that students who participated had higher course averages than those who were invited to participate but did not.

We implemented a standards-based grading scheme in an upperdivision course on algorithm design taken by non-CS-majors. The alternate grading system allows students to submit multiple attempts at the same algorithm design problem, while managing grading load by replacing standard point-based scales with a 4- possibility-scale for all problems. The simplified grading system created flexibility in the course structure that allowed us to give students more problems each week than we expected them to complete, covering different aspects of the given topics (e.g., both theoretical and practical approaches to algorithm design). The additional problems allowed for students with different goals and backgrounds to choose different problems and tailor it to their needs. The availability of resubmissions created incentives for students to master difficult topics throughout the term without a final exam. We argue that the simplified grading system is particularly well-suited to courses in algorithm design and courses for students with varying backgrounds and goals.

Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f(n) as n→∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28n, and the best upper bound was 2nlogn− O(n). In this paper, we show that for all n, f(n) ≤ cn for some universal constant c. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call “mixing”. The latter might be of independent interest.