Announcements
Jan. 5, 2009. Welcome to CSE 105!
Jan. 28, 2009. The midterm will be Thurs, Feb. 12, 2009 in class. The midterm will be open book and open notes.
Feb. 2, 2009. Homework 3 is posted. Homework 1 will be available to pick up at William's office hours or future Monday sections.
Feb. 4, 2009. Two sample midterms from Fall 2008 are available: [pdf 1] [pdf 2]
Feb. 5, 2009. The midterm this quarter will cover up to and including Sipser 2.2. It will not include the Pumping Lemma for Context-Free Languages.
Mar. 7, 2009. Two sample finals from Fall 2008 are available: [pdf 1] [pdf 2]
Mar. 16, 2009. William will have office hours 10am-noon on Tuesday, 10am-noon on Wednesday, and noon-2pm on Thursday of finals week. OH will be in (or outside of) B240A (the usual place).
Mar. 18, 2009. Prof. Israeli will have office hours today (Wednesday) from 2pm on, and Thursday from 10am-noon. He also has graded homeworks and midterms (but not all homework has been graded yet).
Lectures
Jan. 6, 2009. Corresponding to Sipser 1.1 (Finite Automata): [ppt][pdf]
Jan. 8, 2009. Corresponding to Sipser 1.2 (Nondeterminism): [ppt][pdf]
Jan. 13, 2009. Corresponding to Sipser 1.2 (Nondeterminism), Continued: [ppt][pdf]
Jan. 15, 2009. Corresponding to Sipser 1.3 (Regular Expressions): [ppt][pdf]
Jan. 20, 2009. Corresponding to Sipser 1.4 (Nonregular Languages): [ppt][pdf]
Jan. 22, 2009. Corresponding to Sipser 2.1 (Context-Free Grammars): [ppt][pdf]
Jan. 27, 2009. Corresponding to Sipser 2.2 (Push Down Automata): [ppt][pdf]
Feb. 5, 2009. Corresponding to Sipser 2.3 (Non-Context-Free Languages): [ppt][pdf]
Feb. 10, 2009. Corresponding to Sipser 3.1 (Turing Machines): [ppt][pdf]
Feb. 17, 2009. Corresponding to Sipser 3.2 (Variants of TMs): [ppt][pdf]
Feb. 19, 2009. Corresponding to Sipser 4.1 (Decidable Languages): [ppt][pdf]
Feb. 24, 2009. Corresponding to Sipser 4.2 (Diagonalization): [ppt][pdf]
Feb. 26, 2009. Corresponding to Sipser 4.2 (The Halting Problem): [ppt][pdf]
Mar. 3, 2009. Corresponding to Sipser 5.1 (Reductions): [ppt][pdf]
Homeworks
Homework 1. Due January 15 [pdf] Solution: [pdf]
Homework 2. Due January 29 [pdf] [data.txt for problem 1] Solution: [pdf]
Homework 3. Due February 12 [pdf] Solution: [pdf]
Homework 4. Due February 26 [pdf] Typo corrected in hw4.pdf: Mail your binary writer to wgmatthews (a) cs.ucsd.edu. Solution: [pdf]
Homework 5. Due March 12 [pdf] Solution: [pdf]
Academic Honesty
Students are allowed to discuss homework problems amongst themselves, but each student must hand in his or her own solution and should not directly copy the work of another student. No collaboration is allowed on exams. Additionally, you should not use any external resource to aid you in completing the homework. For example, it is unacceptable to search for homework answers on Google. If, in the course of studying, you happen to see some material that aids you in solving a homework problem, you should clearly acknowledge the source and how you benefitted from it on your homework. Any student caught cheating on the homeworks or exams will be punished in accordance with the UCSD Politcy on Integrity of Scholarship. Specifically, such students will be given a failing grade for the class and will be reported to the Dean of their college.