2021 Teaching Institute logo

CSC 135: Computability and Formal Languages

Course Description

This is a required upper-division course for all computer science students. It addresses theoretical topics in computer science, in particular proving the equivalence of expressive power for multiple computational models, and the limits of what is computable with each. It is typically taken by Juniors in a lecture setting with 30-40 students.

Before:

Motivation for Redesign

The Computer Science Department has standardized departmental syllabi which give guidance on what to teach in a course, but the guidance is given in each syllabus in multiple possibly confusing ways. This can cause a course to be less focused and spend more time on topics that are unlikely to be assessed. A better specified course may lead to fewer DFWs beause more time can be spent on each assessed topic.

As an example of unfocused and inconsistent information, the CSC 135 syllabus guides what to teach about "regular languages" in three different sections as follows.

In the "course outcomes" section:

Students completing this course will be able to
- Design generators and recognizers for simple regular ... languages and give examples of algorithmically converting from one to the other.
- Explain the limits of regular ... languages and apply a pumping lemma to show a language not to be regular

In the "outcomes" section:

Thorough understanding of:
- Finite automata (deterministic and non-deterministic) and regular expressions
Basic understanding of:
- The pumping lemma for regular languages
Exposure to:
- (No regular language material in this subsection)

In the "expanded list of topics" section:

Regular languages. Regular expressions, deterministic and non-deterministic finite automata, equivalence between the three, limitations and the pumping lemma. (12 hours)

Questions an instructor might have after reading the three syllabus sections:
- Am I free to pick one of the three guides and ignore the rest?
- Do I have to teach everything in every section?
- Do I have to teach only the things mentioned in all three?
- To what depth? What does "thorough"/"basic"/"exposure" and "12 hours" actually mean?

The Association for Computing Machinery (the computer science profession organization) states it's recommended core topics as "knowledge areas" with lists of topics and learning outcomes. An example of their learning outcomes, again restricted to regular language topics:

[Students completing this course will be able to]
1. Discuss the concept of finite state machines. [Familiarity]
2. Design a deterministic finite state machine to accept a specified language. [Usage]
3. Generate a regular expression to represent a specified language. [Usage]
4. Determine a language’s place in the Chomsky hierarchy (regular, context-free, recursively enumerable). [Assessment]
5. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs. [Usage]

This list contains the essential list of topics for the module, but it does so by specifying assessible learning outcomes and a specifier for depth. The specifier is essentially a Bloom's Taxonomy word specifying to what level the material should be taught: knowledge=comprehension, usage=applications, and assessment=analysis.

After:

Rationalization of syllabi learning outcomes

Evidence of Student Learning

By consolidating the three sections of the old syllabus that specified topics to teach, to what level and learning outcome, the guidance is made more coherent and useful. The number of hours specified per topics is removed to allow different teaching styles and methods. Bloom-style depth tags are added to indicate depth. All topics are translated into learning outcomes to make it clearer what is the goal of teaching each topic.

Regular Languages:
[Students completing this course will be able to]
1. Design regular expressions, DFAs and NFAs for simple regular languages [Usage]
2. Convert between regular expressions, DFAs and NFAs [Usage]
3. Argue that a simple language is not regular using the pumping lemma [Assessment]

Besides being clearer, this format is shorter, leading to a syllabus more likely to be read, understood, and followed.

Techniques Incorporated Into Redesign

Discussions on alignment and backward design led me to believe that Computer Science department standard syllabi could benefit from a redesign focusing on learning outcomes.

As a next step, and instructor could use "backward design" to devise intermediate learning outcomes in support of each higher level goal, being mindful that each intermediate outcome should be aligned with the ultimate learning outcome.

Assessment of Redesign Project

The benefits of this project will be assessed indirectly. Both DFW rates and student evaluations of teaching scores should improve after implementation.

Equitable & Inclusive Outcomes for Students

It is often our most marginalized students who receive a disproportionate number of DFWs. By focusing on quality everyone's outcomes should be improved.

Reflection: Challenges and Lessons Learned

Time, as always, is the biggest challenge for faculty at Sac State. There is never enough of it to do the non-deferrable parts of our jobs. Search committee meetings can''t be deferred, Secondary RTP committees can't be deferred, accreditation preparation can't be deferred. Along with a teaching load of four classes, such non-deferrable tasks leave precious little time for the creative (and alas deferrable) aspects of the job... research and curricular development.

I felt like I had very little time to invest in the course improvements during the academic year that TI-21 opened my eyes to. As I revise my courses this summer I will pay special attention to backward design and outcome alignment, and then forward that knowledge to fellow teachers via the department syllabus revision process.

Faculty Biography

Faculty Bio
	I was born in Anaheim, grew up in Santa Cruz, and have lived in Davis since 1995. I got my degrees from Stanford, Oxford, and UC Davis, and liked Davis enough that I decided to stay. I've been at Sacramento State since 2002. I mostly teach theoretical topics like computer algorithms, computer theory, and cryptography, but enjoy programming so much that I once asked if I could teach introductory programming, which I then did for half a dozen years. I've also been the chief judge and problem-setter for the programming contests that the department runs. In my free time I like to swim and make simple delicious vegetarian foods like hummus, salsa, and yogurt.

**Program Sponsors**
	This work was supported by the Sacramento State and The Higher Education Emergency Relief Fund