CSE 6321 - Computability and Complexity

Spring 2015

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

Announcements:

Notes on the complexity of optimization problems.

Textbook:

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

Syllabus:

PDF

Office hours:

By grader: Yu Wang (wang.5205@buckeyemail.osu.edu), Mon 10:20--11:20am in Dreese Labs 686.
By instructor, Dreese Labs 495, Wed 2-3pm or by appointment.

Problem Sets:

PS1 (due beginning of lecture on January 26th). Solutions.
PS2 (due beginning of lecture on February 2nd). Solutions.
PS3 (due beginning of lecture on February 23rd). Solutions.
PS4 (due beginning of lecture on March 2nd). Solutions.
PS5 (due beginning of lecture on March 9th). Solutions.
PS6 (due beginning of lecture on April 10th). Solutions.
PS7 (due beginning of lecture on April 20th). Solutions.
PS8 (due beginning of lecture on April 27th). Solutions.

Topics by lecture (tentative).