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
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.
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
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.
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
Assignments will be uploaded here. You must submit it via Canvas.
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.
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%.
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.
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, firstname.lastname@example.org, visit http://dss.mst.edu/ for information.