University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Notes: Monday 19 April 2004
Schedule

Permute Sort
(define (flat-one lst)
  (if (null? lst) lst (append (car lst) (flat-one (cdr lst)))))

(define (all-permutations lst)
  (flat-one
   (map
    (lambda (n)
      (if (= (length lst) 1)
          (list lst) ;; Only one permutation of 1-length list
          (map 
           (lambda (oneperm) (cons (nth lst n) oneperm))
           (all-permutations (exceptnth lst n)))))
    (intsto (length lst)))))

(define (is-sorted? cf lst)
  (or (null? lst) (= 1 (length lst)) 
      (and (cf (car lst) (cadr lst))
           (is-sorted? cf (cdr lst)))))

(define (permute-sort cf lst)
  (car 
   (filter (lambda (lst) (is-sorted? cf lst)) 
           (all-permutations lst))))
Notes

How much work is permute-sort?



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.

cs200-staff@cs.virginia.edu
Using these Materials