PROJECTS. After a few lectures, you will be given a list of projects to choose from (or you may be smart enough to propose something on your own). These projects will include mainly theory; you'll have to read, analyze and discuss some theoretical paper, and ideally come out with some new ideas (don't be afraid; Nobel prize is desirable for an A, but not necessary).
1. Knowledge and Comprehension
a. Describe the practical need for theory of computing: to know which computational problems are solvable and which are not, and which problems can be, in principle, solved within given computation time, to avoid wasting resources on trying to solve problems in such a general context that they become unsolvable
b. Describe different models of computing, including recursive functions, different versions of Turing machine, etc.
c. Describe how computability in a programming language is related to formal models of computing, on the example of primitive recursive and recursive functions
d. Understand Church-Turing thesis and understand the status of this thesis - that it is, in effect, a statement about the physical world
e. Define decidable and recursively enumerable (r.e., semi-decidable) sets
f. Understand the notion of an oracle and of computing relative to an oracle
g. Define classes P, NP, the notions of polynomial time reduction, NP-hardness, and NP-completeness; understand the motivations behind these definitions: P means feasible, NP stands for a problem; understand the difference between the formal notion of polynomial time and the practical notion of feasibility
i. Understand the difference between a proof and a sequence of reasonable arguments which does not constitute a proof
j. Know several NP-hard problems
k. Define complexity classes from the absolute and relative polynomial hierarchy; give examples of problems
l. Understand the main idea of parallelization
m. Define the class NC of parallelizable P problems, know the relation between NC and P, and an example of a P-complete problem
n. Understand the difference between the formal computation time of a parallel program and the actual time which takes communication time into account
o. Define Kolmogorov complexity, understand motivations behind this definition
p. Be aware of the main ideas behind different physical schemes of computing beyond traditional Turing machines, such as quantum computing
2. Application and Analysis
a. Trace the computation of a primitive recursive or recursive function on a numerical example
b. Translate a formal description of a primitive recursive or recursive function into a program
c. Trace a Turing machine on a given input
d. Prove that satisfiability is NP-hard, and that one more problem is NP-hard
e. Know how to parallelize standard simple parallelizable algorithms (e.g., search, or dot product of two vectors)
f. Use the definition of Kolmogorov complexity K(x) to provide reasonable upper bounds for K(x) of a given string x
3. Synthesis and Evaluation
a. Prove, from the definition, that a given function (e.g., a given polynomial or propositional function) is primitive recursive or recursive
b. Design a Turing machine that computes a given function
c. Synthesize Turing machines that compute two functions into a Turing machine for computing their composition
d. Prove that not every problem is computable - e.g., that the halting problem is undecidable
e. Apply diagonalization to prove results similar to what we had in class
f. Prove that given simple sets are decidable and/or r.e.
g. Prove that the union, intersection, and complement of decidable sets are decidable
h. Prove that the union and intersection of r.e. sets is r.e.; prove that the complement to a r.e. set is not always r.e.
i. Prove that not every r.e. set is decidable and that not every set is r.e.
j. Prove, for a given software requirement, it is algorithmically impossible to check whether a given program satisfies this requirement
k. For problems similar to ones considered in class, prove their NP-hardness
l. Be able to parallelize simple algorithms
m. Be able to understand and present a research paper in Theory of Computing - with a minor help from a professor
MAIN SOURCE: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 2nd edition
TESTS AND GRADES: There will be two tests and one final exam. Each topic means home assignments (mainly on the sheets of paper, but some on the real computer). Some of them may be graded. Maximum number of points:
A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:
STANDARDS OF CONDUCT: Students are expected to conduct themselves in a professional and courteous manner, as prescribed by the Standards of Conduct. Students may discuss programming exercises in a general way with other students, but the solutions must be done independently. Similarly, groups may discuss project assignments with other groups, but the solutions must be done by the group itself. Graded work should be unmistakably your own. You may not transcribe or copy a solution taken from another person, book, or other source, e.g., a web page). Professors are required to - and will - report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students.
DISABILITIES: If you feel you may have a disability that requires accommodation, contact the Disabled Student Services Office at 747-5148, go to Room 106 E. Union, or e-mail to firstname.lastname@example.org.