Introduction to Theoretical Computer Science: Course Policies and Foundations

Course Assignment: CS 2490, Introduction to Theoretical Computer Science (referenced as Introduction to Therapeutic Science), sections 101, 102, and 103.
Instructor: Pierre Gan.
System Transition: The university is transitioning from AsULearn to Canvas.
- Materials, including slides and the syllabus, will be posted on Canvas as the semester progresses.
- Attendance tracking via QR codes, previously handled through old systems, is being replaced or integrated into Canvas; alternative methods like sign-in sheets or custom QR codes may be utilized.
Section Breakdown and Recitations:
- Section 101: Recitation on Monday at 1:00 PM in Room 327 (Computer Science Department).
- Section 102: Recitation on Wednesday.
- Section 103: Recitation on Friday.
- Note: Section 103 is significantly smaller (approx. $5$ to $6$ students). Students from other sections are encouraged to move to Friday to balance group sizes.
Office Hours: Monday, Wednesday, and Friday from 2:00 PM to 3:00 PM in the Computer Science Department building. Availability is also open on Tuesday and Thursday afternoons by appointment via email.
Prerequisites: Completion of Discrete Mathematics and CS 2440.

Computer Science as a Quantitative Science: Similar to biology (the study of life) and physics (the study of the laws of the universe), Computer Science is the formal study of computations.
Core Learning Outcomes:
1. Identify and Manipulate Models of Computation: Understanding the theoretical frameworks for how machines compute.
2. Regular Expressions (Regex): Mastery of tools and theoretical behaviors for identifying specific string patterns.
3. Model Selection and Complexity: Learning three major computational models and choosing the appropriate level of complexity for a given task.
4. The Halting Problem: Identifying the limits of what is computable; understanding that some problems cannot be solved by algorithms.
5. Mathematical Rigor: Transitioning from a "hands-on" programmer mindset to that of a scientist. This involves using formal mathematical language and writing proofs that could convince any mathematician.

Grading Breakdown:
- Final Exam: $30\%$ of the total grade.
- Midterm Exams (2): $15\%$ each ( $30\%$ total). One occurs at the one-third mark of the semester, and the second occurs at the two-thirds mark.
- Semester Homework (3-4 assignments): $15\%$ (traditionally graded for correctness).
- Formative/Training Homework (Weekly): $15\%$ . Graded based on effort and completion. Categories include "Correct," "Work in Progress," or "Incorrect." Students are encouraged to redo assignments until they are correct to ensure mastery.
- Quizzes: $10\%$ . These occur almost every session to refresh memory of the previous class. Multiple attempts are allowed to encourage learning over testing.
- Juggling (Reflections): $10\%$ . A brief activity after each session requiring three takeaways, two points of confusion, and a short summary (2-3 sentences).

Attendance Policy: Attendance is expected for both lectures and recitations.
- Students are granted $4$ "free" absences to cover minor illnesses or personal emergencies.
- After the $4$ th absence, each subsequent absence results in a grade deduction of one-third of a letter grade (e.g., B to B-).
- Extended absences for significant life events (e.g., family tragedy) should be discussed individually.
AI Policy: Artificial Intelligence is permitted as a tutor or learning aid. However, copy-pasting solutions is considered a violation of academic integrity, equivalent to copying from a textbook or person. AI may be used by the instructor to synthesize common questions from the "Juggling" assignments.
Late Submissions: Baseline policy is that late submissions are not accepted without a documented emergency (e.g., car accident).

The Black Box Model: Computation is viewed as an input transitioning through a process to produce an output.
- Input: Usually binary string data.
- Output: Primarily Binary/Boolean (Yes or No). Most complex function outputs can be reduced to a Boolean question (e.g., "Is the result of this function equal to value X?").
Finite State Machines (FSM): The foundational model for this course.
- Finite: Machines have a limited, fixed amount of memory (states).
- Mechanism: Only one state can be active at a time. The machine reads input bit-by-bit and changes states based on internal rules (wiring).

Problem: Design a machine to determine if a binary string has an even or odd number of ones.
Requirements: Two states are necessary.
- State 1 (Red): Represnets an even number of ones (at start, $0$ is even, so this is the initial state).
- State 2 (Green): Represents an odd number of ones.
Transition Rules:
- If in Red and read a $0$ : Stay in Red.
- If in Red and read a $1$ : Move to Green.
- If in Green and read a $0$ : Stay in Green.
- If in Green and read a $1$ : Move to Red.
Result: After reading the entire string, the final state (color) provides the answer. This is functionally equivalent to a flag or a modulo 2 operation in programming languages like Java.

Finite Automata (DFA and NFA):
- Simplest versions of machines.
- Read input left-to-right once; no backtracking.
- Used for pattern recognition and regular expressions.
Pushdown Automata (PDA):
- Builds on finite automata by adding a stack for limited memory.
- Capable of parsing computer languages (e.g., verifying if a Java program follows language rules).
Turing Machines:
- The most powerful computational model.
- Can move back and forth on input and rewrite it, using input as RAM.
- The formal definition of an algorithm.
Uncomputable Problems:
- Problems existing outside the hierarchy that no machine can solve.
- Example: The Halting Problem—determining if an arbitrary algorithm will eventually stop or loop infinitely.

Question: Is it possible to take attendance at the end of class? I have a 20-minute run from my previous class.
Response: For the first day, attendance will be taken at the end. For future sessions, the method (QR code, sign-in sheet, etc.) will be determined, but the 20-minute transition time is noted.