Logistics:
| Credits: | 4 |
| Classes: | Mondays and Wednesdays, 10:10 AM - 11:40 AM (add to your calendar) |
| Classroom: | AC-04-LR-009 |
| Teaching Fellow: | Arnab Ray (arnab.ray_tf@ashoka.edu.in) |
| Teaching Assistant: | Smayan Agarwal (smayan.agarwal_ug25@ashoka.edu.in) |
Links:
| Course Outline and Lectures |
| Selection of Practice Problems |
| Resources and Reading Materials |
Course Description:
Most computer science courses teach how to compute: how to
write programs, implement algorithms, and build systems. This
course asks a deeper question: what is computation?
Different disciplines offer different answers. Logicians
understand computation as symbol manipulation (Gödel, 1931; Post, 1943);
mathematicians as the effective evaluation of functions
(Church, 1936); linguists as the generation and recognition
of grammatical structure (Chomsky, 1956); and engineers as the
control of physical processes (von Neumann, 1945; Shannon 1948).
In CS-3330, we will answer this question as computer
scientists: computation is the execution of an abstract machine
acting on an input according to unambiguous rules (Turing, 1936).
With this perspective, we will unify the symbolic, functional,
linguistic, and physical views of computation, and address
three fundamental questions: What can be computed? What can be
computed with resource constraints? And what cannot be computed
at all?
This course is divided into four modules:
- Finite State Systems: In the first module, we study computation with bounded memory and develop the theory of finite automata and regular languages. We compare different models of computation: deterministic, nondeterministic, and stochastic, as well as finite controllers with bounded data structures. We also introduce the connection between logic, automata, and grammar (and, time permitting, algebra and games), highlighting how simple computational models give rise to rich mathematical characterizations.
- Infinite State Systems: We move beyond finite machines to models with unbounded memory, expressed through stacks, tapes, and other extensible data structures. We examine their grammatical counterparts, such as context-free grammars, and show how these systems capture deeper forms of computational structure. This module clarifies why seemingly different models of general-purpose computation are equivalent in power and presents the Church-Turing Thesis as the unifying principle behind them.
- Decidability and Undecidability: In this module, we study the boundary between solvable and unsolvable problems. Using diagonalization, reductions, and fixed-point arguments, we identify problems that no algorithm can solve. Examples include the Entscheidungsproblem, problems about Turing machines, first-order logic validity, grammar problems, and tiling problems.
- Computational Complexity: When problems can be solved, we examine their time and space complexity, polynomial-time computation, and the notion of intractability. We also discuss the open problem P vs. NP and provide a framework for understanding why some solvable problems remain practically out of reach, and how resource constraints shape the landscape of computation.
Prerequisites: The course will require a certain level of maturity, at least at the level of CS-2212 (Data Structures and Algorithms). It is recommended that students also have familiarity with algorithmic concepts, including reductions, at the level of CS-3210 (Design and Analysis of Algorithms).
Grading: The grading rubric for this course is as follows:
- Assessments (64%): Four in-class assessments will be held during scheduled class sessions, typically at the end of each module. Each assessment contributes 16% to the final grade, for a total of 64%. There are no make-up or repeat assessments.
- Final Exam (30%): The final exam, scheduled by the Office of Examination, accounts for 30% of the final grade. It is intended to provide an opportunity to synthesize and apply all the concepts learned throughout the course.
- Daily Exercises (6%): Students are encouraged to complete daily exercises that accompany lectures and readings. These exercises are designed to reinforce key concepts, develop problem-solving abilities, and give hands-on practice with the material. Completion and effort on these exercises account for 6% of the final grade.
- Extra Credit: If a student loses points on the assessments, they will have the opportunity to revise and resubmit their papers to correct mistakes based on feedback. Successfully addressing the identified issues can earn up to a fourth of the lost points. This is intended as a opportunity to learn from mistakes and refine understanding.
Audit Requirements: 40% of the final grade.
Policies: Please note the following policies:
- Regular attendance is expected but not mandatory. Students arriving more than 5 minutes late may not enter, to minimize disruption. Eating in class is not allowed, and the use of laptops or cellphones is prohibited unless specifically required for course activities. Students are encouraged to take notes on paper by hand (unless granted an exception by OLS or OAA).
- As outlined in Ashoka's Academic Integrity Policy (see MyAshoka → Information and Documents → Office of Academic Affairs), plagiarism and other violations (including but not limited to unauthorized use of large language models or other generative AI tools) are serious offenses. Any violation will result in a failing grade (F) for the course. Please review the policy carefully.
Support: Students are encouraged to reach out to University offices such as the Office of Learning Support, Ashoka Center for Well-Being, and Center for Writing and Communication for additional support.