CS200: Computer Science, Spring 2004

Notes: Monday 19 April 2004
Schedule
 Now: Exam 2
 1421 April (scheduled by teams): PS8 Design Reviews (make sure all your teammates show up at my office at the appointed time)
 Monday, 26 April (last day of class): PS8
 Friday, 30 April, 4:55pm: Final Exam (handed out 26 April)
Permute Sort (define (flatone lst) (if (null? lst) lst (append (car lst) (flatone (cdr lst))))) (define (allpermutations lst) (flatone (map (lambda (n) (if (= (length lst) 1) (list lst) ;; Only one permutation of 1length list (map (lambda (oneperm) (cons (nth lst n) oneperm)) (allpermutations (exceptnth lst n))))) (intsto (length lst))))) (define (issorted? cf lst) (or (null? lst) (= 1 (length lst)) (and (cf (car lst) (cadr lst)) (issorted? cf (cdr lst))))) (define (permutesort cf lst) (car (filter (lambda (lst) (issorted? cf lst)) (allpermutations lst))))Notes How much work is permutesort?
What is a problem?
Could you build a nondeterministic finite state machine?
Is a nondeterministic finite state machine more powerful than a finite state machine?
Could you build a nondeterministic Turing machine?
Is a nondeterministic Turing Machine more powerful than a deterministic (regular) Turing Machine?
Is a nondeterministic Turing Machine faster than a deterministic (regular) Turing Machine?
What does it mean to say a problem is in complexity class P?
What does it mean to say a problem is in complexity class NP?
Are all problems in P also in NP?
Are all problems in NP also in P?
Note: this is the Millennium Prize Problem: The P versus NP Problem. Clay Mathematics Institute will give you $1M if you answer it, so you may need to use the margins to answer it.
cs200staff@cs.virginia.edu Using these Materials 