Course Webpage: http://www-cse.ucsd.edu/classes/sp08/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 reducibility, introduction to complexity theory.
Instructor: Daniele Micciancio
TAs: Steve Checkoway, Will Chang
Textbook: You can you either of the text-books recently adopted for this course:
The two books are pretty much equivalent when it comes to the basic material covered in this course. If you already have one of the two books from a previous quarter (or a previous edition of the book,) you can just stick with it. (I will not assign homework problems from the textbook, so difference in problem selection and numbering are not important.) It is important that you do have a textbook, and read all the relevant chapters as covered in class. (I will try to give pointers in both books.)
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.
| Day | Time | Room | |
| Lectures | Tuesday, Thursday | 12:30pm-1:50pm | CENTER 119 |
| Discussion | Monday | 10am | PETER 104 |
| Discussion | Monday | 11am | PETER 104 |
| Midterm Exam | Tuesday, April 29 | 12:30pm-1:50pm | CENTER 119 |
| Final Exam | Monday June 9 | 11:30am-2:30pm | CENTER 119 |
| Name | Office Hours | Room | ||
| Instructor | Daniele Micciancio | Friday 9:30am-10:30am | EBU-3b (CSE) 4214 | dmiccian(at)ucsd.edu (*) |
|
TA |
Steve Checkoway | Wednesday 1:00pm-2:00pm | EBU-3b (CSE) B275 | scheckow(at)cs.ucsd.edu |
|
TA |
Will Chang | Thursday 11am-12pm | EBU-3b (CSE) B240A | wychang(at)cs.ucsd.edu |
(*) Important: all course related emails sent to the intructor should include the string CSE105 in the subject line (anywhere, possibly within a more descriptive message). If you do not include CSE105 in the subject, your email risks to be discarded by the spam filtering program. Also, your email messages should be in plain text format and include valid sender and return addresses. Emails with no return address, blank body and the message text included as an html attachment, ms word files, etc. risk also be automatically deleted by the email spam filter programs and are likely to never reach the instructor.
Class members are expected to do all of the following in order to satisfactorily pass this class:
Homework assignments will use JFLAP, a java package for experimenting with automata and formal languages.
Midterm will be scheduled during regular lecture hours, (exact date to be announced soon), 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. Each homework accounts for 8% of the course grade (for a total of 40%), the midterm will contribute another 30%, and the final exam will give the remaining 30%. Both the midterm 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 should have received 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-54 (D), 54-58 (C-), 58-62 (C), 62-66 (C+), 66-70 (B-), 70-75 (B), 75-80 (B+), 80-85 (A-), 85-90 (A), 90-100 (A+).
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 the 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.