Teaching Theoretical Computer Science and Mathematical Techniques to Diverse Undergraduate Student Populations

We share our experience and insights gained from teaching foundations of computer science courses to diverse groups of undergraduate (and at times, also graduate) students coming from a broad variety of educational and social backgrounds. Among all required courses of contemporary Computer Science (CS) curricula across the US and Canadian universities, at most institutions (except for the very top research universities), theoretical computer science courses tend to be among the least popular. The reasons behind these prevalent attitudes among CS college students (esp. the undergraduates) tend to fall into two categories: i) theoretical CS courses are "all math" requiring proofs and rigorous formal reasoning that many CS and other engineering students aren't (yet) comfortable with; and ii) "why do we need all this theory anyway" if our career goal is to become software engineers, develop the next cool mobile app, and similar. Yet, most research universities, as well as quite a few non-research colleges, require at least 1-2 semesters of core undergraduate coursework in theoretical or foundational CS. We summarize some interesting lessons learned from teaching theoretical CS to mostly undergraduate upperclassmen (as well as a few non-traditional students) at two prominent public research universities in the US Pacific Northwest, as well as at comparable institutions in Canada (specifically, British Columbia). While the academic and professional backgrounds of the two authors of this paper are considerably different, we also share quite a bit in common: in particular, both of us have spent several years in high-tech industry prior to returning to the academic world as Computer Science faculty. In particular, when teaching various CS courses, we try to relate concepts and techniques covered to the "real-world" applications, and in particular the recent and current technology challenges and R&D done in industry. We have applied this general philosophy to virtually all courses we have taught, including the very theoretical ones -such as those on Automata and Formal Languages. The goal is to get CS and other Engineering students intrigued by how, for example, finite automata or context-free grammars are used in compilers and interpreters (parsing, lexical analysis), or the formal specification of programming languages -as well as to the more recently emerged technologies, such as computational/applied Natural Language Processing (NLP). Without sacrificing rigor, we try to present highly mathematical content in a manner that relates theoretical models and proofs of their properties to practical challenges in computer science and engineering. Some additional challenges we have encountered while teaching Theory of Computing courses stem from very diverse educational backgrounds of the students we have encountered: from graduate students overcoming true or perceived deficiencies in the CS foundations, to undergraduates transferring from local community colleges, many of whom still struggle with formulating a mathematical proof of any kind. This mix of students provides unique challenges, but also opportunities -for example, to revisit teaching methodologies for the "mathematical side of computer science" curricula, how to best relate theory to practice (esp. in terms of technologies and applications these diverse students can most readily relate to), and how to best get students of broadly varying backgrounds actively engage in class