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.
Sat 11/30 2 pm - 5 pm, CSE 4217 Sun 12/8 1 pm - 5 pm, CSE 4258
TA
Dhiren Lad
dlad@ucsd.edu
Thur 2:00pm - 3:00pm, 7:30pm - 8:30pm CSE B240A
TA
Sankeerth Rao
skaringu@ucsd.edu
Tue 8am-10am, CSE 4217
TA
Manish Singh
mksingh@ucsd.edu
Fri 1 pm - 3 pm, CSE B240A
TA
Ritwik Vatsyayan
rvatsyay@ucsd.edu
Mon 6:30pm-8:30pm, CSE B240A
TA
Lisa Xue
zixue@ucsd.edu
Tue 10am - 11am CSE B215, Wed 1pm - 2pm CSE B240A
TA
Ahmed Youssef
a1yousse@ucsd.edu
Wed 8am - 9am CSE B250A, Wed 9am - 10am CSE B215A
Tutor
Joshua Comes
jcomes@ucsd.edu
Wed 7pm-9pm, CSE B250A
Class times
Type
Day
Time
Location
Lecture
MW
5-6:20pm
Peterson (PETER) 110
Discussion A01
W
7-7:50pm
Cognitive Science Building (CSB) 002
Discussion A02
W
8-8:50pm
Cognitive Science Building (CSB) 002
Discussion A03
F
4-4:50pm
Center Hall (CENTR) 109
Discussion A04
F
5-5:50pm
Center Hall (CENTR) 109
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 for about $15, or the bookstore for about $19.
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; lowest grade is dropped)
Homework: 20% (7 homeworks; lowest grade is dropped)
Participation: 10% (see explanation below)
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. It 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 20% of the final grade. There will be 7 homeworks, your lowest grade will be dropped.
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 M3DNJ3).
Instructions:
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
Participation is 10% of the total grade. For full participation grade, you need to collect 20 participation points. There are several ways in which you can get particiaption points:
1 point: coming to lecture and participating in clicker discussions (max 2 per week, not including midterms)
1 point: coming to discussion section (max 1 per week)
2 points: solving the weekly review quiz
i-Clicker
Please register your i-Clicker here.
If you are asked to pay, please use this alternative form.
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.
Podcast
You can access all previous classes through podcast.