Theory of Computation

COSC 39, Winter 2021

Main | Schedule | Homeworks | About


Homeworks

Personally I firmly believe that the real learning doesn't happen in lectures, but only when we are wrestling with a concept through a set of problems, designed specifically at the right difficulty so that it is challenging, sometimes frustrating, but rewarding and expands our knowledge and skills after solving them (maybe with some help from your colleagues). Therefore it is okay if you find the problems hard; that is by design.

We will have problem set coming out every week. Some problems are marked with a star; these are more challenging (and fun) problems, and are therefore optional and do not count towards the final grades. However, working on these problems will help you master the materials and skills taught in this class. I strongly encourage you to try some of them if you are thinking about having a future career that assumes sharp thinking skills and math maturity.

Homework 0
Problem set, due by 1/15
Solutions
Homework 1
Problem set, due by 1/22
Solutions
Homework 2
Problem set, due by 1/29
Solutions
Homework 3
Problem set, due by 2/6
Solutions
Homework 4
Problem set, due by 2/15
Solutions
Homework 5
Problem set, due by 2/19
Solutions
Homework 6
Problem set, due by 2/26
Solutions
Homework 7
Problem set, due by 3/8

Collaboration rules

For Homework 0, you are required to work through the problems as much as possible by yourself and submit the answers individually. It serves as an assessment to whether you have the required knowledge and skills to learn effectively in this class.

Starting from Homework 1, you are allowed to work in groups each up to two people. Each group will submit a solution together by one of the group members; the submitted work should be clearly marked with the names of all the group members.

You are encouraged to use all the resources online/offline toward solving the homework problems. You are also encouraged to work with other groups (and also people outside the course) and discuss your progress, as long as in the end each group individually writes down and submit their own version of solutions in their own words, and properly cites everyone and everything you have consulted. In particular, if you find a solution manual online that contains an answer to the problem, cite the solution manual. If chatting with your friends at gaming night gives you an idea to solve the problem, cite your friends. If your cat walks across your keyboard and sends you to a Wikipedia page you never seen that contains a crucial construction to the proof, cite your cat. However, you don't have to cite the lectures and any course related materials listed on the schedule webpage.

Please refer to the Academic Honor Principle if you have doubts.

Submission and lateness policy

Homeworks will be announced in class and posted on this page. All homeworks should be submitted through Canvas. There is no strict format requirements about your solutions; the only important thing is to present and communicate your ideas in a clear and succinct fashion. Also make sure the lighting works out if you take a picture of your handwritten solutions. (I recommend you to convert the photos to black and white first.)

No late submissions will be allowed. On the other hand, not all problems will be counted towards your final grades. We will drop the lowest one-fourth (rounding up) of all the homework problems. For example, if a total of 24 problems are giving throughout the term, only 18 of them will be counted towards the final grades. You are still strongly encouraged to work on all the problems; this lenient policy is in place to prevent any unforeseen situations coming up. If you believe you need any special accommodations beyond this, please come and talk to me. The online learning experience can be hard for many of us, so please don't hesitate to reach out to me anytime.

Grading

Unless specified otherwise, all the problems with be graded based on a scale from 0 to 5:

But more importantly, we will provide written feedback and comments to your answers. Read them carefully and bring your questions (if any) to the office hours.

You may submit regrade requests if you think we misunderstood your solutions. We will regrade them based on the following rules.


last modified on