[SOLVED] CS CS 320 OCaml HW2

CS 320 OCaml HW2

(* Problem 1.

Copyright By Assignmentchef assignmentchef

Implement a function add_opt. Given two int option inputs a and b, if both are of the
Some form, return their sum tagged with Some. Otherwise return None.

add_opt (Some 1) (Some 2) = Some 3
add_opt None (Some 2) = None
add_opt (Some 1) None = None
add_opt None None = None *)
let add_opt (x : int option) (y : int option) : int option =
failwith unimplemented

(* Problem 2.

Previously in programming assignment 1, we have implemented an is_prime function that
outputs -1 on a prime number input and the smallest factor of a non-prime input. We have
are assigning a special meaning to the special value of -1, but using magic values
in general is not a good programming practice. For someone unfamiliar with our code, they
must be treat magic values with great caution. A much better choice is to use option types
instead of magic values, this will allow us to enforce correct handling of special cases
by leveraging the type system.

Your new implementation of is_prime outputs None on prime inputs. When given a non-prime
input, return its smallest factor tagged by Some.

is_prime 81 = Some 3
is_prime 7 = None
is_prime 144 = Some 2
is_prime 371 = Some 7
is_prime 53 = None

* You may assume that inputs are non-negative integers.
* You may assume inputs are greater than 1. *)
let is_prime (n : int) : int option = failwith unimplemented

(* Problem 3.

Implement the prime factorization function factor using is_prime from problem 1.
Given an input n, return a list of all of its prime factors.

factor 12 = [3; 2; 2]
factor 71 = [71]
factor 77 = [11; 7]
factor 98 = [7; 7; 2]
factor 100 = [5; 5; 2; 2]

* The order of prime factors in the result does not matter.
* Your implementation of factor must use is_prime from problem 1. *)
let factor (n : int) : int list = failwith unimplemented

(* Problem 4.

In assingment 1, you have implemented a dot_product function that computes the
dot product operation of linear algebra. You only needed to consider inputs of
the same length. In this problem you must consider inputs of possibly differing
lengths. When dot_product takes inputs of differing lengths, output None, otherwise
tag the result with Some.

dot_product [1; 1] [1; 1] = Some 2
dot_product [1] [1; 1] = None
dot_product [1; 1] [1] = None
dot_product [] [] = None

* Inputs may be of different lengths.
* If either input is empty, return None.
* StackOverflow errors are not accepted. *)
let dot_product (xs : int list) (ys : int list) : int option =
failwith unimplemented

(* Problem 5.

In this problem, you are to implement a function find_max. When given a list of
ints, find the one with greatest value and return it tagged with Some. If no ints
are found in the list, return None.

find_max [1; 2; 3] = Some 3
find_max [7; 10; 1; 6] = Some 10
find_max [] = None

* StackOverflow errors are not accepted *)
let find_max (ls : int list) : int option = failwith unimplemented

(* Problem 6.

A list could be used as a dictionary that maps values to values. We will use lists
of type (string * int) list as dictionaries to map strings to ints. We can implement
a find_key function that when given a dictionary and a key (string type), outputs
the value associated to the key (int type) tagged with Some if said key exists within
the dictionary. If the searched for key does not exist in the dictionary, output None.

find_key [(a, 1); (b, 2); (c, 3)] b = Some 2
find_key [(a, 1); (b, 2); (c, 3)] c = Some 3
find_key [(a, 1); (b, 2); (c, 3)] d = None
find_key [(a, 1); (b, 2); (c, 3); (b, 4)] b = Some 2

* If the list contains duplicate key entries, output the value associated to the leftmost
let rec find_key (dict : (string * int) list) (key : string) : int option =
failwith unimplemented

(* Problem 7.

Implement a function to_freq, that when given a string list, output a list of
type (string * int) list such that each string is associated with its frequency in
the original input.

to_freq [a; a; b; c; b; a] = [(a, 3); (b, 2), (c, 1)]
to_freq [jack; Jack; JACK] = [(jack, 1); (Jack, 1); (JACK, 1)]

* You do not need to consider the order of entries in the output.
* There should be no entries with repeated strings in your output.
An output such as [(a, 1); (a, 2)] is not accpeted.
* Strings are case sensitive. jack, Jack and JACK are considered different
and their frequencies are counted independently. *)
let to_freq (ls : string list) : (string * int) list = failwith unimplemented

(* Problem 8.

Implement a function filter_prime, that when given an int list removes
all prime numbers from this list.

filter_prime [2; 3; 4; 5; 6] = [4; 6]
filter_prime [7; 8; 9; 10; 11; 12] = [8; 9; 10; 12]

* You may assume all int elements of the input list are greater than 1.
* You MUST use the is_prime function implemented in this assignment. *)
let rec filter_prime (ls : int list) : int list = failwith unimplemented

(* Problem 9.

Implement a function concat that when given a list of int lists,
appends them all together into a single list.

concat [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]] = [1; 2; 3; 4; 5; 6; 7; 8; 9]
concat [[1; 2; 3]; []; [7; 8]] = [1; 2; 3; 7; 8]

* You may NOT use any functions from the OCaml List module.
* You may NOT use the operator. *)
let rec concat (lss : int list list) : int list = failwith unimplemented

(* Problem 10.

Matrix transpose is a fundamental operation in linear algebra. When
given a matrix (a grid filled numbers) of dimensions MxN (columns x rows),
the transpose operation will return back a new matrix with dimensions NxM.
This is done by taking the original rows as new columns and original columns
as new rows.

The following demonstrates the process of transposing a 53 matrix.

Oringinal (53):
01234
56789
10 11 12 13 14

Transposed (35):

A matrix can be represented as a int list list type, the nested
structure of an int list list can be used to encode a matrix. Your task
is to implement a transpose function that performs the transpose
operation on matrices encoded as nested lists.

[[0;1;2;3;4];
[5;6;7;8;9];
[10; 11; 12; 13; 14]]
[[0; 5; 10];
[1; 6; 11];
[2; 7; 12];
[3; 8; 13];
[4; 9; 14]]

[[0; 5; 10];
[1; 6; 11];
[2; 7; 12];
[3; 8; 13];
[4; 9; 14]]
[[0;1;2;3;4];
[5;6;7;8;9];
[10; 11; 12; 13; 14]]

* You may assume all nested int lists are of the same length.
* (optional challenge) Implement transpose such that each int element of
the input is only encountered by transpose or any of its helper functions
at most once, or in other words a single pass. *)
let transpose (lss : int list list) : int list list = failwith unimplemented

(* Problem 11.

Pascals triangle is a important and useful tool in mathematics. The numbers
computed by it have connections to probability theory, combinatorics and algrebra.
Your task is to implement a triangle function that computes Pascals triangle
(encoded as int list list) up to a given row.

To compute an element for a new row, we sum up the two numbers above it in the
previous row. See https://en.wikipedia.org/wiki/Pascals_triangle for a formal
description.

triangle 1 = [[1]]

triangle 2 =

triangle 3 =

triangle 4 =
[1;3;3;1]]

triangle 5 =
[1;4;6;4;1]]

* You may assume the input to triangle is a positive integer.
* (optional challenge) Implement triangle such that each int element of
the triangle is only encountered by triangle or any of its helper functions
at most once, or in other words a single pass. *)
let triangle (n : int) : int list list = failwith unimplemented

CS: assignmentchef QQ: 1823890830 Email: [email protected]