CSE 105: Intro. to Theory of Computation, Fall 2010

Section ID: 692209
Course Webpage: http://www-cse.ucsd.edu/classes/fa10/cse105/

Course Description: This course introduces the basic, formal ideas underlying the notion of computation. Syllabus: finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability, undecidability, the halting problem, Turing reductions, map reductions, introduction to computational complexity.

Textbook: Sipser, Introduction to the Theory of Computation, 2nd edition.
(The first edition is not very different from the second and should be mostly usable as a substitute.)

Announcements: Course announcements will be made through this course web page. (Announcements are in reverse chronological order, most recent announcement on top.) You are responsible for checking the webpage regularly for announcements.

This is a reminder the final exam is this week on Thursday at 11:30pm-1:30pm. (Notice, this is a 2 hour final exam, and not a 3 hour one as listed on triton link.) Daniele will hold office hours on Thursday as usual during final week, in case you have some last minute questions.
Homework 6 is due Fri. Nov. 19. (Solutions)
Homework 5 is due Wed. Nov. 10. (Solutions)
Homework 4 is due Wed. Nov. 3. (Solutions)
On Thu. Oct. 21, Daniele will hold office hour at 1pm rather than 9am
Homework 3 is due Wed. Oct. 20. (Solutions)
Homework 2 is due Wed. Oct. 13. (Solutions) The homework as distrubuted in class and previously posted here contains a small typo: on line 6 of problem 2 the words DFA and VSA should be swapped! The problem asks to give a transformation from VSA to DFA.
Homework 1 is due Wed. Oct. 6. (Solutions)
Due to student conflicts, we are no longer rescheduling the 3pm session to 4pm. Discussion sessions will be at 3pm and 5pm as originally scheduled.
No TA office hours on Sep 27-28. Daniele will hold regular office hours on Sep 30
We are in the process of rescheduling the first discussion session from Wed. 3-4pm to Wed 4-5pm, to avoid conflict with TAs classes. Time and room will be posted as soon as we find an available space.
We will be using QuickTopic CSE105FA10 as a discussion board for the class.

Schedule	Day	Time	Room
Lectures	Monday, Wednesday, Friday	12:00pm-12:50pm	CENTR 109
Discussion	Wednesday	3:00pm-3:50pm	CENTR 109
Discussion	Wednesday	5:00pm-5:50pm	CSB 004
Quiz 1	Monday, October 25	12:00pm-12:50pm	CENTR 109
Quiz 2	Monday, November 22	12:00pm-12:50pm	CENTR 109
Final	Thursday Dec 9	11:30pm-1:30pm	CENTR 109

The syllabus will be covered in roughly the same order as presented in the textbook (Chapters 1-5). At the end of each chapter you can find several exercises and problems that are an excellent complement to the reading and homework assignments given in class. You can work on those problems on your own, as the relevant material is covered in class, and if you have any question, bring them to class, discussion or office hours, or post them on the discussion board. The more problems you solve, the better you will be prepared for the midterm and final exam.

Staff

	Name	Office Hours	Room	Email (*)
Instructor	Daniele Micciancio	Thursday 9:00am-10:00am	EBU-3b (CSE) 4214	dmiccian(at)ucsd.edu
TA	Ruixin Yang	Monday 4:00pm-6:00pm	EBU3b B250A	r4yang(at)cs.ucsd.edu
TA	David Curran	Tuesday 2:00pm-3:00pm	EBU3b B250A	dcurran(at)cs.ucsd.edu

(*) Important: Email should be used only for questions that require individual attention (e.g., exam regrades, etc.). For technical questions (e.g., about homeworks, material presented in class, etc.) you should use the QuickTopic discussion board located at Discuss CSE105FA10 so that everybody can benefit from the answer. All course related emails sent to the intructor or TA should include the string CSE105 in the subject line (anywhere, possibly within a more descriptive message). Also, your email messages should be in plain text format and include valid sender and return addresses. Non comforming emails risk to be automatically deleted by the spam filtering programs and are likely to never reach the instructor/TA.

Course requirements and policies

Class members are expected to do all of the following in order to satisfactorily pass this class:

Attending lectures
Studying relevant chapters of the textbook, as covered in class
6 or 7 Homework assignments
2 (in class) exams
1 final exam

Homework assignments will use JFLAP, a java package for experimenting with automata and formal languages.

Midterm exams are scheduled during regular lecture hours on Monday October 25 and November 22, 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. Homeworks will be weigthed equally, with the lowest hw grade dropped, and account for 40% of course grade. The midterm exams will contribute another 30%, and the final exam will give the remaining 30%. Both the midterms and the final exam will be closed books, closed notes. You can take 1 double sided sheet of notes to each exam, but the notes must be your own.

Grades will be available through GradeSource. If you are enrolled in the class you will receive an email from gradesource with instructions and a secret number to access your grades.

Grades will NOT be assigned on a curve. You will receive a grade based on your own performance. If everybody does well, everybody will get an A! Final grades will be based roughly on 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.

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). In particular, you are encouraged to form study groups, but no form of collaboration is allowed in the solution of the homeworks, midterm and final exams. Also, you should not use any external resource (e.g., the Internet, Google, etc.) when working on the homeworks. (Of course, using such resources as a study tool is fine, but if anything you find using such resources end up being directly useful for the solution of a homework, you should clearly acknowledge the use of the resource on your solutions to avoid academic dishonesty charges.)

Regrade requests on any assignment or exam are only accepted within a week after the graded object has been returned. Do not modify your solutions after they are returned to you. If you alter your solutions, you loose any right to request a regrade of that exam. Modifying the exam and then bringing it back to ask for a regrade will be treated as a violation of academic honesty rules, and so prosecuted.