程序代写代做代考 data structure C ocaml CMSC 330, Fall 2018 — Midterm 1

Ruby Execution
Next to each Ruby snippet, write the output after executing it. If there is an error, then write “error.” 1. [2 pts]
x = {“CMSC330” => 1, “CMSC351” => 2, “CMSC320” => 3}
x[“CMSC216”] = 4
if x.key?(“CMSC216”) then
x[“CMSC330”] = x[“CMSC216”]
end
puts(x[“CMSC330”])
Solution. 4 2. [2 pts]
i=0
x = Hash.new(1) 3.times do
x[i] += 1
i += 1 end
puts(x)
Solution. {0=>2,1=>2,2=>2} 3. [2 pts]
x = [1, 2, 3]
x << "four" puts(x) 4 Solution. [1, 2, 3, ”four”] 4. [3 pts] def fun(y) i=1 while i <= y yield(i * i) i += 1 end end fun(4) { |x| puts(x) } Solution. 1 4 9 16 5. [3 pts] class Foo @@y = [] def initialize(ele) @@y.push(ele) end def add(ele) @@y.push(ele) @@y end end 5 f = Foo.new(12) g = Foo.new("a") h = g.add("e") h[3] = "i" puts(g.add("o")) Solution. [12, "a", "e", "i", "o"] 6 Ruby Programming You’re in charge of building a Ruby class for a bank that deals exclusively in the tech world’s hottest new currency: UMDCash. You need to implement the Bank class in order to support this hot new economy and make the teaching staff very rich. The Bank class must store the account names and each account’s current tally of UMDCash. You can assume that (a) each account name is distinct, and (b) there are no negative amounts ever provided to your code. 1. [2 pts] Implement initialize. You will have to decide the proper data structure(s) for storing the data needed for the rest of the outlined functions. 2. [8 pts] Implement importAccounts that takes the name of a file and loads accounts and their existing UMDCash tally. The file has one account per line, in the format “name:amount” where the name consists of (upper and lowercase) letters and the amount is an integer or float. If the same account appears more than once in the file, store only the highest value. If any line doesn’t follow this format, the line is invalid and should be skipped. Multiple calls to importAccounts will update existing balances. Names are NOT case sensitive (i.e. boB and Bob will be treated as the same name). Here is an example. b = Bank.new b.importAccounts("file.txt") Here is the contents of file.txt. Bob:10 Alice:48.50 McKenzie:33 Samantha:28.01 Kyle:Fifty # Invalid Line You may find it useful to use the IO.foreach method, that reads files. IO.foreach("myfile.txt") { |line| puts line } 3. [4 pts] Implement transfer that takes in an account name from, account name to, and a transfer amount. It returns true if the transaction succeeds, or false if either of the accounts do not exist or the from account doesn’t have enough UMDCash to complete the transfer. If false is returned, neither account’s balance should change. 4. [4 pts] Implement whoIsTheRichest that returns the name of the account in your bank who currently has the highest UMDCash total. Return nil if there are currently no accounts in your bank. 7 Solution. class Bank def initialize ledger = Hash.new(0) end def importAccounts(file) IO.foreach(file) do |line| if line =~ /^([A-Za-z]+):(\d+(\.\d+)?)/ then ledger[$1] = [ledger[$1], $2.to_f].max end end def transfer(from, to, amount) if not (ledger.key?(from) and ledger.key?(to) and ledger[from] >= amount) then
return false
end
ledger[from] -= amount
ledger[to] += amount
true
end
def whoIsTheRichest()
pair = ledger.max_by { |_, amt| amt }
pair[0] if pair
end end
8

OCaml Typing
Recall the definition of ‘a option.
type ‘a option = Some of ‘a | None
Determine the type of the following expressions. If there is an error, write “error.”
1. [3 pts]
fun a -> if a then None else (Some a)
Solution. bool->booloption
2. [3 pts]
fun a b c -> (a b) +. c > 0.0
Solution. (‘a->float)->’a->float->bool
Write an expression that has the following type, without using type annotations.
3. [3 pts] int -> int option -> int Solution.
let f a b =
match b with
| None -> a
| Some x -> a + x
4. [3 pts](‘a->’b->’a*’b)->’a->’b->(‘a*’b)list Solution. letfabc=(abc)::[(b,c)]
Define functions f that when used in the following expressions will not produce any type errors.
5. [3 pts]fungt->[gt;fgt]
Solution. fungt->gt
6. [2 pts]funx->(fx)::[x]
Solution. funx->x
9

OCaml Execution
Recall the definitions of map, fold_left, and fold_right.
let rec map f xs =
match xs with
| [] -> []
| x :: xt -> (f x) :: (map f xt)
let rec fold_right f xs a =
match xs with
| [] -> a
| x :: xt -> f x (fold_right f xt a)
let rec fold_left f a xs =
match xs with
| [] -> a
| x :: xt -> fold_left f (f a x) xt
Write the final value of the following OCaml expressions next to each snippet. If there is an error, write “error.”
1. [2 pts]
let y = 3 in
let x = y + 1 in
let y = 5 in
x
Solution. 4 2. [2 pts]
let f x y = if x > y then x – y else (if x < y then y - x) f32 Solution. Error. 3. [3 pts] let f a = match a with | (a1, a2) -> a1 * a2
map f [(2, 2); (1, 4); (3, 2)] Solution. [4;4;6]
10

4. [4 pts]
fold_left (fun a x -> if x mod 3 = 0 then x :: a else a) [] [1; 3; 11; 27]
Solution. [27;3] 5. [4 pts]
let rec f l = match l with
| [] -> []
| h :: t -> (fold_left (fun a x -> a * x) 1 t) :: (f t)
in f [1; 2; 3; 4]
Solution. [24;12;4;1]
11

OCaml Programming
For the following questions you may use map, fold_left, and fold_right.
1. [8 pts] Write sum_thresh : int list -> int -> (int * int) that returns a tuple where
• the first component is the sum of all elements in xs strictly less than thresh, and
• the second component is the sum of all the elements in xs greater than or equal to thresh.
Examples:
sum_thresh [5; 2; 7; 3] 4 = (5, 12)
sum_thresh [1; 2; 10; 5] 5 = (3, 15)
Solution.
let sum_thresh xs thresh =
fold_left (fun (a1, a2) x -> if x < thresh then (a1 + x, a2) else (a1, a2 + x)) (0, 0) xs 2. [10 pts] Write compress: 'a list -> (‘a * int) list that packs in consecutive duplicate elements together in a tuple (a, b), where a is the element and b is the number of consecutive occurrences.
Examples:
compress [] = []
compress [“a”; “a”] = [(“a”, 2)]
compress [“a”; “a”; “b”; “c”; “b”; “b”] = [(“a”, 2); (“b”, 1); (“c”, 1); (“b”, 2)]
Solution.
let compress xs = fold_left (fun a x ->
match a with
| [] -> [(x, 1)]
| (ch, cnt) :: xt ->
if ch = x then (ch, cnt + 1) :: xt
else (x, 1) :: (ch, cnt) :: xt) [] xs
12