Time: TuTh 9:30AM - 10:45AM
Location: Computer Science 00120
Instructor: Avah Banerjee
Office Hours: TuTh 11:00AM -12:00 PM (or by appointment)
Recitation Hours: TBA, GTA: Asim Sharma, Email : asn32 [at] mst [dot] edu
UTA Office Hours: TBA
Email: banerjeeav [at] mst [dot] edu
Course website: https://www.avahbanerjee.com/cs2200-f24.html
Course description:
Theoretical computer science is not rocket science. Arguably, it's harder! That being said, we are here to see the tip of that TCS iceberg from a distance. If you are that student who has so far been introduced to computer science through the lens of programming, this course will feel out of place—and possibly as an anachronism. Hopefully, it will help you appreciate a bit more of the science part of computer science and how it is rooted in other natural sciences.
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 several millennia.
However, a rigorous mathematical treatment of computation was only developed about a century ago. Subsequent progress has shown us that the study of computation is fundamental to understanding nature and to having a unified theory about our universe. It is also believed that it will play an important role in modeling the underlying dynamical processes and structures of our brains.
Course Outcomes:
1. Elementary understanding of the mathematical foundations of computation theory
2. Develop key intuitions about natural computational processes
3. Power and limitations of computational models and resource usage
4. Classification of computational problems using complexity theory
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 textbook. From time to time, I will assign some reading materials (usually before the lecture).
Here are some recommended texts:
1. The Nature of Computation, Christopher 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 Democritus, Scott Aaronson - a humor-filled take on theory, quantum computing, physics, and philosophy
Topics
0. Foundations (Getting to know each other, Logic, Axiomatic Set Theory, Mathematical Proofs, Puzzles), 2 weeks
1. Universal Computation (Languages, Turing Machines, Church-Turing Thesis CTT), Computational Resources), 2 weeks
2. Computability Theory (Decidability, Undecidability, Recursion Theorem), 2 weeks
3. Complexity Theory (Efficient Computation, P vs. NP, Complexity Classes), 3 weeks
4. Randomness and psudorandomness 2 week
5. Quantum Computation (Superposition, Entanglement, Magic, Qunatum-Extended-CTT), 2 weeks
Take Home Assignments
Assignments will be uploaded here. You must submit them via Canvas.
Assignment 1 [PDF]
Assignment 2 [PDF]
Grading Policy:
1. (Individual) Assignments (25% x 3 = 75%): There will be a total of 4 take-home assignments, out of which the one with the lowest score will be dropped. To ensure the work you submit is the product of your own intellectual efforts, a certain percentage of students will be randomly sampled after the submission of each assignment. They will be interviewed by the GTA and possibly by me to confirm that they have a complete understanding of their own work.
2. (Individual) Self-evaluation (10%): Near the end of the semester, each student will fill out a self-evaluation form in which they will need to input details about their efforts in this course as well as judge their class performance. It is expected that you fill out the form as an impartial observer of your own work, to the best of your ability. Your self-appraisal should be in line with your general class performance. If your self-appraisal has little to no correlation with your class performance, then a lower score will be given. This is to account for efforts by students that sometimes do not reflect in their grades as well as to accommodate non-traditional learning outcomes that cannot be captured by traditional grading.
3. (Entire Class) Class participation and engagement (15%): Throughout the semester, there will be numerous events where I will ask students to volunteer or directly assign them tasks that aim to enrich our classroom discussions and understanding of different concepts. A mathematical model will be used to determine an aggregate score (Class Engagement Score (CES)) for the entire class at the end of each week so that you are aware of what progress needs to be made. I will not disclose the exact mathematical model; however, it will consider, among other factors, the diversity of student participation (e.g., if only a select group of students are active, then the score will be lower), average class attendance, attendance rates of students whose attendance is in the lowest quantile, and the rate of success for activity outcomes, among others.
Late Submission
1. Each student is given a budget of 4 late days for the entire duration of the course.
2. An assignment submitted between 1 minute and 24 hours late will count as 1 late day. If it is more than 24 hours late, it will be counted as 2 days late.
3. An assignment cannot be more than 48 hours late.
4. If you run out of late days, you will not be able to submit any assignments late.
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 regrade request, you must also clearly write your rationale for the request.
2. These rationales must be reasonable. For example, you cannot simply request a regrade by saying something like, "X got Y on problem P, but I got Y' on problem P," unless Y is also willing to have their assignment regraded.
3. Once a regrade request is accepted, your entire assignment will be reviewed for the correctness of the previous grading attempt, and you may end up losing 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/
Honor code violations, including the misuse of AI tools, are grave concerns in this course. If you are uncertain about whether your planned actions, such as utilizing AI for solving assignments, missing citations, or referencing online solutions might breach the honor code, please consult with me prior to submitting your work. Be aware, if it is determined that any portion of your assignment has been plagiarized or completed with prohibited AI assistance, you will receive a grade of zero for that specific submission.
Use of AI
In accordance with the principles of academic integrity and trust in the educational community, students are expected to uphold the highest standards of honesty in their academic endeavors. The following guidelines specifically address the use of artificial intelligence (AI) in the context of this course:
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.