An online version of this syllabus is available on the course web page.

**Web page:** https://cseweb.ucsd.edu/classes/fa22/cse105-a

**Canvas:** https://canvas.ucsd.edu/courses/40756

**Textbook:** M. Sipser, *Introduction to the Theory of
Computation* (any edition)

**Course Description:** In this course, we will explore
what it means for a problem to be “computable”, i.e. solvable by an
algorithm or computer program. We begin with a very simple model of
computation, and work our way to the most powerful, the Turing machine,
named after Alan Turing,
who formalized the notion of “algorithm” even before there were any
physical computers. You’ll also learn about the relationship of these
models to some essential tools in a computer scientist’s toolkit, such
as regular expressions and context-free grammars. Finally, you’ll
develop your technical communication skills in writing formal arguments
and proofs.

**Tools:** See course webpage
for additional information on **Piazza** (discussion
board), **Gradescope** (homework submission, grading),
**iClickers** (active learning/attendance),
**FLAP/flap.js** (machine visualization) and
**LaTeX/Overleaf** (typesetting.) Enrollment/access to
Piazza and Gradescope should be automatic through Canvas. Make sure you
have your clicker registered on Canvas by Sunday, Oct 2. Intallation
instructions for JFLAP/flap.js and LaTeX/Overleaf are on the course
webpage.

**Instructor:** Daniele Micciancio

**TAs:** Parth Doshi, Satvik Gupta, Saketh Khandavalli,
Venkat Krishnamohan, Shreya Saha, Madhav Wagle, Satish Yerva

See the canvas calendar for the staff’s **office hour**
schedule. We have multiple **office hours** almost every
day. So, come see us whenever you need help!

For general/technical questions that may be of interest to other
students (e.g., clarifications about homework or lectures), you are
encouraged to use Piazza. If you
are not sure if your question should be publicly posted, or want only
the instructors/TAs to read it, you can still use piazza and mark it as
*private*. For in-person questions/help about homework
assignments, you should attend discussion and/or office hours of any of
the course staff.

**Lectures:** Monday, Wednesday 5:00pm-6:20pm in PETER
108

**Discussions:** Friday 12:00p-12:50p in WLH 2001

**Exams:**

- Midterm 1: We 10/19/2022 (in class)
- Midterm 2: We 11/09/2022 (in class)
- Final: Th 12/08/2022, 8:00p-10:59p (TBA)

**Course Calendar**: For weekly topics, reading
assignments and homework due dates, see the course calendar posted on
the course webpage. You are responsible for all
the reading material posted up to the current lecture. (Slides/lecture
notes available on Canvas.)

The formal prerequisites for CSE 105 are CSE 12 and CSE 21, as well as all implied prerequisites of those classes (most importantly CSE 20.) One of Math 15B, Math 100A, or Math 103A may substitute for CSE 21.

We expect you to be comfortable with mathematical concepts such as sets, tuples, relations, and functions. You should in particular be familiar with the notion that a set is (or isn’t) closed under some operation. We expect you to be comfortable with manipulating formal mathematical definitions, reading and writing formal proofs.

We further expect you to be comfortable with basic data structures, such as trees and graphs; with basic algorithms on those data structures, such as depth-first search and graph reachability; with basic tools of algorithm analysis, such as big-O notation; and with general computer and programming concepts, so to be able to easily pick up a new programming language and write short snippets of code.

Our objectives in CSE 105 are: (1) to define computation formally; (2) to show that there are limits to what is computable; (3) to reason precisely about computation and its limits. Along the way, we will pick up some useful tools (finite automata, regular expressions, context-free grammars) and lay the foundation for the study (in CSE 200) of complexity theory.

**Learning outcomes.** A successful student will learn
the following in CSE 105:

- Recall, understand and manipulate formal definitions for DFAs, NFAs, CFGs, and TMs, and understand implications of these definitions and variants thereof.
- Understand and manipulate language definitions written in “set-builder” notation.
- Understand and generate closure-property proofs for claims of the
form “if
*L*is a regular language, then so is*f(L)*” for*f*transforming a language into another, and also for other classes of languages than regular languages. - Understand the meaning and implications of closure properties, especially for the standard language operations; e.g., if two languages are not regular, can/must their concatenation be regular?
- Understand and use reductions for decidability and undecidability, and mapping reductions for recognizability.
- Given a language, determine whether it is decidable or undecidable and prove that claim formally and convincingly.

**iClickers:** We will use iClickers as a learning tool
and to measure class attendance/partecipation. Make sure you have your
clicker registered with Canvas by **Sun October 2**. See
course webpage for instructions.

**Attendance:** Podcast recordings of the lectures will
be available (shortly after class, typically within a day) at https://podcast.ucsd.edu/watch/fa22/cse105_a00 for
review, or for making up for occasionally missing a lecture. Still, you
are expected to **attend lectures in person** (unless you
are sick), make sure that your iClicker is registered in Canvas, and use
it to **actively partecipate**. You should
**not** come to lecture if you are sick or not feeling
well. In order to allow some flexibility, the iClicker/partecipation
score will **not** directly contribute a fixed portion of
your grade. Rather, it will be used to determine your “discretionary
score” (see below.)

**Exams:** There will be 2 midterm exams and a final.
Midterm and Final exams dates/times have been set by the university
before registration (Midterms are during regular class times), and
everybody is expected to attend. There will be no make up midterm or
final. Not showing up to either exam will count as 0 grade, unless your
absence is due to a demonstrated personal health problem at the time.
Exams will be closed book, closed notes.

**Homework** assignments will *typically* go out
Thursday night, and be due on Friday the following week. (See course
webpage for assignment schedule.) So, there will be one day overlap
between the two. This is to allow you to look at the assignment before
the discussion on Friday. You should try to submit your homework by
Thursday, so you can focus on the new assignment. Think of the Friday
deadline as a one-day extension, in case you need that extra time for
whatever reason. No submissions will be accepted after Friday. Homework
assignments are distributed on Canvas and submitted on gradescope.
Homework should be done in groups of **one to three**
people. You are free to change group members at any time throughout the
quarter. Problems should be solved together, not divided up between
partners. A **single representative** of your group should
submit your work through Gradescope. On submission, make sure to add all
your group members to the Gradescope assignment. Submissions must be
received by 11:59pm on the due date, and there are no exceptions to this
rule. We recommend that you submit early drafts to Gradescope so that in
case of any technical difficulties, at least some of your work is
present. You may update your submission as many times as you’d like up
to the deadline. Additional submission instructions may be provided on
each individual homework assignment.

**Grades** for homework and midterm exams will be
available through Gradescope. The course grade is based on your
homework, midterm exams and a final exam. Denoting your percentage
scores on these as *H*, *M*, *F*, we compute your
raw score *RS* and total score *TS* via the formulas

RS= 0.35H+ 0.30M+ 0.35F

TS= 0.95RS+ 0.05DS

where *DS* is your discretionary score, to be explained. Your
grade is determined by your total score TS. Now let us explain. In
computing the raw score, homework weigh 35%, midterm exams 30% and the
final exam 35%. In determining *H*, homework assignments are
weighted equally, and the lowest homework score is dropped. For
*M*, the two midterms also carry equal weight (15% each), but the
weight of your lowest midterm will be moved to the final exam if your
final score is higher than that midterm. (So, the final exam is your
opportunity to improve a low midterm score.) Your total score is 95%
your raw score RS and 5% your discretionary score DS. How is DS
computed? Its default value is RS. Thus, if you do nothing to either
increase or decrease it (which is likely true for most students), then
TS is just RS. However it is possible to increase DS, and also possible
to decrease it, relative to its default value RS. Actions that may
increase your discretionary score DS above RS include attending lectures
(with attendance recorded by iClicker partecipation), answering Piazza
posts by other students, creating positive impression through
interaction or posts, spotting mistakes or bugs in our posts, etc.
Actions that may decrease your discretionary score DS below RS include
requesting exceptions to policies stated here or on the slides, asking
administrative questions already answered here or on the slides,
requesting actions already denied by policies here on the slides and
asking for special consideration. The latter includes asking that your
grade depend on things beyond your performance. An example is ``Please
pass me because I am graduating this quarter.’’ This is not appropriate
because it is effectively asking for unfairness, that you be treated
differently from other students.

The class is *not* graded on a curve. There is no fixed
correspondence between letter grades and particular scores, nor is the
grade distribution dependent in some fixed way on statistics such as the
average or standard deviation. But, just to give you an indication of
where you are headed, in the past grades followed roughly the following
scale: 50-55% (D), 55-70% (C), 70-85% (B), 85-100% (A), with (+) and (-)
assigned to the instructor discretion. This includes, but is not limited
to improvement over the quarter, class participation, and natural
“breaks” in the distribution of scores. As per university rules, a P
means a C- or above.

**Regrade requests**. Regrades need to be requested
within three days of announcement of grades. The regrade window will be
set in Gradescope. In the regrade request, include a brief but detailed
explanation of why you think there was an error in the grading. A
regrade request may lead to us reviewing the entire assignment and may
lead to the score being adjusted up or down depending on any errors
found in the original grading. There will be no regrade window for the
final exam. Finals will be available for inspection only after the
quarter is over and class grades have been assigned.

**Academic honesty:** All students are expected to be
familiar with and abide by the rules of UCSD Policy on Integrity of
Scholarship as described in the UCSD General Catalog. In case of
cheating, such policy will be enforced. This means an F grade in the
course, and action by the Dean of your college (probation or suspension
from UCSD).

**Homework and Collaboration Policy** You are encouraged
to form study groups to discuss the material presented in class and the
homework assignments. However, you should write the solutions to the
homework entirely on your own or within your team. If you collaborated
with other students on the solution of the homework (beside your team
mates), you must list the name of everyone you discussed the homework
with, and which problems you discussed with whom.

You can use Internet, additional textbooks, and any material you find
useful as a study tool. However, the use of any such resource in the
solution of homework assignments is prohibited. In particular, you
should **not** search for solutions to homework problems
on-line, or post homework related questions on any site other than the
course web discussion board. Should you still (inadvertently) come
across material on the internet that is closely related to the solution
of the homework assignments, make sure you clearly aknowledged your
source in your solutions to avoid academic dishonesty charges. Posting
of your solutions (as a whole, or in part, even after the homework due
date) is also prohibited. No form of collaboration is allowed during
midterm and final exams.

We are committed to fostering a learning environment for this course that supports a diversity of thoughts, perspectives and experiences, and respects your identities (including race, ethnicity, heritage, gender, sex, class, sexuality, religion, ability, age, educational background, etc.). Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive.

Our instructional staff will make a concerted effort to be welcoming and inclusive to the wide diversity of students in this course. If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door. Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input.

We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community (https://ucsd.edu/about/principles.html). Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.

If you experience any sort of harassment or discrimination, please contact the instructor as soon as possible. If you prefer to speak with someone outside of the course, please contact the Office of Prevention of Harassment and Discrimination: https://ophd.ucsd.edu/.

We aim to create an environment in which all students can succeed in this course. If you have a disability, please contact the Office for Students with Disability (OSD), which is located in University Center 202 behind Center Hall, to discuss appropriate accommodations right away. We will work to provide you with the accommodations you need, but you must first provide a current Authorization for Accommodation (AFA) letter issued by the OSD. You are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged.

If you are experiencing any basic needs insecurities (food, housing, financial resources), there are resources available on campus to help, including The Hub and the Triton Food Pantry. Please visit http://thehub.ucsd.edu/ for more information.