CS172: Computability and Complexity

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS172: Computability and Complexity

CS172. Computability and Complexity

This course is about the part of theoretical computer science that studies the limits of what can be done with computing machines.

The course is divided into three parts, corresponding three ways of modeling computations. In the first part we consider the model of finite state automata. This is a very simple model, and it captures only a small set of algorithms. Its advantage is that it captures algorithms used in parsing and string matching and it is simple enough that we can understand it inside out. In the second part we see how all conceivable discrete computing devices can be simulated by Turing machines, a conceptually simple abstract device, and we consider the model of Turing machines that always solve the given problem, even though they can take arbitrary time. This is too powerful a model, in the sense that there are problems which are intractable in any practical sense but that can be solved in such a model. Its generality makes it easier to study, and in fact a lot is known about this model too. Finally, we come to the study of polynomial time computations, a sensible model of the computations that can actually be realized in practice. Being the most realistic, this is also the most messy field of study, and our ignorance far outweighs our understanding here. (And million dollar price awaits the solver of the main open question in this field.) Meanwhile, complexity theorist have already proved several very beautiful, and sometimes unexpected, results in the past thirty-five years, and we will see a few of them.

Grading

The grade is determined by

Weekly homeworks, 45%
Two midterms, 15% each
Final exam, 25 %

Prerequisite

CS170 is a prerequisite for this course.

Homeworks

Homeworks are due in class. Late homeworks will not be accepted. The three lowest homework grades will be dropped when computing the grade average. Make sure you write your name on all the pages of your solution.

Cheating

We encourage you to help each other learn the material by discussing the work before you do each assignment. For most assignments, explaining the meaning of a question or a way of approaching a solution is an interaction that we encourage. On the other hand, you should never read another student's solution or partial solution, nor have it in your possession, either electronically or on paper. You should write your homework strictly by yourself. For some problems, we may instruct you not to discuss the problem with other students at all. If you receive a significant idea from someone in the class, explicitly acknowledge that person in your solution. Not only is this a good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.

Presenting another person's work as your own constitutes cheating, whether that person is a friend, a student in this class or a previous semester's class, or an anonymous person on the Web who happens to have solved the problem you've been asked to solve. Everything you turn in must be your own doing, and it is your responsibility to make it clear to the graders that it really is your own work. The following activities are specifically forbidden in all graded course work:

Possession (or theft) of another student's solution or partial solution in any form (electronic, handwritten, or printed).
Giving a solution or partial solution to another student, even with the explicit understanding that it will not be copied.
Working together to develop a single solution and then turning in copies (or modified versions) of that solution under multiple names.

Cheating on an homework or a midterm will result in a grade of zero for that assignment. Cheating on the final, or repeated offenses, will be reported to the Office of Student Conduct and will probably result in an F.