Instructor Information
- Nicole Eikmeier, Assistant Professor of Computer Science
- Preferred name: Professor Eikmeier (she/her)
- Email: eikmeier@grinnell.edu
Please feel free to contact me by email if you have questions that do not require an office hours appointment. In the evenings and on the weekends, I aim to prioritize non-work areas of my life, so you may not hear back from me until up to 24 working-hours after your email. I encourage you to also find balance between your schoolwork and other areas of your life.
- Office Hours: Book online at calendly.com/eikmeier.
I look forward to meeting with you to discuss any aspect of our course, so please do not hesitate to book an appointment. You can find times for office hours on our course website but I will add times in calendly as things fill up. If available times in calendly don’t work for you, please send me a quick email with some times that do work for you so we can find a time to meet. If my door is closed, please assume that I am in either an in-person or online meeting.
Office hour times are tentatively set for: Mondays 2pm – 3:45pm; Wednesdays 10am – 12pm; Thursdays 2:30pm – 4:00pm
Logistics
Class meets Tuesdays and Thursdays in Noyce 3821.
- Section 01: 8:30am – 9:50am
- Section 02: 1:00pm – 2:20pm
Textbook
We will use Michael Sipser’s Introduction to the Theory of Computation (3rd edition). The second edition of the text will likely suffice, but may be missing things or have different page numbers. I do not endorse the use of pirated copies. I will distribute additional reading and material as needed.
Communication & Software
We will use email for communication in this class, and readings, problem sets, and labs will be submitted on Gradescope. All of the important course information will be found on the course website: eikmeier.sites.grinnell.edu/csc-341-fall-2024
Mentoring Sessions
This course employs the use of a mentor to aid you in navigating the course. Our course mentor will host 1 – 2 mentor sessions throughout the week. Mentor Sessions may review course content, provide practice problems, or provide help with problem sets or labs.
- Mentor: Erin Jarvis (she/her) jarviser2@grinnell.edu
- Mentor Session Times: TBD
Course Overview, Topics, and Learning Outcomes
In this course, we will study the theory of computation and use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:
- Deeply understand a problem and its potential corner cases.
- Prove properties of a problem, e.g., the correctness of candidate solutions.
- Reduce a problem to another problem.
- Categorize a problem as easier or harder than other problems in a precise way.
- Regular Languages: Machine- and linguistic-based models; Nondeterminism; Equivalence of models; Closure operations, properties, and decision procedures; Irregularity (the pumping lemma)
- Context-free Languages: Models and properties
- Decidable Languages: Turing machines, low-level and high-level operations; Properties and variants
- Complexity Theory: P vs. NP; Cook’s theorem, NP-completeness, and reductions; Space complexity and Savitch’s theorem
- Decidability Theory: Decision procedures for Turing machines; Undecidability and reductions; The post-correspondence problem; Rice’s theorem; The recursion theorem; Logical theories
- Special Topics in the Theory of Computation
- Represent a problem using a regular model of computation.
- Prove closure and algorithmic properties of the regular languages.
- Prove the irregularity of a problem.
- Represent a problem using a context-free model of computation.
- Represent a problem using a Turing machine.
- Prove closure and algorithmic properties of Turing machines.
- Prove that a problem is in a particular time complexity class.
- Prove that a problem is NP-complete by way of a reduction.
- Explain the practical ramifications of the P vs. NP problem.
- Prove that a problem is in a particular space complexity class.
- Describe the essential characteristics of problems belonging to each of the major complexity classes.
- Describe the relationships between various time and space complexity classes.
- Prove the decidability of a given machine analysis algorithm.
- Prove the undecidability of a given problem by way of a reduction.
- Prove the undecidability of a given problem through Rice’s Theorem.
- Describe the practical ramifications of computational undecidability.
- Describe problem-solving strategies for dealing with intractable problems.
Class Components
There will be 5 components to your grade in this class:
- Attendance & Participation (mostly required)
- Readings (done individually, due before class each day)
- Labs (done in groups, mostly during class)
- Problem Sets (collaboration allowed, completed individually)
- Exams (individual in-class assessment)
Attendance & Participation
Your attendance and participation in class is an integral part of your learning, thus it is a requirement. Class will start promptly at the start time each day, so you should be sure to arrive before class starts. I will hold my end of the social contract by making sure we end class on time every day.
On each day of class, you will be marked as present and engaged (or not). To be marked positively you will minimally need to:
- Arrive on time for class, do not leave early
- Arrive prepared for class activities by having completed the required reading
- Actively engage and participate in all lab work
- Engaged in full group discussion/lecture (not on phone, etc.)
When you miss a class day (excused or unexcused) you are still responsible for the material covered in class. You should review readings, labs, and notes from class and consult with peers who were in class the day you missed to catch up.
If you miss a significant number of class days (including via excused absences) it may be difficult for you to meet the expectations of the course. Additionally, if you miss more than one class period in a row without notice to me, you should expect to hear from me as well as student advising (via SAL). The goal here is not to scold you, but to make sure you’re aware of the situation and have the information you need to stay on track or withdraw from the course if completing it successfully is no longer feasible.
Unexcused absences: An excessive number of unexcused absences (including being marked as late or not participating) will impact your grade in the following manner. If you are unexcused for more than 2 days, you may not receive a grade higher than a B+ in our class. Similarly, if you are unexcused for more than 4 days you may not receive higher than a C+ in our class. Finally, if you are unexcused for more than 6 days, you may not receive a grade higher than a D.
Excused absences: You may be excused for a class under certain situations. I encourage students who plan to observe holy days that coincide with class meetings or assignment due dates to consult with me in the first three weeks of classes so that we may reach a mutual understanding of how you can meet the terms of your religious observance and also the requirements for this course. Likewise, please discuss with me in the first three weeks of the semester if you will be absent due to athletic events.
You may also be excused from class in the even of an emergency or illness. I will not require proof or details, just please inform me as soon as you are able. If you attend class with respiratory symptoms, please consider wearing an N-95 mask to protect others.
Readings
Accompanying most class days there will be a required reading that you are to complete before class starts. After reading, find corresponding questions on the schedule, and answer those questions in Gradescope. These are meant to be an accountability device – motivation to complete the reading before class. My hope is that the questions will help you to find the important information or help you identify the things that are unclear.
Readings will be graded on a scale of full credit, or no credit. Answers will receive full credit if they are either correct, or incorrect while showing evidence of significant effort. Incomplete answers or work that is incorrect with little evidence of effort will earn zero.
There will be no revisions on Readings.
There is no 48-hour grace period for Readings.
Labs
Most class days will consist of a lab component. Lab exercises give you a chance to engage with our class material in a low-stakes way, with the benefit of collaboration from your peers. You will turn in each lab as a group, and they will be graded on a scale of full credit, half credit, or no credit. Work that is correct or nearly correct with evidence of significant effort will earn full credit. Incomplete submissions or work that is incorrect with little evidence of further effort will earn half credit. Missing work or work that shows very little effort will earn a zero.
There will be no revisions for lab exercises.
Problem Sets
Problem Sets are opportunities for you to demonstrate mastery of the course learning goals by applying these concepts and skills to problems larger in scope and complexity than the labs. Submissions that receive full credit will minimally meet the following criteria:
- The problem set must be complete, by providing answers to all questions, and/or following all instructions.
- Submission is neat. If hand-written it is legible, and if typed it is formatted appropriately using Latex or word equations.
- Answers are correct or nearly correct, showing full understanding of course material.
You will have the opportunity to revise problems sets using our token system.
Exams
We will have three exams this semester. The dates are as follows:
- Exam 1: Tue Oct 8
- Exam 2: Tue Nov 12
- Exam 3:
- (section 1) Tue Dec 17, 2pm-5pm
- (section 2) Thur Dec 19, 2pm-5pm
Exams will be on paper in class, however you will be allowed to use a limited set of notes. More details will be given as the exam approaches. You may be allowed to revise one problem from each of the first two exams using our token system.
Revision Tokens
Tokens are meant to give you the opportunity to revisit work from our course that challenged you the first time around. I hope this system will remove some of the pressure of “performance” in our course, since you may resubmit some things without penalty.
You may earn tokens by supporting your peers and being an active member of the Grinnell computer science community. Eligible opportunities will be listed at the start of each class. You will be limited to 6 total tokens, 3 supporting your peers and 3 attending academic events. (See Token FAQ)
Revise Problem Set: You may use one token to resubmit a Problem Set. You may not resubmit a problem set which you did not turn in. This system is meant to encourage you to take a second look at concepts that you may have struggled with initially, not as a way to turn in things late. Problem Sets must show a good faith effort initially in order to be revised. The same collaboration policies apply as in the original submission.
Revise Exam Problem: You may use one token to revise one exam problem. After each of the first two exams, I will announce which of the problems are eligible for revision, and you may choose to revise up to one of them. You are not allowed to obtain help from any person or resource other than me (Professor Eikmeier), the textbook, your notes, and our course webpage.
A note on feedback: I urge you to read all feedback given through Gradescope, especially on labs and problem sets. Feedback on these assessments is essential for you to understand how to improve, and sometimes you may receive full credit even though you would not on an exam. In Gradescope, viewing feedback means clicking through a few buttons beyond your grade.
A note on instructor/grader workload:
In order for your instructor to maintain sanity this semester, no more than three of your problem sets or revisions (problem sets or exams) may submitted in a single week. This will help to keep the grading load reasonable. While revised work is not officially due until the last day of finals, this means you cannot submit more than 2 revisions in a single week.
Letter Grades
The graded components for this course will contribute to your total grade in the following proportions:
| Readings | 5% |
| Labs | 20% |
| Problem Sets | 30% |
| Exams | 45% |
| Attendance & Participation | only as a penalty |
There will be no curves or competitive grading in this course; every student has an opportunity to earn an A. Your letter grade will be determined with the usual scale:
| A | 93 – 100% |
| A- | 90 – 93% |
| B+ | 87 – 90% |
| B | 83 – 87% |
| B- | 80 – 83% |
| C+ | 77 – 80% |
| C | 70 – 77% |
| D | 60 – 70% |
| F | 0 – 60% |
Course and College Policies
Late Work
All assignments (readings, labs, and problem sets) are to be turned in electronically on the day they are due. I am aware that there are a number of things outside of your control that may affect your ability to complete work on time, so any lab or problem set may be submitted up to 48 hours late without prior approval and without penalty. I do appreciate knowing if you plan to turn in work late.
If you believe you will need an extension of more than 48 hours, please talk with me as soon as possible. Assignments turned in more than two days late, without prior approval (before the original due date) of the instructor will not be accepted. Please refer to the Student Workload statement below, to emphasize that you should attempt to follow the posted deadlines. Please keep in mind that if you turn in work late, I may not be able to grade it as quickly as you or I hope.
Readings will not be accepted late. If you have a planned absence, you should arrange to complete the reading ahead of time. If you have an un-planned excused absence, please communicate with me about getting the accompanying reading excused if needed.
Incomplete Grades
All work for the course is due by 5:00 pm on the last day of finals (12/20/2024). In exceptional circumstances, incomplete grades can be granted. Talk with me if you think you might need an incomplete to complete all the requirements of the course.
Student Workload
You can expect to spend 12 hours per week on this course, including all in-class and out of class time. This number is based off the Grinnell Guidelines for credit-hours. Since our class meets for approximately 3 hours each week, you can expect to work 9 additional hours outside of class time. This includes: reading and interrogating the textbook, mentor sessions, office hours, problem sets, and general studying.
Academic Honesty
Grinnell College’s Academic Honesty policy is located in the online Student Handbook. It is the College’s expectation that students be aware of and meet the expectations expressed in this policy. In addition, in this course, it is my expectation that students may collaborate on the Problem Sets and Labs, however your collaboration must be attributed on Problem Sets.
In this course, you are not allowed to use solutions you find on the internet, and further, you are not allowed to search for information about problems on the internet. This includes any AI assistive tools such as ChatGPT. I know that there is great temptation to look for solutions online when things get difficult. I will provide you with numerous resources to get help which include office hours, group class work, mentor sessions, and revisions. It is my hope that allowing you to resubmit problem sets without penalty eases some of the pressure that you might feel.
If you have questions about how a particular assignment relates to the College’s policy, or how to attribute your collaboration, I will gladly consult with you in advance of the assignment’s due date. Asking about course policies is never an academic honesty violation, but violating academic honesty policies is a serious issue whether you do so knowingly or unknowingly.
Title IV and Pregnancy Related Conditions
Grinnell College is committed to compliance with Title IX and to supporting the academic success of pregnant and parenting students and students with pregnancy related conditions. If you are a pregnant student, have pregnancy related conditions, or are a parenting student (child under one-year needs documented medical care) who wishes to request reasonable related supportive measures from the College under Title IX, please email the Title IX Coordinator at titleix@grinnell.edu. The Title IX Coordinator will work with Disability Resources and your professors to provide reasonable supportive measures in support of your education while pregnant or as a parent under Title IX.
Students with Disabilities
I encourage students with documented disabilities, including invisible disabilities such as chronic illness, learning disabilities, and psychiatric disabilities, to discuss appropriate accommodations with me. You will also need to have a conversation about and provide documentation of your disability to the Coordinator for Disability Resources, located on the ground level of Steiner Hall (641-269-3124).
Technology Usage Policy
Materials you have obtained from this course including problem sets and exams should not be distributed outside of the members of our class. Live synchronous sessions should not be recorded by students. You may not use your cell phone during class, and it should be silenced and put away during class time. Laptops and tablets are allowed for note-taking, however you should personally assess if these devices are a distraction to your learning.
AI assistance tools like ChatGPT are not permitted in this class. These tools can do a very good job of imitating the work of students. Often, they even produce correct code and proofs. However, because you are newer to the topics of this class, these tools are more likely to interfere with your learning than to support it. Submitted work that includes text produced by an AI tool will receive an automatic zero. Submitting AI tool output without citation is a violation of the academic honesty policy and will be handled through the College’s formal academic honesty process.
Inclusion Statement
It is my intention that students from all backgrounds and perspectives will be well served by this course, and that the diversity that students bring to this class will be viewed as an asset. I welcome individuals of all ages, backgrounds, beliefs, ethnicities, genders, gender identities, gender expressions, national origins, religious affiliations, sexual orientations, socioeconomic background, family education level, ability – and other visible and nonvisible differences. All members of this class are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the class. Your suggestions are encouraged and appreciated.
Take Care of Yourself
Do your best to maintain a healthy lifestyle this term by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available through campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often beneficial.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, I strongly encourage you to seek support. Student Health and Wellness (SHAW) is here to help: call 641-269-3230 and visit their website at grinnell.edu/about/offices-services/student-health. Consider reaching out to a friend, faculty, or family member you trust for help getting connected to the support that can help.
If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:
- Need to Talk Line: 641-269-4404 (available 24/7 for counseling needs)
- 24/7 Suicidal Hotline: 1-800-273-8255
- If the situation is life threatening, call 911
Misc. Resources
- Databases, journal articles, and more: https://www.grinnell.edu/academics/libraries
- Student Health and Wellness (SHAW): grinnell.edu/about/offices-services/student-health
- Time management, study strategies, and other resources for students from Academic Advising: grinco.sharepoint.com/sites/AcademicAdvising/SitePages/Resources.aspx
- Information about emergency funds, textbook lending library, student food pantry, and loaner laptops: grinnell.edu/about/leadership/offices-services/crssj/fgli-resources
Syllabus Acknowledgements
- The inclusion statement has been taken verbatim from lgbtq.asee.org
- The Take Care of Yourself Section has been adapted from CMU
- I am grateful to my colleagues in Computer Science for generously sharing their course materials (including syllabi) with me. Some of the verbiage may be taken and adapted from current and past instructors.
