Esercizi di Linguaggi di Programmazione

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:

  1. 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
  2. implementing an operation that visits in a convenient way all the elements of the graph
  3. 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

Groups

Rings

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:

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 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:

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 aij denote 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:

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.

Walter Cazzola

Didactics

Publications

Funded Projects

Research Projects

Related Events








Valid XHTML 1.0 Transitional