UNIVERSITY OF CALIFORNIA, SAN DIEGO
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING


CSE 105 - Theory of Computability

2004 Summer Session I


[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


ANNOUNCEMENTS

Henceforth, announcements will be posted on the discussion board only. [Posted on July 9, 2004 at 1:06 PM]


COURSE DESCRIPTION

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. 


Objectives:

The general goals of this course are the following. 
  • The development of an understanding of the fundamental principles, concepts and results of Computability Theory. 
  • The development or strengthening of problem solving skills. 
  • The development or strengthening of the ability to write clearly and precisely. 
  • The appreciation of the relevance of Computability Theory to other areas of Computer Science and Engineering. 
  • The development of a more positive attitude toward theory and mathematics. 
Upon completion of the course, the student should have the ability to perform the following tasks. 
  • List and define the major terms and concepts in Computability Theory. 
  • Demonstrate familiarity with the main theorems and results, and prove (or at least outline proofs of) the most basic and important theorems. 
  • Apply the definitions and basic results to a new situation, extending definitions and results appropriately. 
  • Prove (for example):
    • A language regular or context free by construction and/or by closure properties of the language class. 
    • A language non-regular or non-context-free by the corresponding pumping lemma and/or by closure properties of the language class. 
    • A language decidable by construction, by closure properties of the class of decidable languages, and/or by reduction to a decidable language. 
    • A language undecidable by reduction from an undecidable language. 
    • Closure properties of a language class. 
  • Determine whether a proof is correct and, if it is not, then pinpoint the fallacy. 
  • Describe the application of a concept from the course to some nontheoretical area of Computer Science or Computer Engineering. 

Prerequisites:

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. 


MEETINGS

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


STAFF

 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 Web-based discussion board, so that all students can benefit from the staff's responses.


TEXTBOOK

"Introduction to the Theory of Computation" by Michael Sipser, PWS Publishing Company, 1997.  The website includes errata. 
ISBN: 0-534-94728-X. 
The relevant chapters are 0, 1, 2, 3, 4, 5, 7, but not everything in these chapters will be covered. 

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. 


FORMAT

The course is organized into
  • Lectures  given by the instructor
  • Discussion sections  lead by the TAs to reinforce concepts discussed during lecture and answer questions about the lecture, reading assignments, problem sets, and exams.  The two discussion sections that take place each week will always involve different topics or different problems, so students are encouraged to attend both. 
  • Office hours  offered by the instructor and the TAs to answer questions about the lecture, reading assignments, problem sets, and exams
  • Web-based discussion board  for questions and comments concerning the course that could be of interest to multiple students
  • Reading assignments  from the textbook.  The readings provide preparation and a reference for the lectures.  They are required in the sense that the material in the readings is covered on the exams. 
  • Problem sets (ungraded)  based on the lectures and reading assignments.  There are approximately three problem sets.  These are not to be turned in, but students are strongly encouraged to solve them because this is an excellent way to test your understanding and problem solving abilities, and to prepare for the exams.  Solutions will be posted. 
  • Exams  for evaluation of progress.  There are two tests and a final examination.  Exams cover the material presented by the staff in lecture and the discussion board, and the material in reading assignments and problem sets.  Solutions will be posted. 

Your grade for the course will be based on your performance on the exams and your class participation as follows: 
  • Test 1: 30%
  • Test 2: 30%
  • Final examination: 40%
  • Participation in the lectures, discussion sections and discussion board will have an impact in the margins (i.e., borders between grades) -- it pays to let the instructor and TAs know who you are!

For more information about grading policies and appeal procedures, see the Course Policies. 


PROBLEM SETS

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. 


EXAMS

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


TENTATIVE SCHEDULE

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 MAKE-UP 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 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 
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  


OTHER RESOURCES

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


WORK LOAD

Approximately 20 hours per week -- 6 hours of lecture, 2 hours of discussion section, and 12 hours of outside preparation. 
This course is fast-paced and cumulative.  It is imperative for the student not to fall behind. 

Most recently updated on July 20, 2004 by Adriana Palacio.