Computer programming - Lab 11

• 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

Dynamic allocation

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, S₁ = 01, S_n = S_n-1S_n-2 (concatenation).
Write a function that takes an unsigned n and returns S_n. Use at most n allocations and copy operations.

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.

Type casts and void *

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.

String traversals

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.

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.