Previous Contents Next

Exercises

Doubly Linked Lists

Functional programming lends itself well to the manipulation of non-cyclic data structures, such as lists for example. For cyclic structures, on the other hand, there are real implementation difficulties. Here we propose to define doubly linked lists, i.e., where each element of a list knows its predecessor and its successor.
  1. Define a parameterized type for doubly linked lists, using at least one record with mutable fields.

  2. Write the functions add and remove which add and remove an element of a doubly linked list.

Solving linear systems

This exercise has to do with matrix algebra. It solves a system of equations by Gaussian elimination (i.e., pivoting). We write the system of equations A   X = Y with A, a square matrix of dimension n, Y, a vector of constants of dimension n and X, a vector of unknowns of the same dimension.

This method consists of transforming the system A   X = Y into an equivalent system C   X = Z such that the matrix C is upper triangular. We diagonalize C to obtain the solution.
  1. Define a type vect, a type mat, and a type syst .

  2. Write utility functions for manipulating vectors: to display a system on screen, to add two vectors, to multiply a vector by a scalar.

  3. Write utility functions for matrix computations: multiplication of two matrices, product of a matrix with a vector.

  4. Write utility functions for manipulating systems: division of a row of a system by a pivot, (Aii), swapping two rows.

  5. Write a function to diagonalize a system. From this, obtain a function solving a linear system.

  6. Test your functions on the following systems:

    AX =



    10 7 8 7
    7 5 6 5
    8 6 10 9
    7 5 9 10




    *



    x1
    x2
    x3
    x4




    =



    32
    23
    33
    31




    = Y

    AX =



    10 7 8 7
    7 5 6 5
    8 6 10 9
    7 5 9 10




    *



    x1
    x2
    x3
    x4




    =



    32.1
    22.9
    33.1
    30.9




    = Y

    AX =



    10 7 8.1 7.2
    7.08 5.04 6 5
    8 5.98 9.89 9
    6.99 4.99 9 9.98




    *



    x1
    x2
    x3
    x4




    =



    32
    23
    33
    31




    = Y


  7. What can you say about the results you got?

Previous Contents Next