Computer programming - Lab 10

Topics for the lab:

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.

4. Splitting into words Write a function that splits a string into words (strings with no whitespace), returning a (dynamically allocated) array of pointers to (dynamically allocated) copies of the words in the string.

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: S0 = 0, S1 = 01, Sn = Sn-1Sn-2 (concatenation).
Write a function that takes an unsigned n and returns Sn. 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.


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

8. 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 pn, a negative integer -n denotes its negation ¬pn; 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). Ignore the first line and use the appropriate of the first two numbers, which give the number of variables and number of clauses.


Marius Minea
Last modified: Mon Dec 5 11:30:00 EET 2016