Syllabus
Computer Science 204 Fall 2025
Course Instructor
- Instructor Name: Dr. Gregory M. Kapfhammer
- Office Location: Alden Hall 108
Please visit the instructor’s web site for more information!
Instructor Appointments
- Monday: 11:00 AM – 12:00 noon
- Tuesday: 4:00 PM – 5:00 PM
- Wednesday: 4:00 PM – 5:00 PM
- Thursday: 11:00 AM – 12:00 noon
- Thursday: 2:30 AM – 4:00 PM
- Friday: 11:00 AM – 12:00 noon
- Friday: 3:00 PM – 4:00 PM
All instructor appointments are 15-minute time slots and take place in Alden Hall, Room 108.
Course Description
A study of theoretical computer science concepts that addresses both the fundamental nature and limitations of computation and the ways in which to practically apply these insights. While using a machine-centered abstraction of computation implemented in a general-purpose programming language, students investigate what is computable and explore the categories and complexity of computational problems. Participating in hands-on activities that often require teamwork, students gain experience in the use of a programming language to characterize a problem solving strategy. During a weekly laboratory session, students use industry-grade technology to complete projects, reporting on their results through both written documents and oral presentations. Students are invited to use their own departmentally approved laptop in this course; a limited number of laptops are available for use during class and lab sessions.
- Prerequisite: CMPSC 102 or permission of instructor
- Distribution Requirements: QR, SP
Course Textbook
- What Can be Computed? A Practical Guide to the Theory of Computation by John MacCormick. The description of this textbook is: “An accessible and rigorous textbook for introducing undergraduates to computer science theory.” Please see the textbook’s web site for more details, including an outline, course slides, and source code examples.
Learning Objectives
Allegheny College’s educational program is designed so that its graduates are able to:
- AC-1: Think critically and creatively.
- AC-2: Communicate clearly and persuasively as speakers and writers.
- AC-3: Invoke multiple ways of understanding to organize and evaluate evidence, and to interpret and make sense of their experiences and the experiences of others.
- AC-4: Apply their knowledge and learning to engage in informed debate, and to analyze and solve problems.
Computer Science 204 is a course taken by all Computer Science majors and often taken by many students who major or minor in Computer Science, Data Science, or Informatics. Graduates with the Computer Science major — who all take the Computer Science 204 course — must demonstrate their attainment of these learning objectives:
- CS-1: Demonstrate and be able to communicate the knowledge of data types, algorithms, and mathematical principles behind discrete objects.
- CS-2: Use scientific and theoretical methods to design, implement, evaluate, deploy, improve, maintain, and document software and hardware systems.
- CS-3: Apply and articulate key concepts from a specialization area where the interconnection between software and hardware is important and evident.
- CS-4: Able to communicate technical details of the produced software and hardware artifacts both in writing and orally.
All five of the Computer Science major’s learning objectives support the QR and SP distribution requirements and the College’s learning objectives.
The specific learning objectives for Computer Science 204 are as follows:
- CS-204-1: Use both intuitive analysis and theoretical proof techniques to correctly distinguish between problems that are tractable, intractable, and uncomputable.
- CS-204-2: Correctly use one or more variants of the Turing machine (TM) abstraction to both describe and analyze the solution to a computational problem.
- CS-204-3: Correctly use one or more variants of the finite statement machine (FSM) abstraction to describe and analyze the solution to a computational problem.
- CS-204-4: Use a formal proof technique to correctly classify a problem according to whether or not it is in the P, NP, NP-Hard, and/or NP-Complete complexity class(es).
- CS-204-5: Apply insights from theoretical proofs concerning the limits of either program feasibility or complexity to the implementation of both correct and efficient real-world Python programs.
The learning objectives for Computer Science 204 enable the attainment of both the Computer Science program learning objectives that in turn support the attainment of the College’s learning objectives. Throughout this course, the instructor will reference these learning objectives, connect them to the course activities, and invite students to reflect on their attainment of them. In addition to administering an assessment of learning objective attainment as a part of the final examination, the course instructor will ask students to complete a self assessment of their attainment of these learning objectives.
Course Policies
Assessment
The grade that a student receives in this class will be based on the following categories. All of these percentages are approximate and, if the need to do so presents itself, the course instructor may, for instance, change the assigned percentages during the academic semester.
| Category | Percentage |
|---|---|
| Class Participation | 10% |
| Proofgrammer Skill-Checks | 10% |
| Proofgrammer Knowledge-Checks | 10% |
| Proofgrammer Charettes | 10% |
| Executable Examinations | 20% |
| Proofgrammer Presentations | 40% |
These assessment categories have the following definitions:
Class Participation: Students are expected to regularly attend and actively participate in all of the class and laboratory sessions, as outlined on the course schedule. After either an unexcused absence or a late attendance to either a class or a laboratory session, a student’s weekly class participation grade will be reduced. Students who need to miss class or attend class late for an excused reason should use email to communicate their situation to the course instructor in a timely fashion. A student’s weekly class participation grade will be reduced if they are frequently observed, during either class or laboratory sessions, undertaking non-course-related activities like viewing email, browsing social media, or looking at any other content not about the theory of computation.
Proofgrammer Skill-Checks: Completed during a Tuesday laboratory session, these skill-checks are online, cumulative assessments covering all prior technical material from the prior course sessions, as outlined on the course schedule. Unless prior arrangements are made with the instructor, all students should use their computer to take these skill-checks on the scheduled date and to complete it in the stated location while taking no more than the required amount of time. Designed to prepare learners for the three executable examinations, each skill-check is an executable assessment that students complete through the use of GitHub, a text editor like VS Code, and the Python programming tools on their laptops. During the completion of a skill-check, students may use external sources, including artificial intelligence coding assistants, provided that they cite these sources and explain how they used them to complete the skill-check.
Proofgrammer Knowledge-Checks: Completed individually during a Thursday laboratory session, these knowledge-checks are in-person, cumulative assessments covering all prior material from the prior course sessions, as outlined on the course schedule. All students should be prepared to answer questions about the conceptual knowledge and technical skills in the field of theoretical machines, with a focus on both the material presented and discussed during instructor presentations and investigated as a part of the team-based proofgrammer presentations. Students may not use any external sources (e.g., artificial intelligence assistants, online sources, or written notes) or devices (e.g., laptop, tablet, or mobile phone) during an in-person knowledge check.
Proofgrammer Charettes: Completed in the second half of a Thursday classroom session, these discussion workshops invite students to collaboratively pose and answer questions in the field of theoretical machines. During a charette session, students will first pose questions about the less-well-understood technical and mathematical course content that was presented during the prior laboratory sessions. After posing a series of new questions and revising past questions that have not yet been answered, students will work in teams to answers chosen questions. Once the class members approve the answer for a question, the team members who correctly answered the question will record their contact information and a brief answer in the charette tracking system.
Executable Examinations: An executable examination is an online, cumulative assessment covering all of the material during all of the course sessions, as outlined on the course schedule. Unless prior arrangements are made with the instructor, all students should use their computer to take each executable examination on the scheduled date and to complete it in the stated location while taking no more than the required amount of time. Each cumulative executable examination will complete by a student through the use of GitHub, a text editor like VS Code, and the Python programming tools installed on their laptops. During the completion of the final examination, students may use external sources, including artificial intelligence coding assistants, provided that they cite these sources and explain how they used them to complete the final examination.
Proofgrammer Presentations: Completed by assigned teams of students during a Tuesday laboratory session, these in-person presentations are on technical topics assigned by the course instructor. Students will use all the tools setup on their laptops to implement a Python program that solves the stated problem and/or completes the required proof, ensuring that it is built as a stand-alone script with its dependencies and virtual environments managed by
uv. Along with the three proofgrammer presentations given per module, assigned teams of students will also complete two retrospective presentations that review the content covered during the first two modules of the course. For each team assigned to give a proofgrammer presentation, there will be another assigned team of students that is responsible for posing questions to the presenting team and evaluating the presentation. For all proofgrammer presentations, both the presentation and evaluation teams will receive a grade for their submitted work. Although both the presentation and evaluation teams may use external sources, including artificial coding assistants, during the completion of their materials, they must cite their sources. Except for the slides published on the course website, the presenters may not use any external sources during either the presentation or the evaluation phases. All proofgrammer presentations must be completed through the use of Quarto, RevealJS, Markdown, Git, GitHub, and the GitHub Flow model. All work for a presentation must be available, in final form, as a pull request in the GitHub repository for the course web site, no later than 11:59 PM on the day before the team is scheduled to present. Each student member of a presentation team must use Git and their own GitHub account to commit their work through to the pull request that their team creates for the presentation. In addition to giving the presentation itself, every student on a presentation team must make a contribution to the presentation slides in the form of commits to the pull request.
Course Schedule
Module Overview
- Module One:
- Topic: Introduction to Theoretical Machines
- Weeks: One through Six
- Technical Topics:
- Chapter One: Introduction to the Theory of Computation
- Chapter Two: What is a Computer Program?
- Chapter Three: Some Impossible Python Programs
- Chapter Four: What is a Computational Problem?
- Chapter Five: Turing Machines: The Simplest Computers
- Module Two:
- Topic: Foundations of Theoretical Machines
- Weeks: Seven through Eleven
- Technical Topics:
- Chapter Six: Universal Computer Programs: Programs that Can Do Anything
- Chapter Seven: Reductions: How to Prove a Problem is Hard
- Chapter Eight: Nondeterminism: Magic or Reality?
- Chapter Nine: Finite Automata: Computing with Limited Resources
- Module Three:
- Topic: Advanced Topics in Theoretical Machines
- Weeks: Twelve through Sixteen
- Technical Topics:
- Chapter Ten: Complexity Theory: When Efficiency Does Matter
- Chapter Eleven: Poly and Expo: The Two Most Fundamental Complexity Classes
- Chapter Twelve: PolyCheck and NPoly: Hard Problems that are Easy to Verify
- Chapter Thirteen: Polynomial-time Reductions: Proving X is as Easy as Y
- Chapter Fourteen: NP-Completeness: Most Hard Problems are Equally Hard
Schedule Details
Week-by-Week Highlights
- Basics:
- Start Semester: Week One
- Fall Break: Week Seven
- Mid-Term Grades Submission: Week Nine
- All-College Programming: Week Eleven
- Thanksgiving Break: Week Fourteen
- End Semester: Week Sixteen
- Final Examination: Week Sixteen
- Proofgrammer Skill-Checks:
- Skill-Check One: Week Five
- Skill-Check Two: Week Ten
- Skill-Check Three: Week Fifteen
- Proofgrammer Knowledge-Checks:
- Knowledge-Check One: Week Five
- Knowledge-Check Two: Week Ten
- Knowledge-Check Three: Week Fifteen
- Proofgrammer Presentations:
- Module One Presentations:
- Week Two
- Week Three
- Week Four
- Module One Retrospective Presentations:
- Half of Class: Week Six on Tuesday
- Half of Class: Week Six on Thursday
- Module Two Presentations:
- Week Seven
- Week Eight
- Week Nine
- Module Two Retrospective Presentations:
- Half of Class: Week Eleven on Tuesday
- Half of Class: Week Eleven on Thursday
- Module Three Presentations:
- Week Twelve
- Week Thirteen
- Week Fourteen
- No module three retrospective presentations
- Module One Presentations:
- Interim Executable Examinations:
- Interim Executable Examination One: Week Six
- Interim Executable Examination Two: Week Eleven
Important Dates
- Final Executable Examination
- Examination Code: C
- Date: Monday, December 8, 2025
- Time: 9:00 AM – 12:00 Noon
- Location: Alden 109
Weekly Cadence
Monday: - Presentation teams finalize GitHub pull request for presentation by 11:59 PM
- All Python programs must run as a stand-alone script managed by
uv - All presentation slides must be built with Quarto and RevealJS
- All content submitted to the pull request must be in its final form
- All students in a presentation team must contribute to the pull request
- Excepting documented, extenuating circumstances, no content allowed after deadline
- Evaluation teams submit the evaluation questions for their assigned team to GitHub
Tuesday: - Instructor presentation and activities as a deep-dive into the week’s technical topic
- Technical and engineering knowledge and skills in the field of theoretical machines
- Teams complete their final practice steps for their proofgrammer presentations
Tuesday Laboratory Session: - Proofgrammer presentations and evaluations by all student teams
- Teams and presentation topics assigned at the start of each week
- On designated weeks, complete proofgrammer skill-checks and knowledge-checks
- On designated weeks, complete the two interim executable examinations
Wednesday: - Teams finalize GitHub pull request for retrospective presentation by 11:59 PM
- All content submitted to the pull request must be in its final form
- All students in a presentation team must contribute to the pull request
- Excepting documented, extenuating circumstances, no content allowed after deadline
Thursday: - Instructor presentation and activities as a deep-dive into the week’s technical topic
- Proofgrammer charette sessions to collaboratively pose and answer questions
- Confirm that all technical topics are well-understood by each proofgrammer
Assessment Policies
Unless exempted by the instructor, students must abide by the following assessment policies:
Assignment Submission
All assignments will have a stated due date shared through GitHub, GitHub Classroom, and/or the Proofgrammers Discord. No credit will be awarded for any course work that you submit to the incorrect GitHub repository or website. Unless special advance arrangements are made with the instructor to address extenuating circumstances or a student pays a document engineering token, no work will be accepted after the deadline.
Assignment Evaluation
Using a report that the instructor shares with you through your GitHub repositories devoted to work in the field of theoretical machines, you will privately receive a grade for and feedback on your projects. Your grade will be a function of whether or not you (a) completed work that fulfills the project’s specification and (b) submitted it by the deadline to the stated platform.
Proofgrammer Tokens
Students may “spend” up to three “tokens” that they may use to retake certain assessments. After using a provided GitHub repository to request their use of a token, ensuring that they follow all guidelines, students may use a token to re-take either a proofgrammer skill-check or knowledge-check. Students cannot use a token for any interim or final executable examination or any type of presentation or evaluation. Outside of using these three tokens — or severe, extenuating, and unexpected circumstances that are well documented — the instructor will not grant any requests for extensions or assignment re-reassessments.
Course Attendance
It is mandatory for all students to attend every one of the course sessions with all the equipment needed for this course, including a charged laptop, a laptop power supply, and a web-enabled device that can scan a QR code (e.g., a mobile phone or a tablet). If, due to extenuating circumstances beyond your reasonable control, you will not be able to attend a session, then, whenever possible, please communicate with the instructor at least one week in advance to describe your situation. In the context of this course, “missing class” includes both coming to a class or laboratory session after attendance was taken (i.e., “being late” for class) or not attending the session. After a student misses more than two weeks of class and laboratory sessions (i.e., misses more than a total of six classes and two laboratory sessions), their final grade in the course will be reduced by one letter grade. Students who have any signs of illness should not attend any of the in-person course or laboratory sessions. With that said, missing class for any reason — including illness or attendance at any College-approved event — will still be recorded by the instructor as a course absence.
Class Preparation
In order to minimize confusion and maximize learning, students must invest time to prepare for the class sessions that focus on the concepts, tasks, and tools of theoretical machines. Although the course instructor and the student technical leaders will always be available to serve as guide for individual students, teams of students, and the entire class, it is expected that students will volunteer to lead and actively contribute to all class sessions. Only those students who have prepared for class by reading and running the assigned material and completing the assigned projects will be able to effectively participate in these class discussions. To help students remain organized and to effectively prepare for classes, the instructor will maintain a list of course slides and a course schedule with reading assignments, programming suggestions, and other important information about the course.
Seeking Assistance
Students who are struggling to understand the knowledge and skills developed in this course’s exploration of theoretical machines are encouraged to seek assistance from the instructor and/or the student technical leaders. Students should, within the bounds of the Honor Code, ask and answer questions on the Proofgrammers Discord Server; please request assistance from the instructor and student technical leaders first through public Discord channels before sending an email or a direct message. Students who need more assistance are invited to schedule a meeting through the instructor’s appointment scheduler and come to the meeting with details about their question. Students can see the office hour schedule for student technical leaders by viewing the list of student technical leaders and by monitoring announcements in the Allegheny College Computer Science Discord Server.
Using GitHub and Discord
This course will primarily use GitHub and Discord for all course communication. We will use GitHub for the sharing of both source code and documentation for course projects and for reporting issues in those materials. We will use two distinct Discord servers for all course discussions. The Proofgrammers Discord Server provides a way for members of the theoretical machines community to use text and video to chat with each other and will be the main forum for discussing the professional and technical content in the field of this course. The Allegheny College Computer Science Discord Server will be the main forum for Department of Computer and Information Science announcements. Finally, any content that a student wants the instructor to assess (e.g., the work for a document engineering tool building project) must be in a GitHub repository created by a GitHub Classroom-affiliated link.
Using Email
Although we will primarily use the Proofgrammers Discord Server for class communication, the course instructor will sometimes use email to send announcements about important matters such as changes in the schedule. It is your responsibility to check your email at least once a day and to ensure that you can reliably send and receive emails. This class policy is based on the statement about the use of email that appears in The Compass, the College’s student handbook; please see the instructor if you do not have this handbook.
Honor Code
The Allegheny College Academic bulletin describes The Academic Honor Program that governs the entire academic program at Allegheny College. The Honor Program applies to all work that is submitted for academic credit or to meet non-credit requirements for graduation at Allegheny College. This includes all work assigned for this class (e.g., presentation slides, skill checks, knowledge checks, executable examinations, and course projects). All students who have enrolled in the College will work under the Honor Program. Each student who matriculates at the College acknowledges this Honor Code pledge:
I hereby recognize and pledge to fulfill my responsibilities, as defined in the Honor Code, and to maintain the integrity of both myself and the College community as a whole.
Working Effectively as Proofgrammer
Students who create the source code and documentation for their theoretical machines projects should ensure the implementation of a high-quality final product. While students are permitted to use a wide variety of proofgramming tools, such as integrated development environments, testing frameworks, automated debuggers, and code generators (e.g., systems that leverage large language models through GitHub Copilot) and documentation sites such as StackOverflow, they must take final responsibility for all the source code and documentation that they submit for this course (e.g., for the Proofgrammer Presentations), including artifacts that are generated by a tool like an AI coding assistant such as Gemini or OpenCode.
This policy means that every student must work as an effective proofgrammer by documenting the sources for their work and verifying the correctness, maintainability, and long-term reliability of all source code and documentation that they submit. As such, students who use software tools to create or revise content are responsible for citing their sources and demonstrating their understanding of it as a part of any follow-on written or oral assessment. Moreover, all students in the class are responsible for all of the source code and documentation submitted to the GitHub repository that hosts the course projects, including any tool-generated software artifacts. This means that every student should be able to answer questions, during either an in-person or online discussion, about any theoretical machines content, including that which was automatically generated by a software tool.
Students who are effective documentation engineers also pledge to always abide by the ACM Code of Ethics and Professional Conduct and the ACM Technology Policy Council’s Principles for the Development, Deployment, and Use of Generative AI Technologies. Unless the students in this course furnish a different governing contract, they also pledge to follow, in addition to these two ACM documents, the principles espoused by exemplary technical organizations, such as Oxide Computer and its public statement of mission and principles.
Disability Services
Students with disabilities who believe they may need accommodations in this class are encouraged to contact Student Accessibility and Support Services (SASS) at 814-332-2898 or studentaccessibility@allegheny.edu. SASS is located in the Center for Student Success in Pelletier Library. Please contact SASS as soon as possible to ensure that approved accommodations are implemented in a timely fashion.
Welcome Message
In reference to software, Frederick P. Brooks, Jr. wrote in chapter one of The Mythical Man Month that “the magic of myth and legend has come true in our time.” Even though it has fundamental limitations, software is a pervasive aspect of our society that changes how we think and act. Since it is important for us to understand the theory of computation, let’s embark on this journey of discovery and innovation as we learn how to become “proofgrammers” who can harness the power of software while recognizing and working around its fundamental limits. Please join together in this adventure in theoretical machines!