Computer Science and Engineering 105
Introduction to the Theory of Computation
Summer 2003
Revised July 29, 2003.
- Instructor:
- Dr. Larmore
- Office, AP&M 4018. Telephone, 534-4652, llarmore@cs.ucsd.edu
- Office Hours:
- Mondays, 11:00 - 12:00, Tuesdays 1:00 - 2:00
- Contacting Me:
- It's best to send me email at llarmore@cs.ucsd.edu. Be
sure to write "CSE105" in the subject field so that
I know what the message is
about. (I delete lots of messages without reading them, based on the subject
fields.)
- While in San Diego, I cannot read email once I leave the campus, which
will be early in the afternoon. So, if you have a question that needs to
be answered by morning, it's best to cc the email to one of the teaching
assistants.
- You may also telephone my office, but please do not leave voicemail,
as I do not (yet) have the ability to retrieve it.
- Please, never try to communicate with me by leaving
notes
on my door, under my door, or in my mailbox in the department office,
as those notes get lost, and I can't retrieve them remotely.
- Graduate Assistants:
- Bogdan Warinschi.
Office hours: Mondays 2-3, Fridays 10:30-11:30, AP&M 3337A.
Bogdan Warinschi is holding special office hours Tuesday July 29,
4:00-5:00, AP&M 3337A
- Wenjing Rao.
Office hours: Mondays 3-4, Wednesdays 2-3, AP&M 3337D.
- Days of Instruction:
- June 30, 2003 - July 31, 2003.
- Time of Instruction:
- 8:00 - 9:20, Monday, Tuesday, Wednesday, and Thursday.
- Discussion Sessions:
- 2:00 - 3:00 Tuesdays CENTR 212
- 8:00 - 9:00 Fridays CENTR 214
- Place of Instruction:
- CENTR 119.
- Final Examination:
-
July 30, 8:00 AM, and July 31, 8:00 AM. Note change!
Textbook:
Introduction to the
Theory of Computation, by Michael Sipser. PWS. ISBN 0-534-95651-3.
Prerequisites:
CSE 12 (Basic Data Structures and Object-Oriented Programming)
One of the following courses: MATH 103A, MATH 100A, CSE 21, MATH 15B.
Click here
if you did not take both prerequisites at UCSD.
Written Homework:
will be assigned, collected, and graded. You are permitted to discuss
homework with others.
Examinations:
Midterm examination will be July 17.
Final examination will be July 31.
Final Grade:
15 % Homework
35 % Mid-term Examination
50 % Final Examination
This course is arguably the
most interesting in the Computer Science core curriculum.
During this Semester,
you will learn the accurate meanings of a number of
terms that you have probably heard. In some cases,
you will have to unlearn
what you previously believed! For example, you will learn the following
concepts:
- Automaton.
- Language.
(You may have thought you knew this one!)
- Grammar. (You probably thought you knew this one, too!)
- Turing Machine.
- Universal Turing Machine. The machine that can do anything that any
machine in this or any other universe could possibly do. But, rather slowly!
- NP-complete. Almost everyone in computer science has heard this term, but
few can give a precise definition.
- Undecidability. There are problems that are undecidable. There are
propositions that are true but for which there is no proof. I don't mean no
one has found a proof yet, I mean that no proof can exist at all! There are
problems, such as the halting problem, which cannot be solved by any
algorithm. No future genius, with a finite intellect, will ever find one, not
in this (or any other) universe, ever.
- Computable.
There are functions which cannot be implemented by any machine
that could ever be built.
- "But they told the Wright brothers that a flying machine was
impossible."
- P = NP? The most famous open question in all of computer science. What
does this mean? What does it mean in practical terms?
Detailed
description of the CYK algorithm.
Homework
and tests
from prior semesters are available.