Exercise 1 Write a function

calculate : expfloat

that returns a result of a given arithmetic formula. The exp type is defined as follows:

type exp = X | INT of int

| REAL of float

| ADD of exp * exp

| SUB of exp * exp

| MUL of exp * exp

| DIV of exp * exp

| SIGMA of exp * exp * exp

| INTEGRAL of exp * exp * exp

For example, the following arithmetic formulas can be written in the exp type:

SIGMA(INT1,INT10,SUB(MUL(X,X),INT1)) INTEGRAL(REAL1.0,REAL10.0,SUB(MUL(X,X),INT1))

When you compute integrals, dx should be 0.1. 2

Exercise 2 Write a function

diff : aestringAE

that differentiates the given algebraic expression with respect to the variable given as the second argument. The ae type is defined as follows:

type ae = CONST of int

| VAR of string

| POWER of string * int

| TIMES of ae list

| SUM of ae list

For example, x² + 2x + 1 is represented by

SUM [POWER (x, 2); TIMES [CONST 2; VAR x]; CONST 1]

and differentiating it (w.r.t. x) gives 2x + 2, which can be represented by

SUM [TIMES [CONST 2; VAR x]; CONST 2]

Exercise 3 The following type specifies a set of big integers which can represent positive numbers larger than the 32-bit integer limit (2³² 1).

type bigint = BigInt of string

For example, a big integer 1032 is represented as BigInt 1032.

Write a function compute_bigint : op -> bigint * bigint -> bigint

that returns a resulting big integer for a given arithmetic operation along with two big integers as operands, and the op type is defined as follows:

type op = ADD | MUL

The function should behaves as follows:

compute_bigint ADD ((BigInt 1032), (BigInt 1032))

= BigInt 2064 compute_bigint MUL ((BigInt 183829184395481829391), (BigInt 76187828))

= BigInt 14005546282103253594766852748

Exercise 4 Write a function

countstring : stringstringint.

that returns the number of substrings in a given string. count string s x count how many times x is found in s (if x is the empty string , 0 is returned.

For instance,

countstring aaa⁰⁰ a = 3

countstring aaa⁰⁰ aa = 2

countstring abababababa⁰⁰ aba = 5

countstring GeeksforGeeksforGeeksforGeeks⁰⁰ GeeksforGeeks⁰⁰ = 3

countstring aaa⁰⁰ = 0

Note that the function should give correct results when two occurrences of the substring overlap. You may refer to the OCaml standard API https://ocaml.

org/api/String.html for useful functions for manipulating strings.

Exercise 5 Consider the following triangle which is called Pascals triangle:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

where the numbers on an edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.

Write a function

pascal : int * int -> int

that computes an element of Pascals triangle at a location specified by a row and a column (starting from 0). For example, pascal should behave as follows:

pascal (0,0) = 1 pascal (1,0) = 1 pascal (0,0) = 1 pascal (2,1) = 2

pascal (4,2) = 6

Exercise 6 The edit distance^[1] is a string metric for measuring the difference between two strings. Informally, the edit distance between two strings is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one string into the other. For example, the edit distance between kitten and sitting is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

1. kitten sitten (substitution of s for k)
2. sitten sittin (substitution of i for e)
3. sittin sitting (insertion of g at the end).

Write a function closest : string -> string list -> string

which takes a string s and a list of string vocab, and returns a string in vocab which is the most similar to s. For example, closest kitten [sitting; fighting; kicking] = sitting

because the edit distance between kitten and fighting is 5 and the distance between kitten and kicking is 4. In case of tie (i.e., multiple strings of the same edit distance), the leftmost element in the list vocab should be returned.

When computing the edit distance between two strings a and b (denoted dist(a,b), you may refer to the following inductive definition. tail(a) denotes a substring of a without the first character of a (e.g., tail(abc) = bc).

dist(tail(a),tail(b))dist(a,b) = dist(tail(a),b) 1 + min distdist((a,tailtail(a)(,tailb)) (b))

(the first characters of a and b are equal)

length of a (b is the empty string) length of b (a is the empty string)

Exercise 7 A graph is a structure amounting to a set of nodes in which some pairs of the nodes are related^[2].

We can depict personal relationships by a graph. Suppose person A likes person B, who likes person C. Person C also likes person B. Another person D likes person A. These relations can be represented by the following graph.

Let us suppose this like relation is transitive in the sense that if A likes B and B likes C, then A also likes C.

Write a function

likes : relationships -> person -> int

that given a graph of relationships and a person, returns the number of people whom the person likes. The type relationships is for representing a graph of personal relationships, which is defined as follow:

type relationships = (string * string) list

For example, the above graph can be represented as let graph = [(A, B); (B, C); (C, B); (D, A)]

The function should behave as follows:

likes graph A = 2 likes graph B = 2 likes graph C = 2 likes graph D = 3

Exercise 8 In the above graph, B likes him/herself for the following reason: B likes C and C likes B, and because the relation is transitive, B also likes B. For a similar reason, C also likes him/herself.

Write a function

selflove : relationshipsint

that returns the number of people who like him/herself. For example, given the above graph, selflove graph should return 2.