CSE 200: Computability and Complexity

Winter 2005: Sec. ID 518442

Course Description: Computability review, including halting problem, decidable sets, r.e. sets, many-one reductions; TIME(t(n)), SPACE(s(n)) and general relations between these classes; L, P, PSPACE, NP; NP - completeness; hierarchy theorems; RP, BPP

Prerequisites: Knowledge of automata theory and basic theory of computation as offered by UCSD undergraduate course CSE 105, or Chapters 0-5 of the text book. (Specific topics assumed are: finite state automata, regular expressions, context free grammars, push down automata, and Turing machines.) Undergraduate level courses on algorithms (CSE 101) and discrete mathematics (CSE 20, CSE 21) are also assumed.

Course webpage: http://www.cse.ucsd.edu/classes/wi05/cse200/

Instructor: Daniele Micciancio

Office Hour: Wednesday 3:00pm-3:50pm in AP&M 4202

Email: daniele(at)cs.ucsd.edu. Important: all course related emails sent to the intructor should include the string CSE200 in the subject line (anywhere, possibly within a more descriptive message). If you do not include CSE200 in the subject, your email risks to be discarded by my spam filtering program. Also, please send email in plain text format, and with a valid return address. Emails with no return address or message included as an html attachment are also discarded as spam.

Lectures: Monday and Wednesday 5:00pm-6:20pm in Peter 104

TA: Chris Calabro

Office Hour: Friday 12:00pm-13:00pm in EBU-1 6307A

Email: ccalabro(at)cs.ucsd.edu

Textbook: Introduction to the Theory of Computation by Mike Sipser, PWS Publishing Co., 1997. (See book website for Errata.)

Also suggested: Computers and intractability : a guide to the theory of NP-completeness, Michael R. Garey, David S. Johnson

Announcements: Course announcements will be made through the course mailing list. All students should add themselves to the list through the page https://www.cse.ucsd.edu/mailman/listinfo/cse200. You are responsible for providing a working email account, otherwise you may miss important course announcements. E.g., we may use the mailing list to send you hints about the solution of the homework assignments.

Grades, Discussion board: grades and a discussion board will be available on WebCT as soon as ACS sets up the accounts. You can find the WebCT Step 1 guide at http://iwdc.ucsd.edu/step1_webct4.pdf. Typically, you can access WebCT using your email username and password.

Course Schedule

Requirements

Students are expected to regularly attend lectures, and read all relevant sections of the text book.

The course has a number (5-7) of homework assignments, one midterm exam, and one final exam. Your grade is based on your course score as determined by the formula: 49*HS/HT + 0.17*MS + 0.34*FS, where HS is the sum of the scores received on the homeworks, HT is the sum of the maximum possible scores in the homeworks, MS is the midterm score (out of 100), and FS is the final exam score (out of 100).

Homeworks

Homeworks assignments and solutions will be distributed through this webpage. Each assignment typically consists of a problem, some motivating discussion, and an extra question. You are only required to provide an answer to the first problem. The discussion gives motivation and explainations about the problem, but it is not typically helpful for its solution. The extra question is there only for those of you who find the first problem too easy, and need more food for their brains. The extra question may be very hard and will not be formally graded, so unless you have something meaningful to say about it, just skip it.

• Homework 1: Due Wednesday January 12 in class (See important policies below.) [Solutions.ps]
• Homework 2: Due Monday January 24 in class (Usual policies apply.) [Solutions.ps]
• Homework 3: Due Monday February 7 [Solutions.ps]
• Midterm exam [Solutions.ps]
• Homework 4: Due Monday February 28 [Solutions.ps]
• Homework 5: Due Wednesday March 9 [Solutions.ps]

Mathematical writing: This course involves mathematical abstraction and proofs. Being able to deal with these is one of the important things to learn. In both homeworks and exams, you will be graded based on the correctness, clarity and accuracy of mathematical exposition. Make sure what you write makes sense. Define notation before you use it, distinguish between different types of objects like machines, languages and strings. Answers that "don't make sense" will not get much credit. Your solution should have a logial flow from beginning to end. Remember, you are graded on what you write, not on what you think you "meant". So, make sure you write what you mean.

Write top to bottom, left to right on the page. Don't scatter information all over. Be as concise as possible. Read through whatever you write before turning it in. Make sure there is an argument with a clear flow. If you say lots of different things, you are not going to get points just because one of them is right; indeed, you will get less points for a jumble which sort of includes something right, than for something clear even if not the entire answer.

For homework assignments, first write a rough draft, then write a new, final draft to actually turn in. Think about it from the point of view of a grader: how are you making sure that person will understand? Spend time on the writeup. Reread it after it is written, try to be in the mindset of someone who does not know what you are thinking, but only has your solution to look at. Make sure it can be undestood by suh a person.

For more information about mathematical exposition, see the articles under Mathematical and technical writing available from Mihir Bellare's webpage at http://www.cse.ucsd.edu/users/mihir/education.html.

Reading

Here are a few pointers to the book where you can find specific topics covered in class. This is not an exhaustive list of reading assignments. You should use your class notes as a reference to what has been covered, and these pointers are intended only as a help to locate relevant sections of the text book mostly for topics that are presented in different order.

• Most of the material covered in the first week is presented in Chapters 3-5 (Turing machine, recognizers, deciders, undecidability). The formal definition of Oracle Turing machines and Turing reducibility can be found in Section 6.3.
• The hierarchy theorems are covered in Section 9.1. After we are done with that, we will move back to chapter 7.
• The simulation technique for the tighter space hierarchy theorem presented in class can be found in "Halting space bounded computation", M. Sipser, Theoretical Computer Science 10:335-338, 1980 (UCSD Library call number QA1 .T383. Preliminary version also available in Proceedings of FOCS 1978.) The paper will become available through the UCSD library electronic reserves shortly.
• The polynomial time reduction from the Minimum distance problem to the Maximum likelihood decoding problem covered in class on January 26 is described in the paper "Approximating shortest lattice vectors is not harder than approximating closest lattice vectors", by Goldreich et al., Information Processing Letters 71(2):55-61, 1999. The paper considers approximation versions of the problem (the exact version covered in class correspond to approximation factor equal to 1) , and first gives a reduction between two similar problems on point lattices, before giving the reduction between the coding problems described in class.
• We are covering polynomial time reductions before the theory of NP-completeness. You can find the reductions among the problems covered in class in Sections 7.3 and 7.5 of the textbook. You can ignore the remarks about NP-completeness in those sections until we cover the Cook-Levin theorem from Section 7.4.
• We covered pretty much all of chapter 7, including the Cook-Levin theorem, and several examples of NP-complete problems. This concludes our discussion of time complexity classes.
• Space complexity. You can find this in Chapter 8. We will cover all the material presented in that chapter pretty much in the same order as it appears in the book.

Policies

Exams: The exams are in class, closed books and notes, no calculators, cellphones, pda's, etc. No "blue-books" are required, you will write on the exam itself, but you may want to bring your own scratch paper.

There are no makeup exams under any circumstances. If you do not take the midterm you get zero on it, unless your absence is due to a demonstrated personal health problem at the time, in which case the weight of the midterm will be shifted to the final. If there is any anticipable reason for which you cannot take the final exam at the scheduled time, don't take the course. If you do not take the final you get a zeor on it.

Homeworks: Each student must do their homeworks on their own, without any help from other students and without consulting any sources other than their owncourse notes, course handouts and the course text. In particular, you are not allowed to use any material from pervious years of this course, and you are not allowed to use the Internet. However, sutdents are allowed to study together for the exams.

Solutions to homeworks or exam problems should use without proof only results from class of class notes, and results of previous homework or exam problems. You may not use other results wihout proof, even if they are in the text book. If you are not sure about what can or cannot be used wiuthout proof, ask the instructor.

Homework assignments are due in class on the day indicated on the assignment. Late problem sets are not accepted. Please do not turn in problem sets at any place other than in class. (If you can't make it to class, give it to someone else to turn in for you.) Regrade requests on any homework or exam are only accepted util two weeks after the graded object is question has been returned. Do not modify your solutions after they are returned to you. If you alter the your solutions, you loose any right to request a regrade of that specific assignment or exam.

If your homework solution has more than one sheet of paper, the sheets should be stapled together, not clipped or folded at the corner. Turn in neat, readable solutions. either handwritten or typeset. Points can be deducted otherwise.

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. Cheating, including failure to abide by the above course rules, is taken very seriously. Academic dishonesty cases are prosecured in conjunction with the Dean of Student Affairs and can result in probation or dismissal. Students have been caught cheating in this and other gradutate courses in this department in the past, and have been so prosecuted. Some examples of dishonest academic conduct are: modifying your graded exams or homeworks after they are returned and then bringing them back for regrade, copying from others or bringing unallowed material to exams, sharing electronic or other versions of your homework problems, using solutions from previous year of this or other courses.