- Working with pointers, and pointers to pointers
- Working with
`void *`by casting to the appropriate type - Creating dynamically allocated vectors, pointer arrays, matrices, and returning them from functions
- Storing data of arbitrary size, allocating more memory as needed
- Freeing temporary allocated data when no longer needed
- Sorting and writing appropriate comparison functions
- Working with length-prefixed strings

1. **Scaling a matrix** Write a function that takes as parameter a matrix
of reals and its dimensions and returns a dynamically allocated matrix where each element has been divided by the sum of the elements on that line (if nonzero).

2. **Matrix transpose** Write a function that takes as parameters
a matrix and its dimensions and returns its transpose, dynamically allocated.

3. **Matrix addition** Write a function that takes as parameters two matrices of equal size and their dimensions and returns a dynamically allocated matrix for their sum.

5. **Sort text lines**
Read text until end of input, splitting lines longer than 255 characters.
Store the text in memory as array of pointers to lines. Each line is stored
as a length-prefixed string: there is no '\0' terminator, but the first
byte of a string stores its length. Sort the strings in increasing order
of their lengths, breaking ties in alphabetical order.

6. **Fibonacci strings**.
Fibonacci strings are defined as follows: *S*_{0} = 0,
*S*_{1} = 01,
*S _{n}* =

Write a function that takes an

7. **Mergesort** Write a function that sorts an array: 1) split it into two (almost) equal parts; 2) recursively sort the parts; 3) merge the sorted parts,
by repeatedly choosing the smallest of the two values at the front of each
sequence. If using dynamic allocation, free all temporary allocated data.

8. **Print from address array**
Write a function `int myprintf(const char *fmt, void *adrtab[])`
that works like `printf`, but receives a `NULL`-terminated array of
addresses (`void *`) of objects to be printed.

Implement the format specifiers %d, %f and %s, as well as printing ordinary
characters and `%`.
An error encountered in the format should terminate printing.

9.

Implement the format specifiers %d and %lf as well as matching ordinary characters and whitespace. An error encountered in the format should terminate reading.

10. **Sum of products**
An expression is a sum (+) of one or more products (*) of one or more
unsigned numbers, with optional whitespace.
Write a function that takes a string and returns the value of the expression represented by the string.
In a similar way to `strtol/strtod`, use the second parameter (a `char **`) to store the address where processing a correct expression stopped.

11. **Product of sums**
An expression is a sequence of terms. A term is an unsigned number
or a sum (+) of unsigned numbers enclosed in ( ). Whitespace is optional.
Write a function that takes a string and returns the value of the expression represented by the string.
In a similar way to `strtol/strtod`, use the second parameter (a `char **`) to store the address where processing a correct expression stopped.

Optional take-home exercise (review of propositional formulas, and structuring a problem into functions)

12. **Conjunctive normal form**
Write a program that reads from input, stores and then processes a list
of lists of integers representing a Boolean formula, as follows:

Each list is given as whitespace-separated nonzero integers ended by 0 (which is not part of the list)

Each list should be stored as a dynamically allocated array of integers, terminated by 0

The addresses of each array should be stored in a NULL-terminated array of pointers, dynamically allocated and returned from the function that reads all integers.

Option a): the maximum number of elements in a list is given (first number read from input), the number of lists could be arbitrarily large

Option b): the number of lists is given (first number read from input), the number of elements in a list could be arbitrarily large

Such an input can be used to represent a Boolean formula in conjunctive normal form: a positive integer n denotes proposition p_{n}, a negative integer -n denotes its negation ¬p_{n}; a list (clause) represents the disjunction (OR) of all propositions; the formula is the conjunction (AND) of all clauses (lists).

Process the formula to find out which propositions appear only positive, or only negated (i.e. for what numbers `x` the opposite, `-x` does not appear).

Remove from the pointer array all vectors which contain such numbers, and free their memory (those clauses can be trivially made true).

You can obtain random inputs here (option: Random k-Sat). The first line gives the number of variables and number of clauses.

Marius Minea Last modified: Wed Dec 6 10:30:00 EET 2017