CS200: Computer Science, Spring 2004
Notes: Monday 19 April 2004
- Now: Exam 2
- 14-21 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 (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.
Using these Materials