Syllabus

What can a computer do? What problems can be solved and are some more difficult than others? Are there problems that a computer cannot solve?

In this course, you will learn to analyze computational problems within formal mathematical models of computation and begin to understand answers to these questions.

The textbook for this course is Introduction to the Theory of Computation by Michael Sipser -- we will be using the second edition. As in the text, the course will roughly be divided into three parts:

1. Automata and Languages

2. Computability Theory

3. Complexity Theory

In the first part, "Automata and Languages," you will be exposed to limited formal models of computation. This will allow you to gain experience reasoning within a mathematical model and proving properties about it. During this part, we will be learning about regular languages and context-free languages. How much can be expressed in each type of language?

The second part, "Computability Theory," explores the question of what limitations a computer has when solving problems. Are there problems that a computer provably cannot solve?

Finally, we will look at "Complexity Theory" and begin to reason about a formal notion of "how difficult" a problem is. Are some problems easier than others? Are some of the same "difficulty"?

The course activities are structured to help you engage with the material:

• Lectures will typically provide a different presentation of material than what is in the textbook, helping to spark your curiosity in the problems, algorithms and analysis.

• In-class engagement and questions will support your initial understanding.

• Homeworks provide an opportunity to practice skills modeled through the presented materials. 

• Reflections prompt you to be strategic in your learning.

• Exams are intended to inspire you to acquire a deep understanding of the material.

My goal is to create an inclusive learning environment that provides the structure and support to help you successfully understand models of computation and their limits. It is your responsibility to utilize the offered resources and undertake the work that optimizes your learning experience. By taking ownership, you will leave this course with tools that can assist in your academic and professional pathway. The grade breakdown is intended to strategically guide effective learning.

The instructor and students in CS 311 are expected to be respectful, inclusive of all students, and to not discriminate. Mount Holyoke resources on diversity, equity, and inclusion can be found here. Bias incidents can be reported here. Students are encouraged to bring concerns or feedback to the attention of the instructor.

• Engagement during class, including (completion, not correctness, of) questions via Ed Discussion.

• Ten weekly homeworks, typically due on Thursdays. 

• Weekly reflections (different from homework self-assessment & reflection).

• Two take-home midterm exams (2 hour time limit):

  • Exam I: out Tuesday 2/20, due Monday 2/26

  • Exam II: out Tuesday 4/2, due Monday 4/8

• A take-home final (3 hour time limit) in the final exam period. 

• Exams are open-notes and open-book. Review the logistics for accessing your book and notes.

Grading 

• Class engagement: 10%

• Weekly reflections: 5%

• Homeworks: 20%

• Midterm exams: 40%

• Final exam: 25%

Lateness policy

It's important to keep up with the content and pacing of the course. I recognize that sometimes unpredicted situations arise that may prevent you from submitting an homework. Therefore, your lowest homework grade will be dropped. In addition, you will have 2 additional days (48 hours) to submit without a consequence to your grade. After that, I will calculate your grade according to this chart:

• ≤ 2 days (48 hours): full credit of your earned grade, or

• ≤ 3 days (48 - 72 hours): 70% credit of your earned grade, or

• ≤ 4 days (72 - 96 hours):  30% credit of your earned grade, or

• > 4 days: 0% credit of your earned grade

Computer science is a subject that builds up on itself. To encourage you to continue to deepen your understanding of a topic, you will perform a written reflection on each homework. Solutions will be released on moodle along with the homework; you should not look at the solutions until you have completed the work. It is up to you to decide if you want to review each problem’s solution as you go or wait until you’ve completed the whole homework.

You may revise your work after reviewing the solutions and before submitting your final version. If you do so, you must articulate how you used the solutions to revise your original work as part of your reflection. Failure to do so is a violation of the Honor Code. You may use your revised work for your self-assessment mark.

When you submit the homework, you must include a self-assessment and reflection:

• Self-assessment. Use the solutions to assess and reflect upon your submission. For each problem, you must:

  • Give yourself an assessment mark. (These are based on Mark Talbert’s EMRN rubric; here is a link to a flow chart illustration of the rubric).

    • E - The work meets or exceeds the expectations of the homework. Communication is clear and complete. Deep understanding of the concepts is evident. There are no non-trivial errors. This work could be used as a classroom example.

    • M - Understanding of the concepts is evident through correct work and clear, audience-appropriate explanations. Some revision or expansion is needed, but no significant gaps or errors are present. No additional instruction on the concepts is needed.

    • R - Partial understanding of the concepts is evident, but there are significant gaps that remain. Needs further work, more review, and/or improved explanations.

    • N - Not enough information is present in the work to determine whether there is understanding of the concepts. The work is fragmentary of contains significant omissions. Or, there are too many issues to justify correcting each one.

    • ? - If you are really unsure as to what mark to assign.

• Reflection. 

  • Provide a short and specific reflection as to why you earned your self-assessment mark, such as:

    • “In problem 2, I was confused by the definition of ….”, or

    • “For the proof of problem 1, I incorrectly assumed that …”, etc.

  • Ask specific questions that still remain, such as:

    • “Is this also a counterexample?” or

    • <circle a part of a proof you’re unsure of> “I didn’t know how to phrase this – how can I be more technically accurate?”

  • [Optional] Provide one hint for the problem (to your past self or future student).

Each problem on the homework will be graded on a 3 point scale, analogous to the self-assessment rubric. The grade for the entire homework will be weighted with 75% calculated from the average of the problems and 25% from the quality of your self-assessment/reflection.

• E - (3 points) The work meets or exceeds the expectations of the homework. Communication is clear and complete. Mastery of the concepts is evident. There are no non-trivial errors. This work could be used as a classroom example.

• M - (2 points) Understanding of the concepts is evident through correct work and clear, audience-appropriate explanations. Some revision or expansion is needed, but no significant gaps or errors are present. No additional instruction on the concepts is needed.

• R - (1 points) Partial understanding of the concepts is evident, but there are significant gaps that remain. Needs further work, more review, and/or improved explanations.

• N/? - (0 points) Not enough information is present in the work to determine whether there is understanding of the concepts. The work is fragmentary of contains significant omissions. Or, there are too many issues to justify correcting each one. Or, no self-assessment was provided.

Collaboration

• Collaboration is encouraged while thinking through the homeworks. Problems will take time to understand and solve, and you will benefit from developing ideas and solutions in small groups. 

• You must write your own solutions, and no collaboration is allowed while writing the solutions. Writing solutions on your own will cement understanding of the problem and demonstrate mastery of the solution. Looking at solutions from other students or any other source (including the posted solutions or the web), or collaborating to write solutions, is considered a violation of the Honor Code. All suspected violations will be referred to the Honor Code Council. For more detail on what constitutes an academic violation of the Honor Code, please see the Student Accountability webpage.

Submission

• You must submit homeworks along with a self-assessment & reflection through Gradescope. Refer to the Tools page for details.

Feedback and grading

• Homeworks are a chance for you to engage with the material and the process of learning as well as receive feedback. To this end, you will be evaluated based on your self-assessment and reflection, and I will provide feedback in response to your specific questions. 

• The general workflow will involve:

  • submission of homework [75%]

  • self-assessment and reflection [25%]

Accommodations

Disability Services is the office on campus that determines academic accommodations for students with disabilities. If you need official accommodations through Disability Services, you have a right to have these met and kept confidential. Please contact Disability Services, located in Mary Lyon Hall 3rd Floor, at 413-538-2634 or disability-services@mtholyoke.edu. If you are eligible for academic accommodations, you will be provided with an accommodation letter. Once you receive your accommodation letter, I would like to meet with you and discuss these approved accommodations and our class. For more information on who might be eligible for accommodations and the application process please see the Disability Services website (https://www.mtholyoke.edu/disability-services).​​​​​

Title IX/Responsible Reporter:

If you or someone you know has been a victim of discrimination, harassment or violence based on sex or gender and you would like to talk to someone about our resources, please contact the Title IX Coordinator, Shannon Da Silva at ​titleixofficer@mtholyoke.edu​. 

As a faculty member, I am a responsible reporter for any information I learn that may be a violation of our Gender-based and Sexual Misconduct Policy. This means that I will need to share this information with our Title IX Coordinator, Shannon Da Silva. This could be anything related to sexual assault, dating violence, stalking or sex or gender-based harassment. If you are experiencing any of these things and you want to talk with someone who is not a responsible reporter, I can help direct you to private and confidential resources on campus (Counseling Service, Health Services, and Alcohol and Drug Awareness Project. These offices have a legal mandate for confidentiality. These offices are not required to turn over identifying information to the Title IX coordinator but may provide anonymous data to the Title IX coordinator for reporting requirements of the Clery Act). 

Academic Integrity & Honor Code

Mount Holyoke College is a community of students, faculty, staff, and administrators committed to free inquiry and the pursuit of knowledge in the tradition of the liberal arts. The decision to join this academic community requires acceptance of special rights and responsibilities that are essential for its effective functioning and the realization of its mission. All members of the community share the responsibility to uphold the highest standards of academic integrity. 

I expect all your work to abide by the MHC Honor Code: “I will honor myself, my fellow students, and Mount Holyoke College by acting responsibly, honestly, and respectfully in both my words and deeds.” Any work that does not will be reported to the Academic Honor Board. For more detail on what constitutes an academic violation of the Honor Code, please see the College ​Academic Rights and Responsibilities webpage. 

More specifically: 

The Computer Science Department follows the Mount Holyoke College Honor Code. Work submitted for grading must be entirely your own, unless you were instructed to work in groups. The purpose of course assignments is to practice skills, gain a deeper understanding of the course material, and apply that knowledge to new situations. Assignments are designed to challenge you, stimulate critical thinking, and help you understand the concepts related to the course. Your grade is a reflection of your understanding of the material. 

We recognize that collaboration can help you master course material. In fact, there are certain ways in which we will encourage you to collaborate. These include: 

• discussing course content at a high level

• getting hints

• talking about problem-solving strategies

• discussing ideas together

However, you must do all write-ups on your own. Writing solutions on your own will test and demonstrate your mastery of course material. 

Looking at solutions from other students or any other source (including the web), or collaborating to write solutions to individual work, is considered a violation of the honor code. All suspected violations will be referred to the academic honor board. If you are uncertain whether something is allowed, it is your responsibility to ask.

If you have engaged in any of the above acceptable collaboration activities for an assignment, you MUST acknowledge the classmates or TAs with whom you spoke – this should be done as a note when you submit your work.

Note that the Association for Computing Machinery has a strong Code of Ethics and Professional Conduct.  At this site you can read both the current Code from 1992 and the draft of the new 2018 version.

• Internet sources 

  • All material for the course is contained on this web site, the course moodle site and the text. 

  • You should not consult any other source.

Honor code dos and don'ts

These lists are intended to clarify what types of behaviors are and are not generally permissible. Follow these guidelines unless specifically directed otherwise. (clarify if uncertain)

Do:

• • Organize study groups.

  • Clarify ambiguities or vague points in class handouts, textbooks, assignments, and labs.

  • Discuss assignments at a high level to understand what is being asked for, and to discuss related concepts and the high-level approach.

  • Refine high-level ideas/concepts for projects (i.e. brainstorming).

  • Outline solutions to assignments with others using diagrams or proof sketches, but not complete machines/proofs.

  • Get or give help on how to operate the computer, terminal, or course software.

  • Submit the result of collaborative coding work if and only if group work is explicitly permitted (or required).

Don’t:

• • Look at another student’s solutions.

  • Use solutions to same or similar problems found online or elsewhere.

  • Search for homework solutions online.

  • Turn in any part of someone else's work as your own (with or without their knowledge).

  • Share your code or written solutions with another student.

  • Share your written solutions online.

  • Allow someone else to turn in your work as their own. (Be sure to disconnect your network drive when you logout and remove any printouts promptly from printers.)

  • Collaborate while writing programs or solutions to written problems. (But see above about specific ways to give or get debugging help.) 

  • Write homework assignments together unless it is specified as a group assignment.

  • Collaborate with anyone outside your group for a group assignment. 

  • Use resources during a quiz or exam beyond those explicitly allowed in the quiz/exam instructions. (If it is not listed, don’t use it. Ask if you are unsure.)

  • Submit the same or similar work in more than one course. (Always ask the instructor if it is OK to reuse any part of a different project in their course.).

Audio/Visual Recording Policy 

To encourage active engagement and academic inquiry in the classroom, as well as to safeguard the privacy of students and faculty, no form of audio or visual recording in the classroom is permitted without explicit permission from the professor/instructor or without a letter from AccessAbility Services, signed by the faculty member, authorizing the recording as an accommodation. Authorized recordings may only be used by a student who has obtained permission and may not be shared or distributed for any reason. Violation of this policy is an infraction of the Mount Holyoke Honor Code and academic regulations and will result in disciplinary action. 

Thanks to Randy Shull for so generously letting me use his notes from his version of this course!