Welcome to CSE 105! All class members are asked to read the information on this webpage and check it frequently for updates.
Section ID Number: 503693
Henceforth, announcements will be posted on the discussion board only. [Posted on July 9, 2004 at 1:06 PM]
This course introduces the basic, formal ideas underlying the notion of computation: finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, computability, decidability, undecidability, the halting problem, and reducibility. In studying these objects and concepts, we aim to determine what can and cannot be computed, and on which type of computational model. The course stresses the understanding of the basic concepts and constructions.
This material is essential to being a computer scientist or computer engineer. The course provides tools to understand some fundamental properties of hardware and software. We will be studying basic theoretical problems that have importance in practice and direct application to fields such as Programming Languages, Compilers, Artificial Intelligence, VLSI CAD, Computer Graphics, and Cryptography! (Adriana's research area).
The course involves mathematical abstraction and proofs. One of the most important components is learning to deal with these. This will promote the development of abilities that are extremely valuable to professionals in any area of Computer Science and Computer Engineering: the ability to think in an organized fashion, solve problems, know when a problem cannot be solved, know when you have not solved a problem, and express yourself clearly and precisely.
Do not let the formal nature of the material daunt you. Programming is formal too. You just need to learn the "rules" of the formal systems we will study, just like you learn the "rules" of Java or C.
|The general goals of this course are the following.|
|Upon completion of the course, the student should have the ability to perform the following tasks.|
and any of the following:
More specifically, prerequisite topics include discrete mathematics: exposure to relations, set notation and graphs; programming in some standard imperative language; elementary logic and predicate calculus, boolean functions and truth tables.
Note: Credit not offered for both Math 166 and CSE 105. Equivalent to Math 166.
Dates: June 28 - July 31, 2004
Lecture: M, Tu, W, Th, 11:00 AM - 12:20 PM in Peterson Hall 110. See map.
Discussion section: M, Th, 2:00 PM - 3:20 PM in Peterson Hall 110
|POSITION||NAME||EMAIL (*)||OFFICE HOURS - subject to change|
|Instructor||Adriana Palacioemail@example.com||Tu, W, 2:00 PM - 3:00 PM in AP&M 3349A|
|TA||Ragesh Jaiswalfirstname.lastname@example.org||Th, 4:00 PM - 5:00 PM in EBU1 6307A|
|TA||Vadim Lyubashevskyemail@example.com||M, 1:00 PM - 2:00 PM in EBU1 6307A  |
|TA||Saurabh Panjwanifirstname.lastname@example.org||F, 2:00 PM - 3:00 PM in EBU1 6307A|
(*) Please include "cse105" in the subject line of your message.
Make use of the discussion sections and staff office hours to ask questions about course material. For matters of a personal nature, students may email the staff directly. Avoid using email for technical questions. Instead, use the Web-based discussion board, so that all students can benefit from the staff's responses.
This excellent book is available at the UCSD campus bookstore (new: $102.35, used: $76.80) and elsewhere. You may want to use addall.com to compare online prices. It is also on reserve in the UCSD Science & Engineering Library.
For more information about grading policies and appeal procedures, see the Course Policies.
|Problems:||PS 1: pdf, ps||PS 2: pdf, ps||PS 3: pdf, ps|
|Solutions:||SS 1: pdf, ps||SS 2: pdf, ps||SS 3: pdf, ps|
These problem set solutions and the exam solutions available below tell you not only how to solve the problems, but also how to formulate your answers. You are encouraged to read the solution to a problem, even if you know how to solve it or you got it right on an exam, because this will help you improve your writing skills.
The two tests will take place in the lecture room during regular lecture hours on the dates specified in the course schedule. The topics covered on each of these tests will be announced in class and on this webpage. The final examination will take place on the date specified in the course schedule. It will be inclusive of all course material. All exams are closed book and notes. Calculators may not be used. For each exam, all needed paper will be provided with the exam itself. Please bring a photo ID to every exam.
Make-up exams will not be offered. The only acceptable reason to miss a test is that the student has a certified health problem at the time. For a student with such a medical excuse, arrangements will be made to shift the weight of the test to the final examination. A student who misses the final exam, will obtain a zero (0) on it. If there is any foreseeable reason for which you cannot take the final examination at the scheduled time, then please do not take the course.
If a student is approved as having legitimately missed a test, then a score for that test will be computed as a function of 1) the score the student obtained on the final examination, 2) the statistical parameters of the test, and 3) the statistical parameters of the final examination. This function is complex and cannot be detailed in advance.
|Test 1||Test 2||Final Examination|
The following schedule is subject to change depending upon the progress of the class. All readings are from the textbook.
|June 28||Course overview Solutions to class problems||Chapter 0: prerequisite material|
|June 29||Finite automata (DFAs), Regular languages Lecture 2 notes||Chapter 1: 1.1 except last subsection|
|June 30||Nondeterministic finite automata (NFAs), Equivalence of DFAs and NFAs Lecture 3 notes||Chapter 1: 1.2 except last subsection|
Regular operations, closure properties of the class of
Regular expressions Lecture 4 notes
Chapter 1: last subsections of 1.1 and 1.2
Chapter 1: 1.3
|July 02||Last day for 1) Late Add with $100 fee, 2) (100%) refund|
|July 06||Equivalence of regular expressions and finite automata, Nonregular languages Lecture 5 notes||Chapter 1: 1.3 and 1.4|
|July 07||Pumping lemma for regular languages, Proving a language nonregular||Chapter 1: 1.4|
|July 08||Pumping lemma for regular languages, Proving a language nonregular||Chapter 1: 1.4|
|July 09||MAKE-UP LECTURE: Pushdown automata (PDAs)||Chapter 2: 2.2 except last subsection|
Test 1: 11:00 AM - 12:20 PM,
Peterson Hall 110
The test covers all the material corresponding to the first 8 lectures.
|Last day to 1) change grading option, 2) drop w/o a 'W'|
|July 13||Context-free grammars (CFGs), parse trees, Context-free languages (CFLs)||
Chapter 2: 2.1 except last subsection
|July 14||Equivalence of PDAs and CFGs||Chapter 2: last subsection of 2.2|
|July 15||Closure properties of CFLs, Non-context-free languages, pumping lemma for CFLs||Chapter 2: 2.3|
|July 19||Turing machines (TMs), Recognizable languages, Decidable languages||Chapter 3: 3.1|
|July 20||TM Variants, equivalence, the definition of algorithm||Chapter 3: 3.2 and 3.3|
|July 21||Closure properties of recognizable languages and decidable languages, Decidable problems||Chapter 3: 3.2 and 3.3, Chapter 4: 4.1|
|July 22||Decidable problems Lecture 15 notes||Chapter 4: 4.1|
Test 2: 11:00 AM - 12:20 PM,
Peterson Hall 110
The test covers all the material corresponding to lectures between July 13 and July 22.
|July 27||Undecidability, the halting problem||Chapter 4: 4.2|
|Last day to drop with a 'W'|
|July 28||Undecidability, the halting problem||Chapter 4: 4.2|
|July 29||Proving a language undecidable, Reducibility||Chapter 5: 5.1|
|July 31||Final examination: 11:30 AM - 2:30 PM, Location TBA|
Notes for section - July 19, 2004. Ragesh Jaiswal
Notes on Chapter 2 - July 19, 2004. Ragesh Jaiswal
Online Turing Machine simulator
Final review notes - July 30, 2004. Danny Rubio
Approximately 20 hours per week -- 6 hours of lecture,
2 hours of discussion section, and 12 hours of outside
This course is fast-paced and cumulative. It is imperative for the student not to fall behind.