Overview

• A bit of info about the quiz (topics, general forms of questions)
• Your questions on recent topics or the exam
• Sample quiz questions

About the Quiz

What's on the quiz?

Searching and sorting. We assume you will know linear search and binary search and the purpose of sorting and the normal parameters and insertion sort. You do not need to know merge sort.

What kinds of questions will you ask?

"Show the steps (or output) when you run this algorithm on this input."

Finish this code for something related to those algorithms.

Document / clean up code.

General Questions

Can you talk about binary search?

Model: Searching in a vector, the vector is sorted (by "key").

We think about compound values. For a student, the "key" might be their name or their student ID number or their box or ....

When you are looking for something (by key), we start by looking in the "middle" of the remaining elements. Three options: * The thing in the middle has the same key -> We're done! * The thing in the middle has a smaller key -> We can throw away all of the things that are smaller. (Half the vector.) * The thing in the middle has a larger key -> We can throw away all the things that are larger. (Half the vector.)

Practical issue: You can't "throw away" half an array. So, we instead keep track of the portion of the array that may contain the element (lower bound and upper bound).

Sample Quiz Questions

Finish the following definition of binary search on a sorted vector of integers.

;;; Procedure: ;;; binary-search-integers ;;; Parameters: ;;; val, an integer ;;; values, a vector of integers that is sorted ;;; Purpose: :;; Determine whether val appears in values ;;; Produces: ;;; in-vector?, a boolean ;;; Preconditions: ;;; For all reasonable i, ;;; (<= (vector-ref values i) (vector-ref values (+ i 1))) ;;; Postconditions: ;;; in-vector? is #t if val is in values ;;; in-vector? is #f otherwise (define binary-search-integers (lambda (val values) (let kernel ([lb __]) ([ub __]) (let ([mid (quotient (+ lb ub) 2)]) (cond [(__) #f] [(< val (vector-ref values mid)) ____] [(> val (vector-ref values mid)) ____] [else ____])))))

(define binary-search-integers (lambda (val values) (let kernel ([lb 0]) ([ub (- (vector-length values) 1)]) (let ([mid (quotient (+ lb ub) 2)]) (cond [(< ub lb) #f] [(< val (vector-ref values mid)) (kernel lb (- mid 1))] [(> val (vector-ref values mid)) (kernel (+ mid 1) ub)] [else #t])))))

Why do we do (+ mid 1) rather than mid in the third case?

Consider searching for 5 in the vector #(4 8). The midpoint is 0. If don't throw it away, we'll recurse forever.

For problem 6 on the exam, what do you mean by "in place"?

We don't want you to create a new vector or list. We want you to change the vector itself. (So yes, you should avoid creating new vectors or lists.)

Hint: You know how to use numeric recursion to iterate over positions in vectors.

Is it okay if our vector-reverse returns something at the end?

Sure.

How do we avoid returning anything?

1. Use a when clause. If the test doesn't hold, you get nothing. (when (test) consequent)

2. The procedure (void) also returns nothing.

When I wrote vector-reverse most recently, I used a when clause.

Problem: Write the procedure from the lab in which we return x.5 when the value is not there.

;;; Procedure: ;;; binary-search-integers ;;; Parameters: ;;; val, an integer ;;; values, a vector of integers that is sorted ;;; Purpose: :;; Determine where val appears in values ;;; Produces: ;;; index, a real number ;;; Preconditions: ;;; For all reasonable i, ;;; (<= (vector-ref values i) (vector-ref values (+ i 1))) ;;; Postconditions: ;;; If val is in values (= (vector-ref values index) val) ;;; Otherwise (< (vector-ref values (floor index)) val) ;;; (< val (vector-ref values (ceiling index)) val) ;;; val ends in .5 (define binary-search-integers (lambda (val values) (let kernel ([lb 0] [ub (- (vector-length values) 1)]) (let ([mid (quotient (+ lb ub) 2)]) (cond [(< ub lb) (* 0.5 (+ lb ub))] [(< val (vector-ref values mid)) (kernel lb (- mid 1))] [(> val (vector-ref values mid)) (kernel (+ mid 1) ub)] [else mid])))))

Let's see whether just averaging works for the base case. Suppose the value at mid is too small, and lb=ub=x. Recurse on lb=x+1 ub=x, Result is x+0.5 Suppose the value at mid is too large, and lb=ub=x. Recurse lb=x, ub=x-1. Result will be x-0.5 Experiments suggest that I was correct.

If I wasn't, I would have added an (= lb ub) case and dealth with the three options.

Can you talk about the four parameters to vector-insert, particularly the boundary parameter?

The boundary is the first thing after the portion of the array that we know is sorted.