University of Virginia Computer Science
CS150: Computer Science, Fall 2005

(none)
21 September 2005

CS150 Notes 13
(21 September 2005)
Upcoming Assignments
 Monday, 26 September: PS4
 Wednesday, 28 September (7pm, location to be announced): The
Assistant Coaches will conduct a review session for Exam 1
 Wednesday, 5 October: Exam 1 (out September 30)
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 wellprepared 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 "antiwisdom" 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 (permutesort cf lst)
(car
(filter (lambda (lst) (issorted? cf lst))
(allpermutations lst))))
(define (issorted? cf lst)
(or (null? lst) (= 1 (length lst))
(and (cf (car lst) (cadr lst))
(issorted? cf (cdr lst)))))
(define (allpermutations lst)
(flatone
(map
(lambda (n)
(if (= (length lst) 1)
(list lst) ; The permutations of (a) are ((a)) (map
(lambda (oneperm)
(cons (nth lst n) oneperm))
(allpermutations (exceptnth lst n)))))
(intsto (length lst)))))
What is the time complexity of permutesort?
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 ("");
?>