No one showed up. All you get are my preliminary notes.

Overview

• About the final
• Sample final problems
• Other questions

About the final

• In class.
• Thursday, 9-noon (alternate: Wednesday, 2-5pm.)
• Somewhat like a big quiz (no computers).
• Four questions.
• Typical forms of questions
  • Write code
  • Read code and give sample output
  • Analyze efficiency
• Cumulative, but likely to focus more on end-of-semester issues.
• Simple grading scheme.
  • Four right or mostly right: A
  • Three right or mostly right: B
  • Two right or mostly right: C
  • One right or mostly right: D
  • Zero right or mostly right: F
• You may bring one sheet of notes.
  (8.5"x11" or A4, double sided, hand-written).

Problem 1: Is it sorted?

Key idea: Use vector recursion.

(define vector-proc
  (lambda (vec)
    (let kernel ([pos 0])
      (cond
        [(= pos (vector-length vec)) ; Or something similar
         base-value]
        [(another-test)
         base-value]
        [else
         (kernel (+ pos 1))]))))

We are returning a Boolean.

What should our base values be?

Problem 2: Whatzitdo?

We've seen something similar on an exam (or at least I think we have).

Problem 3: Is it efficient?

We know that append requires 1 call to cons for each value in the first list.

So, to reverse a list of length n using list-reverse-1 ...

• append n-1 elements and build a list of 1 element: n calls to cons
• append n-2 elements and build a list of 1 element: n-1 calls to cons
• ...
• apppend 1 element and build a list of 1 element: 2 calls to cons
• append 0 elements and build a list of 1 element: 1 call to cons

So 1+2+3+...+n, which we now know is n(n+1)/2.

Alternately, you could work out the steps by hand.

Problem 4: Nesting

Other Questions

There were none.