Fall 2008: Sec. ID 631675
CourseDescription: 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, NL, P, NP, coNP, PSPACE; NP-completeness; hierarchy theorems; RP, BPP, circuit complexity classes.
Prerequisites: Knowledge of automata theory and basic theory of computation as offered by UCSD undergraduate course CSE105, or Chapters 0-5 of Sipser's book. (Specific topics assumed are: finite state automata, regular expressions, context free grammars, push down automata, and Turing machines.) Undergraduate level courses on algorithms (CSE101) and discrete mathematics (CSE20, CSE21) are also assumed.
Course webpage: http://www.cse.ucsd.edu/classes/fa08/cse200/
Lectures: Tuesday and Thursday 12:30am-1:50pm in EBU3b 2154
| Staff | Name | Email (Read note!) | Office Hour |
|---|---|---|---|
| Instructor | Daniele Micciancio | daniele(at)cs.ucsd.edu | Friday 2-3pm EBU3b 4214 |
| TA | Petros Mol | pmol(at)cs.ucsd.edu | Monday 9:30-11am in EBU3b B250A |
Textbook: The standard reference textbook for this course is
Requirements: Students are expected to regularly attend lectures, and read all relevant sections of the text book, and other reading material distributed in class or through this webpage. The course has a number (4 or 5) of homework assignments, and a take-home final exam, which will contribute 50% of your grade each. See below for collaboration policies. Final exam is due on TBA, that is, the end time of the final exam as scheduled by the department. This will be a firm deadline, no late submissions accepted.
Sending emails: all course related emails sent to the intructor or TA 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 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 may also be discarded as spam. If the emails is related to a homework assignment, include the names of all the group members in the email.
Homeworks assignments and solutions will be distributed through this webpage:
Here is a list of topics I covered in the lectures last year. This list is tentative and will be updated as the course goes on:
Collaboration: You may work on the homework assignments in teams of up to 3 students. Final exams have to be done individually, no collaboration allowed for the final. For the homeworks, each team should submit a single (collaborative) solution to the assignment. Teams may change from one homework assignment to the next. All team members are responsible for partecipating in the solution to all problems submitted, unless a note is attached to the assignment, specifying which problems a group member was not involved with. (Non-partecipating members will not get credit for that problem, but will also not be responsible for academic honesty for that problem.)
Students should not look for answers to homework problems in other texts, on the web, or from people other than their study group, professor or TA. However, students may use other texts as a general study tool, and may accidentally see solutions to homework problems. In this case, the student should write up the final solution without consulting the test or other source, and should give acknowledgment of the source on the first page of their solutions. Such a solution may be given partial or no credit if it follows the text too closely.
Ethical guidelines:
Homeworks and final exams should be solved without consulting any sources other than the instructor/TA, your own course notes, course handouts and the textbook. 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.
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 without proof, ask the instructor.
Homework assignments are due before the class on the day indicated on the assignment. Regrade requests on any homework or exam are only accepted until two weeks after the graded object in question 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 specific assignment or exam.
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/programs, 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 such 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.
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 prosecuted 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, using external sources in the solution of your homeworks/final without disclosing the source, copying from others, sharing electronic or other versions of your homework problems, using solutions from previous year of this or other courses.