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
- The
**member**operation has two arguments: a number`x`and a Simple Set`S`= {`s`_{1},`s`_{2},...,`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`_{1},`s`_{2},...,`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
- Efficiency Analysis
- Informal efficiency analysis
- safe-insert
- Formal analysis
- Proofs
- Solving a recurrence
- Proving
`f`(`n`) is O(`g`(`n`)) - Proving
`f`(`n`) is*not*O(`g`(`n`))

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 `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.

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.

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.

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`).

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.