Lab: Searching

Assigned

Monday, 27 November 2023

Summary

In this brief lab, you’ll practice hand-executing the search algorithms described in the reading.

Problem 1: binary search tracing

The following live code snippet randomly generates three binary search problems for you to work through with your partner. Trace through the step-by-step execution of binary search, looking for each of the given values in the provided vector. Follow the format found in the reading where you outline at each step:

• The region of the vector currently under consideration.
• The middle element that you are comparing next.

(Note 1: the turn-in for Gradescope is an online assignment that you can directly write your results into.)

(Note 2: this code is live and will generate random results for you to practice for the final SoLA!)

;;; (make-random-list n) -> list?
;;;   n: integer?, non-negative
;;; Creates a list of size of n made of random
;;; numbers in the range 0 to n.
(define make-random-list
  (lambda (n)
    (if (zero? n)
        null
        (cons (random n) (make-random-list (- n 1))))))

;;; (insert-sorted l v) -> list?
;;;   l: list?, sorted
;;;   v: any
;;; Returns l but with v inserted in its sorted position in l.
(define insert-sorted
  (lambda (l v)
    (match l
      [null (list v)]
      [(cons head tail)
       (if (<= v head)
           (cons v l)
           (cons head (insert-sorted tail v)))])))

;;; (insertion-sort-helper unsorted) -> list?
;;;   unsorted: list?
;;;   sorted: list?
;;; Returns sorted but with the elements of unsorted inserted into
;;; sorted so that the whole list is sorted.
(define insertion-sort-helper
  (lambda (unsorted sorted)
    (match unsorted
      [null sorted]
      [(cons head tail)
       (insertion-sort-helper tail (insert-sorted sorted head))])))

;;; (insertion-sort l) -> list?
;;;   l: list? of numbers
;;; Returns l but sorted via insertion sort.
(define insertion-sort
  (lambda (l)
    (insertion-sort-helper l null)))

;;; A problem is a pair of an sorted list and a value to find.
(struct problem (lst value))

;;; (make-search-problem n) -> problem?
;;;   n: integer?, non-negative
;;; Constructs a search problem consisting of a sorted list of size
;;; n and one of its values.
(define make-search-problem
  (lambda (n)
    (let* ([lst (insertion-sort (make-random-list n))]
           [value (list-ref lst (random n))])
      (problem lst value))))

; Randomly generated problem (a)
(make-search-problem 15)

; Randomly generated problem (b)
(make-search-problem 15)

; Randomly generated problem (c)
(make-search-problem 15)

Optional Problem: cold call

For this reading, we developed the code to perform both linear and binary search. Even though this code is now available to you, it is excellent practice to try to implement these functions cold without referencing the reading.

If you would like additional practice writing tricky code, try to implement:

• (list-sequential-search lst v)
• (vector-sequential-search vec v)
• (binary-search vec v)

Without referencing the reading. For additional practice, try to vary the implementation of your functions

• Change their input types to be parameterized in the way that elements are compared to equality.
• Change their return types so that they return booleans indicating success versus indices denoting where the element is located.

Optional Problem: binary search trees

You may have noticed that the binary search procedure feels like a binary tree! It turns out there’s a connection. We can enhance the definition of a binary tree to capture this idea of sortedness. The result is a structure called a binary search tree or bst:

• A binary search tree is recursively defined to be either:
  • Empty or a leaf.
  • Non-empty or a node with a value v and a left and right subtree. Furthermore, we require that all the values found in the left subtree are less than or equal v and all the values in the right subtree are greater than v.

This additional condition in the node case is called the binary search tree invariant. Pictorally, we have:

      (v)
     /   \
    /     \
   /       \
left     right
subtree  subtree
 ≤ v       v >

Try implementing (bst-contains t v) which takes a binary search tree t and a value v as input and returns #t if and only if t contains v. Instead of performing a linear search on the nodes of t, you should take advantage of the binary search tree invariant to rapidly hone in on the desired value!