Welcome to CSE 105! This course will help you answer fundamental questions about computing:
What problems are computers capable of solving?
What resources are needed to solve a problem?
Are some problems harder than others?
In this course, we will explore what it means to be "computable". 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" in this last model 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.
Remote instruction
In the first two weeks of the quarter (and whenever required) all lectures/discussions/office hours will be on zoom.
To simplify life, we will use the same zoom meeting room for all of them:
zoom link.
If you want to connect directly, the meeting id is 93416739827 and the password is cse105.
Class times
Note that the locations below are only for in person instruction. When the university is remote, we will use the zoom meeting room given above.
Type
Day
Time
Location
Lecture
MW
5-6:20pm
Peterson 108
Discussion A01
M
4-4:50pm
Peterson 108
Instructors
Role
Name
Email
Office hours
Professor
Shachar Lovett
slovett@ucsd.edu
Wed 3-4pm, CSE 4234
TA
Parth Doshi
pdoshi@ucsd.edu
Tue 12:30-1:30pm, CSE B275
TA
Satvik Gupta
sag005@ucsd.edu
Fri 5:00-6:00pm, CSE B275 (Tantative)
TA
Tony Hu
toh008@ucsd.edu
Thu 9:30-10:30am, CSE B240A
TA
Saketh Khandavalli
lkhandavalli@ucsd.edu
Wed 11:00am-12:00pm, CSE B215
TA
Sanju Koya
spkoya@ucsd.edu
Tue 3:30-4:30pm, CSE B260A
TA
Venkat Krishnamohan
vkrishnamohan@ucsd.edu
Mon 10:00-11:00 am, CSE B240A
TA
Nirmal Thomas
nithomas@ucsd.edu
Fri 10:00-11:00am, CSE B275
TA
Satish Yerva
syerva@ucsd.edu
Wed 1-2pm, CSE B260A
Tutor
Dustin Lin
d6lin@ucsd.edu
Thurs 1:00-2:00pm, location TBD
Textbook
Michael Sipser, Introduction to the Theory of Computation, 3rd ed.
We will use the international edition, which is much more affordable. It is available on Amazon or the UCSD bookstore for about $20.
See also the errata for a list of known typos/errors in the book.
Grading
The final grade will be composed as follows:
Final exam: 40% (must pass to pass class)
Midterms: 30% (2 midterms)
Homework: 30% (7 homeworks)
A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows:
A range (A-,A,A+): 88.0% - 100%
B range (B-,B,B+): 75.0% - 87.9%
C range (C-,C,C+): 60.0% - 74.9%
D: 50.0% - 59.9%
F: below 50.0%
The designation of +/- inside a grade range is based on the instructor discretion, and will depend on the grade distribution as well as your particiaption in class
and discussion, coming to office hours, and improvement throughout the class.
Homework
Homework is 30% of the final grade. There will be 7 homeworks.
Homework is due on Mondays midnight. Submission is online via Gradescope
(you should already be enrolled; if not, enroll using your @ucsd.edu email and the code V8RJJK).
Homework should be solved in groups of 3-4 students (you can change groups for different homeworks; students may be in different sections).
Submit only one submission per group.
No collaboration or discussion outside the groups is allowed (but if you are stuck on a problem, please come to discussion or office hours).
Participation
I want to keep this class as interactive as possible, to help you follow lectures better and to help identify mis-understood concepts early on. For this we will use clicker for in person classes and zoom pools for remote classes.
Discussion forums
We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework. Please use public posts for general questions about the class or material, and private posts for personally relevant questions or questions that can reveal a solution or approach to a homework problem.
Podcast
You can access all previous classes through podcast.
Academic integrity
Your goal is to excel in this class with integrity.
It is an academic violation to:
Ask others to give you homework or test answers
Share your answers on homework or tests
Work on the homework with anyone other than your homework partners
Share answers or notes while taking an exam
Search the internet or other resources not provided for the class for homework solutions
Use chegg or similar websites/services to ask or get answers for homework or exams
This is a partial list of common academic violations in this class.
If you are not sure if some activity constitutes an academic violation or not, please ask us before doing it. We will report academic violations to the academic integrity office. See also the detailed academic integrity policy for more information.