1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-advanced-reader.ss" "lang")((modname |29.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu ;binary-contains? : vector N -> N or false
5 12687dd9 2023-08-04 jrmu ;Given avector and key, returns the index of the key in avector if possible and returns false if key is not in avector.
7 12687dd9 2023-08-04 jrmu (define (binary-contains? avector key)
8 12687dd9 2023-08-04 jrmu (binary-contains?-aux avector key 0 (sub1 (vector-length avector))))
10 12687dd9 2023-08-04 jrmu ;binary-contains?-aux : (vectorof number) [sorted] N N -> N or false
11 12687dd9 2023-08-04 jrmu ;Given avector (sorted), key, left, and right (the boundaries of avector to be searched), binary-contains?-aux determines the index of the key in the vector if it occurs using the binary-search algorithm. Otherwise, returns false.
12 12687dd9 2023-08-04 jrmu ;Termination Argument: Each interval must necessarily reduce in size by at least 50% each recursion. Since the midpoint is not included in the subsequent recursion, we are guaranteed that the interval must actually decrease in size each recursion until both left and right are equal and the interval consists of only a single number. Hence, we are guaranteed that the function will terminate.
14 12687dd9 2023-08-04 jrmu (define (binary-contains?-aux avector key left right)
15 12687dd9 2023-08-04 jrmu (local ((define mid (round (+ left (/ (- right left) 2)))))
17 12687dd9 2023-08-04 jrmu [(= (vector-ref avector mid) key) mid]
18 12687dd9 2023-08-04 jrmu [(= left right) false]
19 12687dd9 2023-08-04 jrmu [(< (vector-ref avector mid) key) (binary-contains?-aux avector key (+ mid 1) right)]
20 12687dd9 2023-08-04 jrmu [else (binary-contains?-aux avector key left (- mid 1))])))
26 12687dd9 2023-08-04 jrmu (define v1 (vector 1 4 6 7 10
27 12687dd9 2023-08-04 jrmu 15 16 17 19 23
28 12687dd9 2023-08-04 jrmu 25 26 27 28))
30 12687dd9 2023-08-04 jrmu (define v2 (build-vector 10000000 identity))
32 12687dd9 2023-08-04 jrmu (binary-contains? v1 27)
33 12687dd9 2023-08-04 jrmu (time (binary-contains? v2 9638723))
35 12687dd9 2023-08-04 jrmu ;abstract run-time is log2(x)?
37 12687dd9 2023-08-04 jrmu ;vector-count : (vectorof symbols) symbol -> N
38 12687dd9 2023-08-04 jrmu ;Given v and s, determine the number of times s occurs in v.
40 12687dd9 2023-08-04 jrmu (define (vector-count v s)
41 12687dd9 2023-08-04 jrmu (vector-count-aux v s 0))
43 12687dd9 2023-08-04 jrmu ;vector-count-aux : (vectorof symbols) symbol N -> N
44 12687dd9 2023-08-04 jrmu ;Given v and s, determine the number of times s occurs in v using i, which indicates the current index.
46 12687dd9 2023-08-04 jrmu (define (vector-count-aux v s i)
48 12687dd9 2023-08-04 jrmu [(= (vector-length v) i) 0]
49 12687dd9 2023-08-04 jrmu [(symbol=? (vector-ref v i) s) (+ 1
50 12687dd9 2023-08-04 jrmu (vector-count-aux v s (add1 i)))]
51 12687dd9 2023-08-04 jrmu [else (vector-count-aux v s (add1 i))]))
55 12687dd9 2023-08-04 jrmu (define v3 (vector 'hi 'my 'name 'is 'sam 'and 'I 'am 'a 'programmer 'how 'about 'you
56 12687dd9 2023-08-04 jrmu 'are 'you 'a 'programmer 'too?))
57 12687dd9 2023-08-04 jrmu (vector-count v3 'programmer)
61 12687dd9 2023-08-04 jrmu ;scalar-product : (vectorof number) number -> (vectorof number)
62 12687dd9 2023-08-04 jrmu ;Multiply each element in v by s to compute the scalar product.
64 12687dd9 2023-08-04 jrmu (define (scalar-product v s)
65 12687dd9 2023-08-04 jrmu (build-vector (vector-length v)
66 12687dd9 2023-08-04 jrmu (lambda (x) (* s (vector-ref v x)))))
68 12687dd9 2023-08-04 jrmu (define v4 (vector 5 6 10 3))
69 12687dd9 2023-08-04 jrmu (scalar-product v4 -2)
71 12687dd9 2023-08-04 jrmu ;id-vector : N -> (vectorof 1's)
72 12687dd9 2023-08-04 jrmu ;Returns a vector containing n number of 1's.
74 12687dd9 2023-08-04 jrmu (define (id-vector n)
75 12687dd9 2023-08-04 jrmu (build-vector n (lambda (x) 1)))
77 12687dd9 2023-08-04 jrmu (equal? (id-vector 6) (vector 1 1 1 1 1 1))
79 12687dd9 2023-08-04 jrmu ;vector+ : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
80 12687dd9 2023-08-04 jrmu ;Computes the sum of v1 and v2.
81 12687dd9 2023-08-04 jrmu ;ASSUMPTION : v1 and v2 have the same length.
83 12687dd9 2023-08-04 jrmu ;(define (vector+ v1 v2)
84 12687dd9 2023-08-04 jrmu ; (build-vector (vector-length v1)
85 12687dd9 2023-08-04 jrmu ; (lambda (x) (+ (vector-ref v1 x)
86 12687dd9 2023-08-04 jrmu ; (vector-ref v2 x)))))
88 12687dd9 2023-08-04 jrmu ;vector-op : (vectorof numbers) (vectorof numbers) (number number -> number) -> (vectorof numbers)
90 12687dd9 2023-08-04 jrmu ;Given v1 and v2, build a new list of vectors where each element in the new vector is created by performing op on the corresponding elements of v1 and v2.
92 12687dd9 2023-08-04 jrmu (define (vector-op v1 v2 op)
93 12687dd9 2023-08-04 jrmu (build-vector (vector-length v1)
94 12687dd9 2023-08-04 jrmu (lambda (x) (op (vector-ref v1 x)
95 12687dd9 2023-08-04 jrmu (vector-ref v2 x)))))
97 12687dd9 2023-08-04 jrmu (define (vector+ v1 v2)
98 12687dd9 2023-08-04 jrmu (vector-op v1 v2 +))
99 12687dd9 2023-08-04 jrmu (define (vector- v1 v2)
100 12687dd9 2023-08-04 jrmu (vector-op v1 v2 -))
102 12687dd9 2023-08-04 jrmu (define v5 (vector 1 9 4 2 -3))
103 12687dd9 2023-08-04 jrmu (define v6 (vector -5 -6 2 9 0))
104 12687dd9 2023-08-04 jrmu (vector+ v5 v6)
105 12687dd9 2023-08-04 jrmu (vector- v5 v6)
107 12687dd9 2023-08-04 jrmu ;checked-vector+ : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
109 12687dd9 2023-08-04 jrmu (define (checked-vector+ v1 v2)
111 12687dd9 2023-08-04 jrmu [(and (vector? v1)
112 12687dd9 2023-08-04 jrmu (vector? v2)
113 12687dd9 2023-08-04 jrmu (= (vector-length v1) (vector-length v2))) (vector+ v1 v2)]
114 12687dd9 2023-08-04 jrmu [else (error 'checked-vector+ "expected arg: 2 vectors")]))
116 12687dd9 2023-08-04 jrmu ;checked-vector- : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
118 12687dd9 2023-08-04 jrmu (define (checked-vector- v1 v2)
120 12687dd9 2023-08-04 jrmu [(and (vector? v1)
121 12687dd9 2023-08-04 jrmu (vector? v2)
122 12687dd9 2023-08-04 jrmu (= (vector-length v1) (vector-length v2))) (vector- v1 v2)]
123 12687dd9 2023-08-04 jrmu [else (error 'checked-vector- "expected arg: 2 vectors")]))
