1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #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 ;binary-contains? : vector N -> N or false
5 ;Given avector and key, returns the index of the key in avector if possible and returns false if key is not in avector.
6 
7 (define (binary-contains? avector key)
8   (binary-contains?-aux avector key 0 (sub1 (vector-length avector))))
9 
10 ;binary-contains?-aux : (vectorof number) [sorted] N N -> N or false
11 ;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 ;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.
13 
14 (define (binary-contains?-aux avector key left right)
15   (local ((define mid (round (+ left (/ (- right left) 2)))))
16     (cond
17       [(= (vector-ref avector mid) key) mid]
18       [(= left right) false]
19       [(< (vector-ref avector mid) key) (binary-contains?-aux avector key (+ mid 1) right)]
20       [else (binary-contains?-aux avector key left (- mid 1))])))
21 
22 #|
23 
24 Tests
25 
26 (define v1 (vector 1 4 6 7 10
27                    15 16 17 19 23
28                    25 26 27 28))
29 
30 (define v2 (build-vector 10000000 identity))
31 
32 (binary-contains? v1 27)
33 (time (binary-contains? v2 9638723))
34 |#
35 ;abstract run-time is log2(x)?
36 
37 ;vector-count : (vectorof symbols) symbol -> N
38 ;Given v and s, determine the number of times s occurs in v.
39 
40 (define (vector-count v s)
41   (vector-count-aux v s 0))
42 
43 ;vector-count-aux : (vectorof symbols) symbol N -> N
44 ;Given v and s, determine the number of times s occurs in v using i, which indicates the current index.
45 
46 (define (vector-count-aux v s i)
47   (cond
48     [(= (vector-length v) i) 0]
49     [(symbol=? (vector-ref v i) s) (+ 1 
50                                       (vector-count-aux v s (add1 i)))]
51     [else (vector-count-aux v s (add1 i))]))
52 #|
53 Test
54 
55 (define v3 (vector 'hi 'my 'name 'is 'sam 'and 'I 'am 'a 'programmer 'how 'about 'you
56                    'are 'you 'a 'programmer 'too?))
57 (vector-count v3 'programmer)
58 
59 |#
60 
61 ;scalar-product : (vectorof number) number -> (vectorof number)
62 ;Multiply each element in v by s to compute the scalar product.
63 
64 (define (scalar-product v s)
65   (build-vector (vector-length v)
66                 (lambda (x) (* s (vector-ref v x)))))
67 
68 (define v4 (vector 5 6 10 3))
69 (scalar-product v4 -2)
70 
71 ;id-vector : N -> (vectorof 1's)
72 ;Returns a vector containing n number of 1's.
73 
74 (define (id-vector n)
75   (build-vector n (lambda (x) 1)))
76 
77 (equal? (id-vector 6) (vector 1 1 1 1 1 1))
78 
79 ;vector+ : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
80 ;Computes the sum of v1 and v2.
81 ;ASSUMPTION : v1 and v2 have the same length.
82 
83 ;(define (vector+ v1 v2)
84 ;  (build-vector (vector-length v1)
85 ;                (lambda (x) (+ (vector-ref v1 x)
86 ;                               (vector-ref v2 x)))))
87 
88 ;vector-op : (vectorof numbers) (vectorof numbers) (number number -> number) -> (vectorof numbers)
89 ;
90 ;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.
91 
92 (define (vector-op v1 v2 op)
93   (build-vector (vector-length v1)
94                 (lambda (x) (op (vector-ref v1 x)
95                                 (vector-ref v2 x)))))
96 
97 (define (vector+ v1 v2)
98   (vector-op v1 v2 +))
99 (define (vector- v1 v2)
100   (vector-op v1 v2 -))
101 
102 (define v5 (vector 1 9 4 2 -3))
103 (define v6 (vector -5 -6 2 9 0))
104 (vector+ v5 v6)
105 (vector- v5 v6)
106 
107 ;checked-vector+ : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
108 
109 (define (checked-vector+ v1 v2)
110   (cond 
111     [(and (vector? v1)
112        (vector? v2)
113        (= (vector-length v1) (vector-length v2))) (vector+ v1 v2)]
114     [else (error 'checked-vector+ "expected arg: 2 vectors")]))
115 
116 ;checked-vector- : (vectorof numbers) (vectorof numbers) -> (vectorof numbers)
117 
118 (define (checked-vector- v1 v2)
119   (cond 
120     [(and (vector? v1)
121        (vector? v2)
122        (= (vector-length v1) (vector-length v2))) (vector- v1 v2)]
123     [else (error 'checked-vector- "expected arg: 2 vectors")]))