Syllabus
Purpose and Objectives
Why do some tasks seem more difficult to compute than others? In CS 3800 you will learn to understand formal treatments of the notions of computation, computability, computational power, and efficiency that will give you the tools to answer this question. You will learn to understand both intuitively and formally simple models of computation. You will gain expertise with mathematical proofs and common proof techniques, and you will also come to understand the connections between these theoretical models and computational tasks in common programming languages.
After this course you will know how to think about:
- What’s going to be an easy task, and what’s going to be a complicated job?
- How can we compose programs together?
- As computers get more powerful, how much easier do various tasks (e.g. chess, password cracking) get?
We call this course “theory”, but the subject is imminently practical, and about the practice of computing. The early field of computer science carved these areas of computationally inspired mathematics out from the broader field as their own subject.
Research in this field concerns how to recognize and classify difficult tasks, and what options we have when we are faced with a computationally difficult task. For instance, we could:
- Perhaps, slightly change the problem statement to an easier problem.
- Perhaps, satisfy ourselves with some “good enough” sub-optimal solution that’s easier to solve.
- Think broadly and be less pessimistic: if the problem is only really difficult in some worst-case scenarios but usually not so bad, we might just go with the solution we have.
Contact
I strongly recommend that for general questions that might benefit others, we communicate via Piazza. A great regular way to reach out for help is via our office hours.
The best way to get in contact for personal, private (FERPA, etc) messages is via my email address jhemann@northeastern.edu. You should expect a response within 48 hours. You will find that I am faster with Piazza. In fact, if I deem it even potentially useful to others, I will (1) anonymize your letter, (2) post the question and answer on Piazza, and (3) forward you the link. If you’re interested in PL research, logic, logic program, automated theorem proving or the like, please let me know on that too! I’m excited to talk more about it all :-)
Required Texts
We will use the 3rd Edition of Sipser’s Introduction to the Theory of Computation text for this class. There are courses where you do not need the putatively required textbook. In this course, the text is really, actually necessary both to complete the required readings and also portions of the homework assignments. This textbook is widely available, including at the Northeastern University bookstore. As you read, please also take care to pay attention for the author’s known errata. You can find an edition of this text available as an E-book from the Snell library.
Grade Breakdown
I will assign overall course grades as follows:
| Category | Weight (%) |
|---------------------------+------------|
| Lecture Quizzes | 20 |
| Exams | 35 |
| Homework | 45 |
| TRACE | 1 |
| Total | 101 |
I will calculate overall numeric grade according to the Northeastern grading schema. Additionally, there will be a “curve”, but I will determine it only at the end of the semester. This curve will potentially raise grades above those described here, but will not lower them. Therefore, the total grade shown on Canvas does not necessarily reflects the worst-case scenario of the letter grade you will get at the end of the semester. This means I cannot give you a more precise estimate of your grade than what you calculate from the raw score. I detail below the aforementioned individual components of your final grade.
I will base some portions of your homework and lecture quiz grades on completion and submission of the relevant exercises. I will base the remaining portion of each on correctness.
Total Running Grade Calculation
We will track your calculated grades on Canvas. You will have an approximate assessment of your current grade status before the Add/Drop deadline.
Collaborative Course Construction and Feedback
I want you all’s feedback and input. I am open to suggestions and changes; I consider this preliminary until the end of the first week of class. You can see any and all changes on the course website’s repository. I cannot promise that we will act on all suggestions, and even those we find compelling may not be implementable as we go.
Participation
I expect you to attend each lecture. We will not take attendance as such, but attendance is a prerequisite for participation, a substantial portion of your grade for this course. I expect students to attend every class and remain in class throughout the duration of the session. Your absence or tardiness will impact your ability to achieve course objectives which could hurt your course grade. An absence, excused or unexcused, does not relieve a student of any course requirement. Lecture content quizzes serve as proxies for participation and thus attendance, as well as to gauge students’ understanding. To account for illnesses, other commitments that come up, and all the other vagaries of life, I’ll drop 5/25 of these quizzes for you all. I don’t know that I’d be comfortable dropping 1/5 of them under normal circumstances, but at least in the current situation that seems like a reasonable precaution. If you think you’re sick, please do get yourself checked and be safe.
Oral Explanation and Participation
Proof has a social component. As such, part of your grade will also include your participating by communicating with your colleagues in lecture. These can take the form of small group “breakout room” work, open class votes and discussions, or walk us all through some of your answers.
Lecture Quizzes/Polls
Expect to have regular content quizzes during or toward the end of lecture. These act as a forcing function, encouraging attention to lectures and/or the ancillary readings and to alert me to students’ difficulties. Sometimes we take these for completion, others for accuracy. These lecture quizzes belongs under your participation grade.
Homework
Homework, consisting of problem sets assigned roughly once per week, is an essential part of the course. We give a few (randomly varying) extra minutes to account for network time disagreements, but beyond this homework assignments are due strictly on the day and time listed on the assignment. These will usually be on Tuesday at 10pm. Some other assignments will require hand-written proofs; we fall back to these when programming assignments add more difficult than the learning they would bestow.
To universally, uniformly and preemptively account for any number of situations that arise, I will drop every student’s lowest homework assignment grade. This absolution for one assignment is our late/etc homework clemency. I shan’t accept late submissions except under the most exceptional of circumstances (family emergencies, hospitalizations, the like)—if that comes up please see me. We are, however happy to go over these missed submissions with you at office hours.
You should make every effort to complete and submit each assignment. If you are struggling with an assignment, it best to turn in what you can complete and to seek help. Homework assignments will build on one another conceptually, and some later assignments require the successful completion of problems from earlier ones. Do not fall behind. If you feel yourself falling behind, seek help immediately and take advantage of office hours, your classmates, ancillary readings, and additional support. Follow both the general homework guidelines, as well as any special instructions given on the assignment itself.
We allow an unlimited number of submissions per assignment, up to the deadline.
We will evaluate your work both for correctness using an automated test suite when possible and also by manual hand inspection. We provide you an autograder test suite for each assignment. This autograder merely ensures that your programs compute the correct answers.
Exams
You will have two long-form exams. I have yet to determine our exams’ format. Students’ suggestions led to several improvements in how I conduct this course, and your continued suggestions will help lead to continued improvements. These exams are at the dates laid out on the calendar and as discussed in class; we will not have a final exam.
We added an additional, optional final. We will score the exam portion of your grade as the best two out of three.
TRACE evaluations
I encourage students to take time and submit TRACE evaluations. Your time is busy at the end of the term when these are available. In order to fairly compensate you for that time without violating the integrity or anonymity of the TRACE system, if 85% or more of the enrolled students complete these TRACE evaluations, then I shall add a point onto the class-wide final average.
Recording
I do not permit electronic video and/or audio recording of class. Unless the student obtains permission from the instructor electronic video and/or audio recording of class is prohibited. If permission is granted, any distribution of the recording is prohibited. Students with specific electronic recording accommodations authorized by the DRC do not require instructor permission; however, the instructor must be notified of any such accommodation prior to recording. Any distribution of such recordings is prohibited. Obviously I cannot stop you, but it’s to both our benefits.
Additional Support
In addition to lecture, we provide the following additional resources for students to avail themselves. Do consider taking regular advantage of them.
Scheduled Office Hours
Course personnel will make ourselves available for 4-6 hours of office hours available weekly, concentrated toward assignment due dates. If our office hours schedule in particularly ill-suited to your class schedule, let me know and we may be able to adjust them. As per current university guidance, we will hold these office hours remotely.
Gradescope
We will be using Gradescope this term, which allows us to provide fast and accurate feedback on your work. Homework will be submitted through Gradescope, and homework and exam grades will be returned through Gradescope. As soon as grades are posted, you will be notified immediately so that you can log in and see your feedback. For clarification on grades, please meet with your grader during office hours.
To access Gradescope, click the Log In button on the Gradescope website and enter your university email. Then enter your existing password if you have one or click Forgot Password to reset it or create one for the first time.
Piazza Forums
Outside of office hours, you should utilize the class’s Piazza forums for questions. We have disabled private messages to instructors, but you can choose to remain anonymous to the class when asking questions. We prefer Piazza over email, as it gives other students the opportunity to learn from those same anwers. Please restrict your questions to those that do not ``give away the punchline’’ to a homework question. For more sensitive questions, or administrative issues that should addressed in private, please email me at the address listed on the front of this syllabus.
Ancillary Videos and Optional Texts
The theory of computation is central to the practice of computer science. Computer scientists have understood this for decades. As such, instructors have covered these materials in a wide variety of styles and media which redounds to all our benefit. Whenever I have them, I will link to some best-in-breed videos that explain the topics from class in a complementary manner, and may also provide sections from other texts. Neither will cover topics precisely the way we do in lecture. Their presentations will differ in technical details and particulars of syntax. However, both provide material that translates to what we do in class. Some students may choose to use these videos or readings after lectures to supplement their understanding. Especially diligent students may use them to preview the lecture and be that much farther ahead. In the rare circumstance you must miss lecture, these may help supplement your understanding from lab, our additional support, and perhaps lecture notes from a friend.
Academic Integrity Policy
Students of course play an integral part in ensuring they receive the full benefit of their coursework. The students of 3800 are certainly beholden to the academic integrity policies of Northeastern University and as laid out in the student handbook, the Khoury College.
Teamwork and Collaboration
You can work with up to 2 others, for a total of 3 people in a group. You aren’t required to work with anyone else if you don’t wish. You can work with students from any other sections you wish. You will submit a single submission for your entire group, and it is your responsibility to include the names of your group members.
Do bear in mind pair programming is a central part of the undergraduate curriculum here. Pair programming is not intended to divide-and-conquer, but instead for students to collaboratively solve problems together. You are only twice as fast working separately if the typing is by and away the hardest part of programming. Which it is not.
Whatever size group you work in or how you meet you should still plan to all work synchronously and simultaneously together. Note a larger group is not necessarily better. You should at least try to do some of this wholly on your own. It’s good to have a baseline early on to know if you have this material under your belt or if you are getting lost. Ultimately, you should be responsible for and have a firm understanding of all work submitted under your name. You should be able to demonstrate this mastery when we request.
Group Dynamics and Difficulties
These groups are not fixed; you should feel free to adjust them to your own need and benefit on a per-week basis. If you find that your group is no longer able to work effectively together or that not everyone can equally participate, please bring this to your grader’s attention. Your grader and/or instructor may have suggestions about how to improve your group cohesion, or may use the staff privilege to reallocate group members.
Academic Accommodations
If you have accommodations from the Disability Resource Center (DRC) please submit your Professor Notification Letter to me by email, preferably within the first two weeks of the quarter, so I can do my part to help you achieve equal access in this course. I am eager to discuss ways we can ensure your full participation.
I encourage all students who may benefit from learning more about DRC services to contact the DRC.
Equity and Compliance
One of our responsibilities in supporting student learning 360° is to help create a safe learning environment both in person and virtually. You should carefully consult the university’s relevant policies, and if you have or experience any violations of the above I encourage you to take full advantage of the university resources.
It is also important that you know that federal regulations and University policy require me to promptly convey any information about certain kinds of misconduct known to me to our Deputy Title IX Coordinator or IU’s Title IX Coordinator. In that event, they will work with a small number of others on campus to ensure that appropriate measures are taken and resources are made available to the student who may have been harmed. Protecting a student’s privacy is of utmost concern, and all involved will only share information with those that need to know to ensure the University can respond and assist.
Acknowledgments
I have taken much of the design and execution of this course from Stephen Chang’s version of a similar class at UMass Boston. Some slides and material therein is borrowed from, in no particular order: Debasis Mitra (FIT), Costas Busch (RPI), Stephen Chang (UMB), and John MacCormick. Lindsey Kuper inspires some of this site and syllabus as well as being all-around inspirational.
