The purpose of the course is to study the capabilities and limitations of computers by formulating mathematically various models of idealized computers and establishing rigorously for these models what kinds of problems can and cannot be solved at all, as well as what kinds of problems can and cannot be solved with a reasonable amount of computing resources. Important practical application areas for this theory include string searching and pattern matching, programming language design and compilation, and cryptography.
The following is the officially adopted course description:
Models of computation: finite-state machines, stack machines, Turing machines, Church's thesis; Computability theory: halting problem and unsolvability, introductory recursion theory; Complexity theory: complexity measures, time and space hierarchy, NP-complete problems.
I expect to be sticking fairly closely to this basic set of topics, though I might treat some other related topics if time allows.
You are supposed to have taken CSE 303 (Introduction to the Theory of Computation) or the equivalent. If you haven't, you should speak to me before attempting this course.
| Lecture: | Tuesday and Thursday, 12:50PM-2:10PM, Library N4072. |
The official book for the course is the following book, which Prof. Ko has used for the course in the past:
The following other books might also be helpful to you. I might draw on material from some of them.
The subject of this course is mathematical. When new mathematics is created, the researcher starts with a more or less vague mental picture of the of the subject area and tries to clarify that picture by making precise definitions and asking questions about their consequences. Since mathematical results have to be proved beyond any doubt, the results of the investigation are traditionally presented in a very stylized form in which definitions are made completely precise and each result is justified using reasoning that clearly separates assumptions from conclusions and makes transparent the dependency of each new assertion on what has come before. However, one must not lose sight of the fact that the clear mental picture, not the stylized presentation, is the actual outcome of a mathematical investigation.
In studying mathematics that has already been created (which is what most students who take mathematics courses do), one attempts to "learn" the subject from the stylized presentation. It is easy to fall into the trap of thinking that memorizing definitions, theorems, and proofs is what this learning entails. However, this is inadequate. The actual objective should be to reconstruct the underlying clear mental picture, so that the truth or falsity of the various theorems becomes more or less obvious as a result.
In order to "decode" mathematical formalism and reconstruct the underlying mental picture, it is necessary to adopt an approach much like that used when the mathematics was created. As each definition is presented, one should try to understand why the definition is stated the way it is and what are and are not consequences of it. As each theorem is studied, one should try to understand how it and its proof serve to elucidate the properties of the mathematical objects under study. In achieving this understanding, it is often useful to consider possible alternatives to what is written in the text; for example, are there simpler (but possibly less general) versions of the theorem that are also true, are there counterexamples that show the necessity of technical hypotheses, or is a complicated proof actually necessary or would a simpler argument suffice?
To facilitate this kind of active approach to assimilating mathematical material, mathematics books often include "exercises". Typically these explore the kinds of "what if" questions that are helpful in reconstructing the underlying mental picture. They are not really optional -- in most cases, if the answer to an exercise is not obvious, then some important feature of the material has been missed. Sometimes mathematics books also include "problems", which are more difficult and are used to introduce the reader to side topics that are not explored in depth in the main text, or to indicate directions for possible extensions or generalization of the existing material. Since the student cannot always easily distinguish an "exercise" from a "problem", it is helpful if textbooks separate the two, but this is not always done.
What I am trying to say by all this is that doing exercises is an important and necessary part of learning mathematical material, and I expect that you will do as many basic exercises as you can manage. I plan to assign homeworks on a roughly weekly basis, but typically these will consist of questions at a level somewhere between the most basic exercises (which you should do yourself without my assigning them) and more advanced problems (which may be too time-consuming for a one-week time frame). You should do the homeworks and turn in your solutions each week. I will look them over, but will probably just "check off" that you attempted a homework problem, rather than scoring the homeworks in detail. Although the benefit of the homeworks will be derived from the attempt to do them, in order to provide you with some additional motivation a nominal portion of your final grade will be dependent on your homework score.
Each student must submit their own individual homework writeup. If more than one student submits substantially the same writeup for a particular homework problem, or if there is some other evidence that the writeup you submit is not your own work, I will regard this as evidence that you are trying to get a higher grade without actually doing the required work and may choose either to make a corresponding deduction from your homework score or (in egregious cases) to pursue the matter as a case of academic dishonesty. Having said that, I want to make clear that it is OK and encouraged to discuss homework problems with each other, as long as the writeup you submit is your own work. Personally, though, I think it is best not to discuss a problem with others until you have attempted it yourself first, since it is from that individual attempt that you will derive the most benefit.
There will be a midterm exam and a final exam.
| Midterm: | TBA |
| Final: | Thursday, December 20, 11:00AM-1:30PM |
In view of the fact that exams have to be completed in a limited period of time, I expect that exam questions will tend to be closer to "exercises" than to "problems".
The final grade will be determined as follows: The raw scores obtained by students on each homework assignment will be summed, and the result standardized by representing the sum as a percentage of the total points possible for the homework assignments. The raw scores obtained by a student on each exam will be standardized by converting them to percentile scores. A weighted sum of the resulting standardized scores will then be formed (with weights as shown below) to obtain a composite score for each student.
Finally, the composite scores will be ranked, and the instructor will apply a subjective method of his choice to determine the cutoffs for each grade category. Absolute performance standards, the distribution of composite scores, and information derived from late homeworks are factors likely to contribute to this decision.
"If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disability Support Services office (DSS), ECC Building (behind SAC), 632-6748/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential."