Advanced Exercises on ML/OCaML

Exercise 1: Social Networks.

A **social network** is a social structure made of individuals (or organizations) called **nodes**, which are tied (**connected**) by one or more specific types of interdependency, such as friendship, kinship, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.

A **graph** is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called **vertices**, and the links that connect some pairs of vertices are called **edges**.

The exercise consists of:

- implementing the social network as a graph, i.e., to define the graph data structure with the operations you consider necessary to implement a social network
- implementing an operation that visits in a convenient way
**all**the elements of the graph - testing it against a dummy social network.

Exercise 2: Playing around with Algebra.

A **monoid** is an algebraic structure consisting of a set together with a single associative binary operation and an identity element. E.g., the set of booleans with the or operator is a monoid whose identity is false.

A **group** is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity and invertibility. E.g., the set Z (the integers with sign) with the + operator is a group but with the * is not since inverting the operation break the closure property.

A **ring** is an algebraic structure consisting of a set together with two binary operations (usually called addition and multiplication), where each operation combines two elements to form a third element. To qualify as a ring, the set together with its two operations must satisfy certain conditions, namely, the set must be an abelian (i.e., commutative) group under addition and a monoid under multiplication such that multiplication distributes over addition.

Write the `Monoid`, `Group` and `Ring` modules implementing the monoids, groups and rings algebraic structures respectively. Each module must be parametric on the algebraic sort, in the sense that the operations and the sets are not a priori defined and they should implement operations to check the properties characterizing the algebraic structure.

Test your implementation with the following examples (S is the set, add=additive operation, mul=multiplicative operation, i=identity):

**Monoids**

- S = {True, False} add = or i = False
- S = Zn={0,1,...,n-1} add = + where a+b=(a+b)%n i = 0

**Groups**

- S = {True, False}, add = or, i = False
- S = Z, add = +, i = 0
- S = Z4 = {0, 1, 2, 3}, add = * where a*b=(a*b)%4, i = 1
- S = {
`a`}*, add: {`a`}*×{`a`}* --> {`a`}* where x1·x2 is x1 if #x1 > #x2, x2 otherwise, i = the empty string

**Rings**

- S = {0} add = + where 0+0=0 mul = * where 0*0=0 i = 0
- S = Z add = + mul = * i = 0
- S = Z4 = {0,1,2,3} add = + where a+b=(a+b)%4 mul = * where a*b=(a*b)%4 i = 0

**Note** property checks on infinite sets should be on a finite subset.

Exercise 3: Playing with Files and Strings.

A `KeWord` In Context (KWIC) index is a simple index for a list of lines or titles. This assignment involves creating a KWIC index for an input list of titles stored in a file. Here's a small example. For the input file:

`Casablanca`

`The Maltese Falcon`

`The Big Sleep`

your program should produce the output:

`3 The Big Sleep .`

`1 Casablanca .`

`2 The Maltese Falcon .`

`2 The Maltese Falcon`

`3 The Big Sleep .`

As you can see, each title is listed for each word (omitting some **minor** words). The titles are arranged so that the word being indexed is shown in a column on the page. The position the lines have in the input file is shown on the left in the result.

Your solution should follow the following rules:

- The input is just a series of titles, one per line. Any leading or trailing spaces should be removed. Internal spaces should be retained (trimmed to one).
- A word is a maximal sequence of non-blank characters.
- The output line is at most 79 characters wide.
- The number is 5 characters wide, right-justified.
- There is a space after the number.
- The key word starts at position 40 (numbering from 1).
- If the part of the title left of the keyword is longer than 33, trim it (on the left) to 33.
- If the part of the keyword and the part to the right is longer than 40, trim it to 40.

- Each title appears in the output once for each word that isn't
**minor.**Any word of length two or less is minor,`and`and`the`words are minor words. - If a title has a repeated word, it should be listed for each repetition.
- Sorting should be case-insensitive.

Exercise 4: A Few More Math.

Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Every even integer greater than 2 is a Goldbach number, i.e., a number that can be expressed as the sum of two odd primes.

Expressing a given even number as a sum of two primes is called a Goldbach partition of the number. For example,

`04 = 2 + 2 6 = 3 + 3 8 = 3 + 5`

`10 = 7 + 3 12 = 5 + 7 14 = 3 + 11`

`16 = 5 + 11 18 = 7 + 11 20 = 7 + 13`

Write the following functions:

`goldbach(n)`that returns a Goldbach partition for`n``goldbach_list(n,m)`that returns a list of Goldbach partitions for the even numbers in the range`(n,m)`.

Exercise 5: A Matrix Class.

You have to write a module `Matrix` to represent and manipulate integer matrices. The module should be parametric and will provide the operations of matrix equivalence, matrix copy, matrix addition, scalar-matrix multiplication, matrix-matrix multiplication, matrix transposition, and matrix norm -- the "size" of a matrix. Override the appropriate operators and raise the appropriate exceptions.

We first define these operations, and then give a skeleton of the Matrix module showing the signatures for all methods and constructors you must implement.

**The operations**

Let aᵢⱼ denotes the i,j-th element of matrix A, located at row i, column j. Using this notation, the matrix operations listed above may be defined precisely as follows:

**matrix equivalence**A ≃ B where A in Ζᵐˣⁿ, B in Zp×q when m = p and n = q and bᵢⱼ = aᵢⱼ for i = 1,...,m j = 1,...,n;**matrix copy**B = A where A, B in Ζᵐˣⁿ (bᵢⱼ = aᵢⱼ for i = 1,...,m j = 1,...,n);**matrix addition**C = A + B where A, B, C in Ζᵐˣⁿ (cᵢⱼ = aᵢⱼ + bᵢⱼ for i = 1,...,m j = 1,...,n);**scalar-matrix multiplication**B = aA where A, B in Ζᵐˣⁿ, a in Z (bᵢⱼ = a·aᵢⱼ for i = 1,...,m j = 1,...,n);**matrix-matrix multiplication**C = A·B where A in Zᵐˣᵖ, B in Zᵖˣⁿp×n, C in Ζᵐˣⁿ (cᵢⱼ = Σₖ=1, ..., p aᵢₖ·bₖⱼ for i = 1,...,m j = 1,...,n);**matrix transposition**B = AT where A in Ζᵐˣⁿ, B in Zⁿˣᵐ (bⱼᵢ = aᵢⱼ for i = 1,...,m j = 1,...,n);**matrix norm (matrix 1-norm)**a = ‖A‖ where a in Z, A in Ζᵐˣⁿ (a = maxⱼ Σᵢ | aᵢⱼ | for i = 1,...,m j = 1, ..., n).

Note that in each case we state the proper matrix dimensions for the operation to be valid. For example, when multiplying two matrices A and B, the number of columns of A must match the number of rows of B.