Theory of Computation
COSC 39, Winter 2021
- Instructor
- Hsien-Chih Chang
(hsien-chih.chang@dartmouth.edu)
- Teaching Assistant
- Themistoklis Haris
(themistoklis.haris.21@dartmouth.edu)
- Lectures
- Zoom
Mon Wed 1:10p–2:15p (Eastern Time)
- Working Sessions
- Zoom
Tue 1:40p–2:30p Fri 1:10p–2:15p (Eastern Time)
- Office Hours
- Zoom
Mon Tue 4p–5p (Hsien)
Thu 2p–3p (Themis)
- Discussion
- Slack
- Links
- Canvas | Syllabus | Notes for COVID-19
Announcements
- Mar 11
-
-
We have finished grading the Final exam. The raw average score is 48.25 ± 18.45 points.
-
Final exam solutions is out. Please take a close look to the rubrics and the comments to your solution on Canvas. If you have any regrade request, please submit them by the end of this weekend (3/21).
-
All final grades will be posted next Monday (3/22). Please come and talk to me if you have any concerns.
- Mar 11
-
-
Final exam is out, due on Mar 16 (next Tuesday) at 11:59pm. Please see the Canvas page for full instructions.
-
Thank you all for learning ToC with me this term, it has been fun! Please come and talk to me if you want to explore more about this magical and wonderful mathematical landscape.
- Mar 7
-
- Mar 4
-
-
We have finished grading Midterm 2. The raw average score is 31.06 ± 9.68 points. Removing the outliers, the average score becomes 31.33 ± 6.62 points.
-
The official solutions will be out soon.
- Mar 2
-
-
Midterm 2 is out, due today at 11:59pm. Please see the Canvas page for full instructions.
- Mar 1
-
-
Homework 7 is out, due by 3/8 (next Monday).
-
Midterm 2 will be held on 3/2 (Tuesday). It will be a closed-book, take-home exam, with 24 hours to finish it. The format is basically identical to midterm 1.
-
Solutions to Homework 6 is out.
- Feb 26
-
-
The solutions to Homework 5 is updated. Now everyone gets full credit on the last question, because my initial solution was incorrect.
-
Themis is kindly offering a review session for the midterm on Saturday (2/27) at 3pm, through the regular office hour link (thank you Themis).
Please come and join if you can!
- Feb 25
-
- Feb 21
-
- Feb 16
-
- Feb 10
-
-
Midterm 1 solutions is out.
-
We have finished grading Midterm 1. The raw average score is 33.67 points, with standard deviation 9.78 points. Removing those who aced the exam, the average score becomes 27.92 ± 5.81 points.
-
Please take a look at your graded exam and the official solutions, and let me know if you have any question! Any regrade request must be submitted in a written format, with a clear explanation of why you think the problem not graded correctly based on the rubric stated. I will regrade the problem from scratch, which means the new score can go both ways.
- Feb 9
-
-
Midterm 1 is out, due today at 11:59pm. Please see the Canvas page for full instructions.
-
The deadline for Homework 4 is postponed to 2/15 (Monday). Homework 5 will still come out some time this weekend.
- Feb 7
-
-
Homework 4 is out, due by 2/12 (next Friday).
-
Solutions to Homework 3 is out.
-
Midterm 1 will be held on 2/9 (next Tuesday). It will be a closed-book, take-home exam; you have 24 hours to finish it. After that, please schedule a 15-minute oral exam with me.
- Jan 31
-
- Jan 23
-
- Jan 19
-
I added another office hour on Monday 4p–5p (and also changed the Tuesday one to 4p–5p as well). Themis is still having office hour on Thu 1p–2p. Let me know if none of the time slots work for you!
- Jan 18
-
I recorded a video on tips for doing inductions on strings and automata over Zoom. Unfortunately the internet connetion was bad enough that the recording is barely watchable.
So we will work on some induction problems together in the working session tomorrow.
On Wednesday we will resume our discussion on how to emulate any regular expression using finite automata.
- Jan 16
-
Solutions to Homework 0 is out.
- Jan 15
-
-
Homework 1 is out, due by 1/22 (next Friday).
-
Starting from Homework 1 you are allowed to work in a group up to two people. You are also allowed to work alone if you prefer. Please coordinate and submit only one solution per group to Canvas by a group member; make sure to mark the names of both members clearly on your submission. There is no requirement to work with the same person (or even working in groups) throughout the course; you are free to switch (or going solo) at any time.
- Feel free to use the group signup page on Canvas to find a group member! Alternatively, you can just email/slack-message each other.
-
You might find some of the problems to be hard. Don't worry; this is normal. I strongly encourage you to utilize the office hours and share your partial attempts with the rest of the class. Learning math is a surprisingly social event; you will soon find out that bouncing ideas off each other and trying to explain your own half-baked ideas help tremendously in learning hard materials.
-
Solutions to Homework 0 will be uploaded after the deadline. Grading rubrics, sample solutions, and some general comments on the problem will all be there; make sure to take a look! If you find an error in the solution sheet, please let me know immediately; depending on the severity, we might decide to forgive the problem (after all, it is not fair to grade you on a problem that I cannot solve).
-
Remember to upload your worksheet for today to Canvas.
-
We don't have a live lecture next Monday (1/18, MLK day). I will upload a lecture video for you to watch in your off time. (Probably during the normal lecture hour so to keep myself on pace.) The class will resume on Tuesday (1/19), which will be another working session.
- Jan 12
-
Remember to submit your worksheet for today's (and all the future) working/headbanging session to Canvas! Don't worry about writing the solution neatly or even finishing all the practice problems; we just want to make sure that you are following along.
- Jan 9
-
-
Today's introductory lecture is uploaded; you can find it (and all future videos) on the Schedule webpage. I recommend you to watch in 1.25x or 1.5x speed as I tend to speak too slowly in live lectures.
-
I apologize for the passcode issue today; all future lectures will be using this new Zoom link; the passcode will be sent through Canvas annoucement.
-
One of the students caught a phrasing problem in Homework 0 Problem 2: Instead of exactly one edge between any pair of vertices, it should be at most one edge between any pair of vertices (in other words, no parallel edges). The problem has been updated with the change.
- Jan 5
- Homework 0 is out, due by 1/15 (next Friday). Please submit all your solutions to the homework problems through Canvas.
-
Homework 0 is designed to make sure that you have the necessary background knowledge and skill for the course. If you find the problems to be way too challenging beyond the realm of fun, come talk to me and we can figure out together if this is the right class for you at the moment.
-
Make sure to read all the policies regarding collaborations, submissions, and grading on the homework page.
-
Most importantly, have fun! There is no reason to take an optional upper-level course about philosophy of computations if you are not having fun.
- Dec 30
- Hello, welcome to COSC 39! This is the webpage for the upcoming course on theory of computation. I'm still preparing for the course; please bear with me! If you see any broken links please do let me know. A few announcements:
- If you still want to enroll but cannot add yourself on Banner, please send a mail to me.
- There will be a Homework 0 coming up on the first day of the class. The goal is to give everyone a sense of what background knowledge is expected from everyone for the course. Stay tuned!