Assignment 01 Solution

Description

1. [3 pts] Imagine a parallel universe in which Ruby is statically typed. Give the type of the simple method or if there is a type error, explain why there is one and if the same program would error with real Ruby.

 

def simple(x) if x == x then

 

1

 

else false

 

end end

 

2. [3 pts] It also happens that in this universe Ruby has no mutable state. Variable assignment acts like OCaml’s let … in … What should be the result of the following piece of code and why? Does this return the same result as regular Ruby?

 

def sum(xs) total = 0 xs.each do |x|

 

total = total + x end

 

total end

 

sum([1, 2, 3])

 

3. [3 pts] In our parallel universe OCaml is dynamically typed. What should the following code produce? If it errors, explain why. What would this code do under regular OCaml?

 

let simple x = if x = x then

 

0

 

else

 

1 + (fun x -> x)

 

in simple 1

 

4. [1 pts] What’s your favorite programming language? (Any programming language is an acceptable answer here.)

 

 

2

 

Regular Expressions

 

1. [3 pts] Write a Ruby regular expression that exactly accepts strings containing zero or more occurrences of the words pie and jam separated by either a , or a ;.

 

• foods?(“pie,jam”) true

 

• foods?(“pie,pie;pie,pie”) true

 

• foods?(“jam&jam”)

 

false

 

Fill in the blank below with your regular expression.

 

 

def foods?(str)
str =~ /	/

 

end

 

2. [3 pts] Write a Ruby regular expression that accepts strings containing an odd number of a’s.

 

 

• odd_as?(“aardvark”) true

 

• odd_as?(“sour”) false

 

Fill in the blank below with your regular expression.

 

 

def odd_as?(str)
str =~ /	/

 

end

 

3. [2 pts] Given the regular expression /w{3}.\w+\d?$/ circle all of the strings that would be accepted.

 

• google.com5

 

• wwwumdedu

 

• cmsc330com

 

 

 

 

 

3

 

Ruby Execution

 

Next to each Ruby snippet, write the output after executing it. If there is an error, then write “error.”

 

1. [2 pts]

 

cmsc = [131, 132, 216, 250, 330, 351] cmsc.reverse!

 

puts(cmsc[0])

 

 

 

2. [2 pts]

 

hash = Hash.new(-1) ruby = “Ruby” ocaml = “OCaml” hash[ruby] = 3 hash[ocaml] = 4

 

puts(hash[ocaml + ruby]) puts(hash[ocaml] + hash[ruby])

 

 

3. [3 pts]

 

def together(arr) str = “” arr.each do |x|

 

str += x.to_s end

 

str end

 

puts(together([1, 2, 3, 4, 5]))

 

 

 

 

 

 

 

 

 

 

 

 

4

 

4. [3 pts]

 

def double(val) yield(2 * val)

 

end

 

 

arr = [“Alpha”, “Beta”, “Charlie”] double(1) { |x| puts(arr[x]) }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

Ruby Programming

 

You’ve recently been hired by the newest pizzeria in town and the owner has asked you to create a way to take orders and pass them along to the delivery driver. Each order comes as a string that contains pizza toppings and the associated address. Due to huge success, each address is limited to a single order at a given time, so if a new order comes from the same address, the old order is replaced.

 

1. [2 pts] Implement the initialize Decide on a data structure(s) to store the needed information.

 

2. [6 pts] Implement the take_order The method will take in a string that is formatted to contain a list of toppings followed by an address. The toppings should contain only alphabetic characters and are separated by single spaces. The address should be a single non-negative four digit number. Because it is a small town, there is only one street (Main Street), going straight through town. Don’t add an order if the input string is malformed.

 

• take_order(“Pepperoni Spinach 3900”)

 

• take_order(“Cheese Pepperoni Peppers Mushrooms Spinach 4131”)

 

• take_order(“Cheese Ham Pineapple 7000”)

 

• take_order(“Cheese 9001”)

 

3. [4 pts] Implement the give_order method that takes a current address (as a string) and returns (again as a string) the closest address with a pending order. If there are no orders it should return false.

 

• give_order(“4000”)

 

“3900”

 

• give_order(“6000”) “7000”

 

4. [4 pts] Your delivery driver can handle up to three orders at once. The owner wants the driver to always go to the nearest location from their current location. Implement the route method to return (as a list of strings) the three closest orders, in order of how close they are to the most recent delivery—starting from the pizzeria at 5000 Main Street. These orders will then be removed from the list of pending orders.

 

• route()

 

[“4131”, “3900”, “7000”]

 

• route()

 

[“9001”]

 

• route()

 

[]

 

 

 

 

6

 

Implement your solution in the class skeleton below.

 

class Pizzeria

 

def initialize()

 

 

 

 

end

 

 

def take_order(order)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

end

 

 

def give_order(location)

 

 

 

 

 

 

 

 

 

end

 

 

def route()

 

 

 

 

 

 

 

 

 

 

 

end

 

end

 

 

7

 

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” and give a brief explanation.

 

1. [2 pts]

 

fun x -> [5] :: x

 

 

 

 

2. [2 pts]

 

[3; 4.0]

 

 

 

 

3. [2 pts]

 

let f x y z = x +. y +. z in f 1.0 2.0

 

 

 

 

Write an expression that has the following type, without using type annotations.

 

4. [2 pts] int option -> int list

 

 

 

 

 

 

 

5. [2 pts] ‘a list -> ‘a list list

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

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 x = 3 in

 

let f x y = x + y in f 5 2

 

2. [3 pts]

 

let f a x = x :: a in fold_left f [] [1; 2; 3]

 

3. [3 pts]

 

map (fun a x -> if (x mod 3) = 0 then x :: a else a) [1; 3; 11; 27]

 

 

 

 

 

4. [4 pts]

 

let f x y z = if y = x then y :: z else z in fold_right (f 3) [1; 2; 3; 3; 2; 1] []

 

 

 

 

 

 

 

 

9

 

OCaml Programming

 

Consider the argmin (f : (int -> int)) (xs : int list) : int function that returns the last element of the list xs that minimizes the given function f. You may assume the function only operates on non-empty lists. Here are some examples:

 

• argmin (fun x -> x) [0; 2; 1]

 

0

 

• argmin (fun x -> -x) [0; 2; 1]

 

2

 

• argmin (fun _ -> 0) [0; 2; 1]

 

1

 

1. [6 pts] Fill in the following blanks to correctly implement argmin. let argmin (f : int -> int) ((x :: xt) : int list) : int =

List.fold_left

 

(fun acc x ->
if	then

 

 

 

else

 

)

 

 

 

 

 

 

2. [2 pts] Suppose the list xs has length n. In terms of n, exactly how many times is the function f evaluated in the above implementation of argmin?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10

 

3. [8 pts] Fill in the following blanks to correctly implement argmin. let argmin (f : int -> int) ((x :: xt) : int list) : int =

let (min_x, _) =

 

List.fold_left
(fun (x’, y’) x ->
let y =				in
						then
if

 

else

 

)

 

(x, f x)

 

xt

 

in min_x

 

4. [2 pts] Suppose the list xs has length n. In terms of n exactly how many times is the function f evaluated in this new implementation of argmin?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11

 

Finite Automata

 

1. [2 pts]

 

 

 

 

 

 

 

 

 

 

 

 

 

Is the above finite automaton an NFA or DFA? (Select the most specific option.)

 

 

 

 

 

 

 

2. [6 pts] Draw a finite automaton (either an NFA or a DFA) that accepts the same strings as the regular expression:

 

(abc^⋆)j(a^⋆)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12

 

3. [8 pts] Convert the following NFA to a DFA using the subset construction algorithm. Label your states

 

 

with their appropriate subsets.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

13