Computer programming - Lab 12

Structures

1.Rational numbers Define a structure type for rational numbers, holding numerator and denominator. Implement functions to add and multiply rationals. Return results that are in canonical form (denominator is positive and gcd with numerator is 1).

2.Continued fractions A real number 0 < x < 1 can be successively approximated in a continued fraction with 1/a1, 1/(a1+1/a2), 1/(a1+1/(a2+1/a3)), ... where a1, a2, a3, ... are natural numbers. In the initial approximation, a1 is ⌊1/x⌋, and one continues using the same rule for the fractional part of the denominator approximated with a1, etc. One obtains a sequence of rational numbers p1/q1, p2/q2, ... that approximate x increasingly well, alternating from above and below.
Define a structure that represents a rational number and compute (recursively) the n^th rational approximation of a fractional number x using a continued fraction.

3.Prime factors. Define a data structure to represent an unsigned number as a product of powers of primes. Write a function that computes the product of two numbers, in the same representation.

4.Predicate formulas. A formula in predicate logic is

a predicate over terms (see exercise in class)
an operator (and, or, not, =>, =) applied to several formulas (one for negation, two for implication and equality, arbitrary number for conjunction/disjunction)
a universal or existential quantifier applied to a variable in a formula

Design a data structure to represent a predicate formula. Write a function to print and another function to read a predicate formula written as an s-expression with operators written in prefix notation, e.g.,
(and (=> p q) (or q r) (not f)). (This syntax is used in the SMT2 format).

Abstract datatypes

1. Implement a function rev_append that takes two (integer) lists l1 and l2 and returns the list obtained by appending the elements of l1 in reverse order in front of l2.

2. Write a function nodup that takes an (integer) list and returns a list with all consecutive duplicates removed.

3. Count the number of segments in a list such that all elements in a segment have the same value and consecutive segments have distinct values.

4. Define a type that can hold a set of alphanumeric characters (both uppercase and lowercase) represented on a 64-bit word and the basic operations on it.

5. Mergesort Write a function that sorts an integer list: 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 list. Free all temporary allocated data (using decons from intlist.h).

Marius Minea

Last modified: Sat Dec 14 18:30:00 EET 2013