Overview

• Quick quiz overview.
• You ask questions, I attempt to answer.
• We talk more about the forthcoming quiz.

Quiz Topics

• Searching (primarily with binary search)
  • Operation (divide-and-conquer, etc.)
  • Parameters (get-key, may-precede?)
  • Preconditions/postconditions
• Sorting
  • Insertion sort (in lists and vectors)
  • Selection sort (discussed, not implemented)
  • Merge sort (in lists)
  • Preconditions/postconditions

Your Topical Questions

Could there be a question on selection sort on the quiz?

Certainly. I might ask you to finish the implementation of selection sort, or to run a selection sort algorithm, or ....

Why is the difference between the number of calls to may-precede? and the number of calls to merge? constant?

Why might merge take different numbers of recursive calls for two pairs of sorted lists of the same length? Are there two lists that you think will be easier to merge or harder to merge?

    (50 60 70 80) (46 47 48 49)
    (50 60 70 80) (55 65 75 85)

Idea: Closeness might have an effect

Two other ideas: In the first case, all the numbers in one list come before all the numbers in the other list. In the other case, the numbers alternate.

    (merge '(50 60 70 80) '(46 47 48 49))
    (cons 46 (merge '(50 60 70 80) '(47 48 49)))
    (cons 46 (cons 47 (merge '(50 60 70 80) '(48 49))))
    (cons 46 (cons 47 (cons 48 (merge '(50 60 70 80) '(49)))))
    (cons 46 (cons 47 (cons 48 (cons 49 (merge '(50 60 70 80) ())))))

    (cons 46 (cons 47 (cons 48 (cons 49 '(50 60 70 80)))))
    (cons 46 (cons 47 (cons 48 '(49 50 60 70 80))))
    (cons 46 (cons 47 '(48 49 50 60 70 80)))
    (cons 46 '(47 48 49 50 60 70 80))
    '(46 47 48 49 50 60 70 80))

    (merge '(50 60 70 80) '(55 65 75 85))
    (cons 50 (merge '(60 70 80) '(55 65 75 85)))
    (cons 50 (cons 55 (merge '(60 70 80) '(65 75 85))))
    (cons 50 (cons 55 (cons 60 (merge '(70 80) '(65 75 85)))))
    (cons 50 (cons 55 (cons 60 (cons 65 (merge '(70 80) '(75 85)))))

Exam Questions

Can you give some hints about problem 1 (testing assoc)

Try different size lists.

Think about some of the complication we encoutered and why we wrote variants of assoc.

Look at some of the ways we suggested that you explore the meaning of assoc.

Error messages and incorrect return values count as errors.

Can you talk more about the "from tables to functions" problem (number 2)?

Input to table->lookup is a table of the kind we use we assoc

    (list (cons key value)
          (cons key value)
          (cons key value))

    (list (list key info1 info2 info3)
          (list key info1 info2 info3)
          (list key info1 info2 info3))

Output is a function (you might call it lookup) with the following characteristics

The function (lookup) a key as input

Looks in the table for the first instance of the key (just like assoc.)

If the key appears in the table, returns the corresponding value.

If the key does not appear in the table, issues an error message.

Hints: 1. Review how to return a function. Review the assoc reading for how to search for the key.

Can you give hints on problem #5

Suppose I have a vector of 71 elements. What element in the vector will be the root of the balanced tree? The elements are indexed from 0 to 70. If we use element at index 35, elements 0..34 (35) will be in the left subtree and elements 36..70 (35) will be in the right subtree.

What will be in the middle of the left subtree? Element 17.

What will be in element 17's left subtree? Elements in positions 0 to 16.

What will be in element 17's right subtree? 18 to 34.

What will be the root of element 35's right subtree (elements 36 to 70)? 53. Because 36 + 17 is 53. (Also other computation.)

What are the elements in the left subtree of the subtree whose root is element 53? 36..52

Which of those elements will be the root of that subtree? 44. 52-36=16, 16/2=8, 36+8=44.

About the Quiz

Likely types of quiz questions:

• Interpret or document this code or this algorithm.
• Finish writing this code that is supposed to accomplish this task.
• Find the bugs in this code that is supposed to accomplish this task.

Write an expression to sort the following list of values, each o of which has the form (list last-name first-name). Recall that the sort procedure has two parmeters: a list of things to sort and the comparator to use (may-precede?)

    (list (list "Smith" "Samuel")
          (list "Anaconda" "Amanda")
          (list "Smith" "Michelle")
          (list "Jones" "James")
          (list "Smith" "Freda")
          (list "Jones" "Janey"))

Observation: We can't just compare last names; we also have to look at first names.

    (sort names (lambda (name1 name2)
                  (if (string-ci=? (car name1) (car name2))
                      (string-ci<=? (cadr name1) (cadr name2))
                      (string-ci<? (car name1) (car name2)))))

    (sort names (lambda (name1 name2)
                  (or (string-ci<? (car name1) (car name2))
                      (and (string-ci=? (car name1) (car name2))
                           (string-ci<=? (cadr name1) (cadr name2))))))

Consider the following vector of animal names in alphabetical order. What animals do we look at when looking for "elephant" using binary search?

    (vector "aardvark" "babboon" "chimp" "dingo" "emu"
            "frog" "guinea hen")
    ; 0: a, 1: b; 2: c; 3: d; 4: e; 5: f; 6: g
    ; position 3 (dingo)
    ; Look in the second half: 4..6
    ; Look in the middle: 5, frog
    ; Look to the left, 4..4
    ; Look in the middle: emu
    ; Look to the left, 4..3
    ; GIVE UP

If there were eight elements, indexed 0 .. 7, we'd look at the element at (quotient (+ 0 7) 2) = 3. (Binary search always rounds down when the middle is between two elements.