CSCI 361 (Fall 2024)

CSCI 361 (Fall 2024) 

Course Overview and Resources: This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free languages, and Turing machines. These models provide a mathematical basis for the study of computability theory. The class also explores important topics in complexity theory: hardness of problems and reductions and characterizations of time and space complexity classes. Prerequisites: CSCI 256 or MATH 3xx and Permission of Instructor. 

• Course webpage: https://williams-cs.github.io/cs361-f24/index.html 

• GLOW page: https://glow.williams.edu/courses/3980860 

• Textbook: Introduction to the Theory of Computation by Michael Sipser (3rd ed) 

Grading Policy: The final grade will be calculated based on the following breakdown: 

• Attendance, Readings & Class Participation (10%) 

• Assignments (30%) 

• Survey Paper and Presentation (10%) 

• Midterm Exam (25%) 

• Final Exam (25%) 

Attendance, Readings and Class Participation: Attendance is required and essential to the course. Students are encouraged to contact me if they need to miss lecture due to any reason. Moreover, because we have an early-morning class, each student has two no-questions-asked absence allowance—we all snooze our alarms from time to time. 

Keeping up with the readings is an important part of coming to class prepared. Reading questions will be assigned for each lecture. Students must turn in their answers to the reading questions at the beginning of each class session. The reading questions will only be graded on completion and not correctness. 

Learning is a collaborative endeavor and most lectures will include in-class group activities and exercises to practice the concepts in the reading and lecture. Together, attendance, reading questions and class participation count towards 10% of your final grade.

Assignments: There will be weekly problem sets to test understanding of materials and prepare students for the exams. The assignments and due dates will be posted on the course website. 

• The solutions must be typeset in LATEXusing the template provided. 

• All assignments must be submitted through https://www.gradescope.com/ (course code: 844447). 

Late Policy: Students are expected to turn in all assignments by the due date to receive full credit. Please contact me as soon as possible if you cannot meet a deadline. Extensions may be provided in case of exceptional circumstances. 

Exams: The course has two exams: a midterm which will take place around week 6/7 and a final exam during the final exam period. The exact format of the exams will be discussed in class. 

Survey Paper and Presentation: Towards the end of the course, the students must write a short survey paper on an advanced topic of their own choosing. The students are also expected to present their findings through a brief presentation in class. Students may work in pairs. Example topics and further guidelines will be provided in class. 

Course Schedule: A tentative schedule of topics is provided below and is subject to change.

Academic Honesty: For a full description of the Computer Science Honor Code, please see: https: //csci.williams.edu/the-cs-honor-code-and-computer-usage-policy/. If you have any doubt about what is appropriate, please email me at [email protected]. Specific rules are outlined below. 

• You must not search the internet and external resources using problem-specific keywords. This includes the use of ChatGPT or other text-generating platforms. One of the learning goals of this course is to understand the limits of computational systems (including AI), and we will discuss this specifically in class and through explicit assignment questions. 

• Collaboration is encouraged for assignment questions unless stated otherwise explicitly. This means you are allowed to discuss high-level approaches and clarifications to assignment questions with your classmates (e.g., is this problem testing the use of pumping lemma from class? Is there an example from lecture that uses strategies that help solve this question? Can we do some examples together to understand what the question is asking? ). However, you must not discuss any low-level details of the solution/proofs (e.g. should the DFA have an arrow going to an accept state on this string?, does this proof approach seem correct? ). 

• You must always cite external resources used for background reading. 

• You should never turn in a solution that you do not understand. If an honor-code violation is suspected, you will be asked to explain your solution orally to determine if you came up with it on your own. 

Health and Accessibility Resources: Students with disabilities or disabling conditions who experience barriers in this course are encouraged to contact me to discuss options for access and full course participation. The Office of Accessible Education is also available to facilitate the removal of barriers and to ensure access and reasonable accommodations. Students with documented disabilities or disabling conditions of any kind who may need accommodations for this course or who have questions about appropriate resources are encouraged to contact the Office of Accessible Education at [email protected].” 

Inclusion and Classroom Culture: The Williams community embraces diversity of age, background, beliefs, ethnicity, gender, gender identity, gender expression, national origin, religious affiliation, sexual orientation, and other visible and non visible categories. I welcome all students in this course and expect that all students contribute to a respectful, welcoming and inclusive environment. If you have any concerns about classroom climate, please come to me to share your concern. 

A note on preferred names/pronouns: In this class, we use the name and gender pronouns that individuals ask us to use as a sign of mutual respect. Please ensure that your preferred pronouns are up to date on GLOW. That said, everyone makes mistakes—in general, should you use an incorrect pronoun or name, the best course of action is to make a quick correction and move on, rather than dwelling on it.