Avah Banerjee

CS 2200 Theory of Computer Science (Fall 2021)

Time: TR 2:00-3:15 PM
Location: Physics 00104
Instructor: Avah Banerjee
Office Hours: TR 12:00-1:00 PM (or by appointment)
Recitation Hours: TBA, GTA: Sai Divya Siriki, Email : ssmkd [at] mst [dot] edu
Grader Office Hours: TBA, David Martin, Email : dpm4n9 [at] mst [dot] edu
Email: banerjeeav [at] mst [dot] edu
Course website: https://www.avahbanerjee.com/cs2200.html

* Read the syllabus carefully and if you have questions about the syllabus send them in by the end of the first week of classes.
* This is not an easy course, only through perseverance, participation and careful time management you will be able to succeed. If you are falling behind do not hesitate to contact us before it is too late.
* This syllabus is not a comprehensive legal contract. It is expected that all students follow the guidelines set here in their intended spirit and refrain themselves of any subversive attempt to gain an unfair advantage over their peers. Such actions will be considered a violation of the honor code and I reserve the right to update the syllabus accordingly to ensure fairness and consistency.

Course description:
In this course we will study the founding principles behind modern day computation as well as look at how computation is inherently a natural process. The theory of computation is a mathematical theory whose roots can be traced back to several millennia. However, a rigorous mathematical treatment of computation was only developed about a century ago. Subsequent progress has showed us that study of computation is fundamental to understanding nature and to have a unified theory about our universe. It is also believed that it will play an important role in modelling the underlying dynamical processes and structures of our brains.

Course Outcomes:
1. Elementary understanding of the mathematical foundation of computation theory
2. Develop key intuitions about natural computational processes
3. Learn formal problem solving and some fundamental proof techniques

Prerequisites:
Comp Sci 2200 Prerequisite*: A "C" or better grade in both Comp Sci 1200 and Comp Sci 1575.
*Although a C in CS 1200 is the minimum requirement, I strongly urge you reconsider taking this course at this time if do not have a grade B or better in CS 1200. In such a situation you should ideally do a pre-enrollment prep during the summer or the winter break. Discuss with me and your academic advisor if you are unsure.

Textbook
We will not follow any specific text book. Time to time I will assign some reading materials. Otherwise, exams, homework, quizzes will be based on the class lectures.
Here are some recommended texts:
1. The Nature of Computation, Cristopher Moore, Stephan Mertens - a very comprehensive but fun introductory guide
2. Introduction to the theory of computation, Sipser - some consider this The textbook for an undergraduate theory course
3. Quantum computing since Democratis, Scott Aaronson - a humor filled take on theory, quantum computing, physics and philosophy

Topics (subject to change)
0. Prologue (Logic , Axiomatic set theory , Mathematical Proofs), 4 lectures
1. Languages (RL, CFL), 4 lectures
2. Computability theory (universality, decidability, recursion etc.), 5 lectures
3. Complexity theory (efficient computation, P vs NP, complexity classes), 5 lectures
4. Randomness and computation, 2 lectures
5. Learning theory, 2 lectures
6. Quantum Computation, 4 lectures
7. Epilogue (Free will, ER=EPR?, MIP*=RE, Cellular Automata etc.), 2 lectures

Homework
Assignments will be uploaded here. You must submit it via Canvas.

Grading Policy:
1. Quizzes (5% x 8 = 40%) : These will be in-class and multiple choice
2. Homework / group assignments (30%): There will be several homework and in class assignments will be given throughout the semester. Some of these will be individual and some will be group efforts.
3. Final Exam (40%)
4. (optional) Project (10%): Adventurous students may contact me and submit a project proposal either individually or as a group. The project should be based on the topics considered in the class and take a deeper look at one of them.

Attendance Policy:
1. Attendance is mandatory.
2. For each missed attendance a student must provide a valid justification in writing which has been endorsed by their academic advisor / university official. A doctor's note is also fine.
2. Otherwise you will be marked as absent for that lecture.
3. You are given a budget of 2 days in total where you can be absent without an excuse. Use them wisely.
4. Suppose your total grade is T out of 100. If there were X lectures given and you were absent in Y of them (beyond the 2 days that were allocated) then your reduced grade will be (1-Y/X)T.

Late Submission
1. Each student is given a budget of 5 late days for the entire duration of the class.
2. An assignment submitted 1.0 min to 24 hrs late counts towards 1 late day, if it is late by more than 24 hours it will be counted as 2 days late.
3. An assignment cannot be more than 48 hours late.
3. If you run out of late days then you will not be able to submit an assignment late.
4. For group assignments, student with the least amount of late day budget will be used to determine compliance. Example, suppose A and B submits an assignment together. Suppose A has 2 and B has 1 late day budget. Then they must submit their joint assignment no more than a day late.

Class Participation and Improvement
I strongly encourage you to participate in class discussions and group activities. If you can set yourself apart from your peers through your class engagement, improving your grades over time etc. then I may bump your grade by as much as 10%.

Regrade request
1. Instructors make mistakes and you may wish to resubmit your graded paper. However make sure you have valid reasons to ask for a regrade. Whenever you submit a re-grade request you must also write clearly your rational for the request.
2. These rationals must be reasonable. For example, you cannot simply request for a regrade by saying something like "X got Y in problem P" but I got Y' in problem P, unless Y is also willing to have their assignment regarded.
3. Once a regrade request is accepted your entire assignment will be reviewed for correctness of the previous grading attempt and you may end up loosing points overall.

Academic Integrity
Please review S&T's Honor Code at https://stuco.mst.edu/. Policy regarding student conduct, plagiarism etc. can be found at https://registrar.mst.edu/academicregs/

Diversity, Inclusion and Belonging
My goal is to create a learning environment that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, and ability). If something was said in class (by me or anyone else) that made you feel uncomfortable, please talk to me about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please do not hesitate to come and talk with me. As a participant in offline and online course discussions, you should also strive to honor the diverse perspectives of your classmates and teaching staff. (Credit: based on the statement of Dr. Monica Linden at Brown University.)

COVID-19 Policy/ Contingencies
1. Refer to https://coronavirus.mst.edu/ for up to date information and guidlines regarding COVID-19.
2. In the event that we move to online synchronous, instead of group assignments we will only have individual homework.
3. Everything else will remain the same. 4. Recitation and office hours will also move online.

Accessibility and Accommodations
It is the university's goal that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on a disability, please contact Student Disability Services at (573) 341-6655, sdsmst@mst.edu, visit http://dss.mst.edu/ for information.