CS 136 Tutorials - Spring 2007

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.

Simple Set ADT

ADT Description

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₁,s₂,..., s_n}. There are two operations on Simple Sets, as follows:

• The member operation has two arguments: a number x and a Simple Set S = {s₁,s₂,..., s_n}, with precondition "true". The postcondition is "true", and the value "true" is returned if and only if x is an element in the set S.
• The insert operation has two arguments: a number x and a Simple Set S = {s₁,s₂,..., s_n}, with precondition that x is not in S. The postcondition is that x is in S, and no value is returned.

ADT Implementation

An implementation of the Simple Set ADT using an unordered list of numbers is given as class ss-list% in the skeleton code for today's tutorial.

Inspect the implementation of ss-list%, and then write a new class ss-vect% which also implements the Simple Set ADT, but by using a sorted vector of numbers.

Efficiency Analysis

Informal efficiency analysis

Estimate the Big-O runtime of the two methods of the Simple Set ADT for the two implementations ss-list% and ss-vect%. You don't need to give proofs, but you should be able to justify your answers.

safe-insert

Suppose we add another operation to the Simple Set ADT called safe-insert, 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 (safe-insert! ele)
  (cond [(not (member? ele))
         (insert! ele)]))

Assuming your informal analyses above are correct, analyze this procedure if it were implemented in either the ss-list% or ss-vect% class.

Formal analysis

The following procedure consumes a list of numbers and returns true iff that list contains the same number twice:

(define (contains-duplicate? 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))
                    (contains-duplicate? (rest lst)))])))

Let T(n) be the maximum number of substitution steps required to evaluate (contains-duplicate? lst) if lst has length n. Write a recurrence relation for T(n).

Proofs

Solving a recurrence

Use induction to prove an explicit formula for the function T(n) above.

Proving f(n) is O(g(n))

Use your explicit formula to prove that T(n) is O(n²).

Proving f(n) is not O(g(n))

Prove that T(n) is not O(n(log n)²).