[Announcements]
[Course Description]
[Meetings]
[Staff]
[Textbook]
[Format]
[Course Policies]
[Work Load]
[Reading Assignments]
[Discussion Board]
[Problem Sets]
[Exams]
[Schedule]
[Other Resources]
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, contextfree 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. 

CSE 12
and any of the following:
CSE 21,
Math 15B,
Math 100A,
or
Math 103A.
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 Palacio  apalacio@cs.ucsd.edu  Tu, W, 2:00 PM  3:00 PM in AP&M 3349A 
TA  Ragesh Jaiswal  rjaiswal@cs.ucsd.edu  Th, 4:00 PM  5:00 PM in EBU1 6307A 
TA  Vadim Lyubashevsky  vlyubash@cs.ucsd.edu  M, 1:00 PM  2:00 PM in EBU1 6307A 
TA  Saurabh Panjwani  spanjwan@cs.ucsd.edu  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 Webbased 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.
Makeup 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.
DATE  LECTURE  READING ASSIGNMENT 

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 
July 01 
Regular operations, closure properties of the class of
regular languages, 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 05  HOLIDAY  
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  MAKEUP LECTURE: Pushdown automata (PDAs)  Chapter 2: 2.2 except last subsection 
July 12 
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  Contextfree grammars (CFGs), parse trees, Contextfree 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, Noncontextfree 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 
July 26 
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
preparation.
This course is fastpaced and cumulative. It is imperative for
the student not to fall behind.