CSE 105: Introduction to the Theory of Computability
University of California, San Diego
Fall 2004

Main course page

Schedule (includes PDFs of lecture notes)

Lecture Notes (for in-class viewing)

Problem sets

Exams

Webboard
 

Course Information

• Instructor: Dr. Sara Miner More
      Email: more@cs  (Please include 'cse105' somewhere in the subject line of your message)
      Office location: AP&M 4101
      Office hours: M 1-2p, Tu 1-2p, Th 11a-12n, and by appointment
   

• Teaching Assistants:
      Konstantinos (Kostas) Bimpikis
         Office hours: W 3-4:30p and Th 2-3:30p.  Location: EBU-1 6307
      Hyun Min Kang
         Office hours: F 10a-12p.  Location: EBU-1 6307A
      Andrew (Drew) Terry
          Office hours: M 3:30-5p and Tu 2:30-4p. (Note new Tu time effective 10/26.)  Location: EBU-1 6307B  
     
     

• Course Meetings:
      Lectures - Tu Th 9:30-10:50a in Center Hall 214
      Sections - F 2-2:50 in HSS 1330

• Course Description:  An introduction to the mathematical theory of computability.  Formal languages.  Finite automata and regular expressions.  Pushdown automata and context-free languages.  Computable or recursive functions.  Turing machines, the halting problem.  Undecidability.  (4 units)
   
• Course Objectives:  This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages.  The course stresses the understanding of the basic concepts and constructions.  An additional emphasis is the writing of clear, logical arguments in a mathematically rigorous way.
   
• Prerequisites:  (CSE 12 and CSE 21) or Math 15B or Math 100A or consent of instructor. 
  Restrictions: Majors only.  Credit not offered for both Math 166 and CSE 105.
   
• Course schedule:  Please see the schedule web page for a tentative list of topics that will be covered and the assigned readings for each day.  You are expected to read the assigned sections of the text prior to the lecture that will cover it.  Lecture slides and handouts will be posted here as well.  I will attempt to post the lecture slides prior to each lecture.
   
• Practice problems:  Practice problem sets will be posted on the problem sets web page periodically.  You are encouraged to work through the problems as we cover the corresponding material in the text (i.e., don't wait until the day before an exam to begin!), and to write down your solutions in the same manner as you would write them on an exam.  Solutions to each problem set will be posted, and you should always compare your solution to the one provided.  Try to resist the temptation to read the solutions without working the problems first - it is much easier to read someone else's solution and try to understand it than to come up with the solution on your own.
   
• Course discussion board:  Announcements relevant to the course will be posted on the Webboard by course staff.  In addition, students are encouraged to use the board to initiate and participate in discussions about course material.  I prefer that students use the Webboard (rather than individual e-mail) for questions of a general nature, so that everyone in the course can benefit from the resulting discussion.  Each student is expected to check the Webboard frequently and will be responsible for material posted there.  Finally, the Webboard is provided to encourage dialogue between students and course staff on topics relevant to CSE 105 only. The course staff reserves the right to remove postings which are deemed inappropriate for this forum.
  Thu 09/23 - Note: ACS informed me today that the initial Webboard password for students who have OCE logins will be your usual computing password (i.e., the one you use for email).  This is contrary to what I announced in class this morning - your student ID number will not be your password!  If you are auditing the course, or have enrolled via concurrent enrollment, please come by my office or see me after class on Tuesday.  I'll give you a slip which you will need to take to ACS so that an account can be established for you. 
   
• Grading:  Your grade in this course will be based on three midterm exams (worth 20% each), and a final exam (worth 40%).  All exams are closed book, closed notes, and do not require a blue book.  The dates of the exams are listed on the exams web page.  As of the first day of class, the dates listed there are fixed, and there will be no makeups except in the case of documented emergency situations.
  
  Your solutions will be graded not only on correctness, but also on presentation.  An important part of this course is proving statements by writing clear, rigorous mathematical arguments.  It is your responsibility to write solutions which a reader/grader can follow immediately.
  
  Grades in this course will not be assigned on a curve.  Your grade will be based upon your own performance.  If everyone does well, everyone will get an A.  Letter grades will be based roughly on the following percentage scale:  A+ range: 100-96, A range: 95-91, A- range: 90-88, B+ range: 87-85, B range: 84-81, B- range: 80-78, C+ range: 77-75, C range: 74-71, C- range: 70-68, D range: 67-61, D- range: 60-58, F range: below 58.
   
• Academic honesty:  During an exam in this course, a student may not access outside written material or communicate in any way with anyone other than an exam proctor.  A student may not alter a graded exam and then submit it for re-grading.  Each of these actions constitute cheating and are grounds for failing the course (F grade).  By enrolling in this course, you implicitly agree to abide by the complete UCSD Policy on Integrity of Scholarship found in the University's Academic Regulations.  If you have any questions or concerns about academic integrity issues, please see Dr. More.
   
• Noteworthy dates:  
  Last day to drop fall '04 courses without a 'W' or to change grading option: October 22nd.
  Last day to withdraw from a Fall '04 course (you will receive a 'W' grade if after Oct. 22):  November 29th.

UCSD CSE