Tutorial 7: Midterm Review (June 15)The main purpose of today's tutorial is to help prepare you for the midterm exam next week. However, do not assume that the topics covered here are exactly those on the exam. For more information on the exam, see the exams page.
Make sure you understand all the components of the following description of the Simple Set abstract data type (ADT): A Simple Set is a (possibly empty) set of numbers {s_{1},s_{2},..., s_{n}}. There are two operations on Simple Sets, as follows: An implementation of the Simple Set ADT using an unordered list of
numbers is given as class Inspect the implementation of Estimate the BigO runtime of the two methods of the Simple Set ADT for
the two implementations Suppose we add another operation to the Simple Set ADT called safeinsert, which is exactly the same as the insert operation, except that it has precondition "true". This could be written in either of the two implementation as: (define/public (safeinsert! ele) (cond [(not (member? ele)) (insert! ele)])) Assuming your informal analyses above are correct, analyze this procedure
if it were implemented in either the The following procedure consumes a list of numbers and returns true iff that list contains the same number twice: (define (containsduplicate? lst) (local ((define (contains? lst num) (cond [(empty? lst) false] [(= (first lst) num) true] [else (contains? (rest lst) num)]))) (cond [(empty? lst) false] [else (or (contains? (rest lst) (first lst)) (containsduplicate? (rest lst)))]))) Let T(n) be the maximum number of
substitution steps required to evaluate
Use induction to prove an explicit formula for the function T(n) above. Use your explicit formula to prove that T(n) is O(n^{2}). Prove that T(n) is not O(n(log n)^{2}). 

Last modified on Friday, 19 August 2011, at 18:05 hours.