CSE 725 - Computability and Unsolvability

Winter 2011

Thought provoking links:

http://en.wikipedia.org/wiki/Hilbert's_tenth_problem
http://rjlipton.wordpress.com/2010/01/20/are-the-reals-really-uncountable/
http://en.wikipedia.org/wiki/Busy_beaver

Textbook:

Introduction to the Theory of Computation, second edition. M. Sipser.

Recommended reading:

Computational Complexity. C. Papadimitriou.
Computational Complexity: A Modern Approach. Sanjeev Arora and Boaz Barak (free draft available).

Syllabus:

PDF

Office hours:

By instructor: Tue 2:30-3:30pm or by appointment.
By grader, Tantan Liu (liut [at] cse.ohio-state.edu): MW 12:00-1:00pm in DL 778.

Problem Sets:

PS1 (due lecture on February 2nd). Solutions.
PS2 (due lecture on February 23rd). Solutions.
PS3 (due lecture on March 9th). Solutions.

Topics by lecture (tentative):

friendster
analytics