University of Virginia Computer Science
CS150: Computer Science, Fall 2005
 (none)
21 September 2005

CS150 Notes 13 (21 September 2005)

Upcoming Assignments

Exam 1
Exam 1 will be handed out Friday, 30 September and due Wednesday, 5 October (note that there is no class on Monday, 3 October). There will not be a time limit, but for a well-prepared student it should only take a couple hours. It will be open book and open notes, but you will not be permitted to use a Scheme interpreter.

Exam 1s from previous CS200 courses are available here:

Your Exam 1 will be quite similar in format and content (but of course, the questions will be different!). The content we have covered for Exam 1 is most similar to that from the Spring 2003 exam, which is attached. You are strongly encouraged to try going through these questions yourself, and then discussing them with other students in the class, before looking at the comments to check that your understanding is correct (but do not be too disturbed by the mention of "anti-wisdom" points!). If you can answer all the questions on this exam, you should expect to do well on your exam. (Conversely, if you don't understand much on the sample exam, you should make sure you do understand it before your exam!) If you want more practice problems, try the Spring 2004 exam.

The exam will cover all material in the course through today's class (Class 13). Monday and Wednesday next week we will cover new material that is not included on Exam 1. On Friday next week, I will either answer questions that are sent to me by email before class or talk about how the Bletchley Park cryptographers really broke the Lorenz cipher.

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

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


(define (all-permutations lst)
  (flat-one
   (map
    (lambda (n)
      (if (= (length lst) 1)
          (list lst) ; The permutations of (a) are ((a))  (map 
           (lambda (oneperm)
             (cons (nth lst n) oneperm))
           (all-permutations (exceptnth lst n)))))
    (intsto (length lst)))))
What is the time complexity of permute-sort?




What is a problem?










Why is it easier to establish an upper bound (O) for a problem than a lower bound (Ω)?







"); print ( $res[$first] ) ; print (""); ?>
CS 150: Computer Science
University of Virginia
 evans@virginia.edu
Using these Materials