Homeworks
General instructions
At the top of your solutions, be sure to write down the names of anyone you discussed this assignment with or any resources you used!
Please copy the description of the problem as well as your solution.
Submit via Gradescope.
You may find it useful that all problems from the Sipser's Theory of Computation (2nd edition) can be found here.
When you submit the homework, you must also 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%]