[SOLVED] CS 320 OCaml Programming

CS 320 OCaml Programming

(* Problem 1.

Copyright By Assignmentchef assignmentchef

In this problem, you are to implement a tail-recursive function tetra for computing the
Tetranacci Sequence. The Tetranacci Sequence is a generalization of the Fibonacci Sequence,
in particular it adds the previous 4 numbers to obtain the next number in the sequence.

tk = tk-1 + tk-2 + tk-3 + tk-4 (for any k > 3)

See https://mathworld.wolfram.com/TetranacciNumber.html for more details if necessary.

* You may assume all inputs are non-negative integers.
* Your tetra function must return a result for large inputs such a 1000.
* StackOverflow errors are not accepted.
* IntegerOverflow is both accepted and expected. *)
let tetra (n : int) : int =

(* Problem 2.

In this problem you are to implement the classical Euclidean algorithm for computing
greatest common divisor. Your implementation of gcd must be tail-recursive.

gcd 7 81 = 1
gcd 9 81 = 9
gcd 141 36 = 3
gcd 84 144 = 12
gcd 315 441 = 63

See https://en.wikipedia.org/wiki/Euclidean_algorithm for more details if necessary.

* You may assume both inputs x and y are positive integers.
* StackOverflow errors are not accepted. *)
let rec gcd (x : int) (y : int) : int =

(* Problem 3.

In this problem, you are to implement a sqrt function that finds the square root
of a given number.

sqrt 100 = 10
sqrt 81 = 9
sqrt 144 = 12
sqrt 15129 = 123

* You may assume the inputs are non-negative integers.
* You may assume there exists an integer square root to each input.
* As a challenge, you can try the binary search method to find the square root (optional). *)
let sqrt (n : int) : int =

(* Problem 4.

In this problem, you are to implement an is_prime to check for prime numbers. If an input
x is prime, then return -1. Otherwise return the smallest factor of input x.

is_prime 81 = 3
is_prime 7 = -1
is_prime 144 = 2
is_prime 371 = 7
is_prime 53 = -1

* You may assume that inputs are non-negative integers.
* You may return any value for inputs 0 and 1. *)
let is_prime (n : int) : int =

(* Problem 5.

In this problem, you are to implement a string_of_intlist function to convert
int lists to their string representations.

string_of_intlist [] = []
string_of_intlist [1] = [1]
string_of_intlist [1; 2] = [1; 2]
string_of_intlist [1; 2; 3] = [1; 2; 3]
string_of_intlist [1; 2; 3; 4] = [1; 2; 3; 4]

* You may use the library function string_of_int to convert int to string.
* You may use the ^ operator to append strings.
* You do not need to worry about spacing. *)
let string_of_intlist (ls : int list) =

(* print_intlist can be used for testing the output of following problems. *)
let print_intlist ls = print_endline (string_of_intlist ls)

(* Problem 6.

Implement a tail-recursive list reversal function rev.

rev [] = []
rev [1] = [1]
rev [1; 2] = [2; 1]
rev [1; 2; 3; 4] = [4; 3; 2; 1]

* Your implementation must be efficient for long lists.
* StackOverflow errors are not accepted. *)
let rev ls =

(* Problem 7.

Implement a tail-recursive function length for counting the number of elements
in an int list.

length [] = 0
length [1] = 1
length [1; 2] = 2
length [1; 2; 3; 4] = 4

* Your implementation must be efficient for long lists.
* StackOverflow errors are not accepted. *)
let length ls =

(* Problem 8.

Implement a prime factorization function factor. 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.
let factor (n : int) : int list =

(* Problem 9.

Implement a range function intlist_range. Given two integer inputs a and b, return a
list of number between a and b (not including b).

intlist_range 0 5 = [0; 1; 2; 3; 4]
intlist_range 7 10 = [7; 8; 9]
intlist_range 10 7 = []
intlist_range (-3) 1 = [-3; -2; -1; 0]

* If b < a, then return an empty list as the result. *)let intlist_range (a : int) (b : int) : int list =(* Problem 10. You are to implement the dot product operation of linear algebra using tail-recursion. When given an int list xs and int list ys, the dot product is computed as follows. xs = [x1; x2; x3; … xk] ys = [y1; y2; y3; … yk] dot_product xs ys = (x1 * y1) + (x2 * y2) + (x3 * y3) + … + (xk * yk) * You may assume inputs xs and ys are of the same length. * StackOverflow errors are not accepted. *)let dot_product (xs : int list) (ys : int list) : int = CS: assignmentchef QQ: 1823890830 Email: [email protected]