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. 2D vectors Define a structure type for vectors in 2-dimensional space. Define functions for addition, subtraction and magnitude, and to read a vector (space-separated real coordinates of endpoint, assuming zero origin). Use this function to compute the total length of the segments drawn in the path d="..." element read from a SVG file. The path keeps a current point, and the commands are of the form letter x y, with L/l for "line to" and M/m for "move", uppercase for absolute coordinates, and lowecase for relative.

3. Polynomials Define a structure type for polynomials, containing the degree and an array of real coefficients. Write a function that prints a polynomial (in X) and one that adds two polynomials, returning a dynamically allocated result.

4. Big numbers Define a structure type for big numbers, represented in binary, using an arbitrary number of bytes (stored as a structure field). Write a function that takes two big numbers and returns their sum, as a dynamically allocated structure.

5.Continued fractions A real number x can be successively approximated in a continued fraction as a0, a0 + 1/a1, a0 + 1/(a1+1/a2), a0 + 1/(a1+1/(a2+1/a3)), ... where a0 is an integer, and a1, a2, a3, ... are positive naturals. In the initial approximation, a0 is ⌊x⌋. The remaining fractional part is either 0 (we stop), or a number 0 < x1 < 1, so 1/x1 > 1 and we continue applying the same process, taking the integer part, etc. One obtains a sequence of rational numbers p0/q0 (= a0), p1/q1 (= a0 + 1/a1), 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 real number x using a continued fraction.

6.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.

7. CSV files A .csv file contains the grade situation for a class of students. Each line contains fields separated by commas. The first field is the student name, followed by up to 10 fields with real-numbered grades or other characters; any remainder of the line is ignored.
Read the file using an appropriate data structure; you may assume there are at most 200 students. Compute averages for the students that have 10 passing grades. Sort students in decreasing order of their grade averages; break ties in alphabetical order. Print the sorted list with grade averages.

8. Sorting text Design a data structure that stores a line of text, together with its length (in characters) and number of words. Read all lines of a file named on the command line into an array of such structures. Sort and print the file with lines in increasing order of length, breaking ties first in decreasing order of words and then in alphabetical order.

9. List ZIP file contents Write a program that lists the names of the files from a .zip archive (whose name is given on the commandline) in decreasing order of their uncompressed size. Here is a zip archive of sample programs written this semester.
The .zip file format is defined here. We will handle a simplified case; additional checks should be added for a robust program.
All integer values are stored in binary, in little-endian byte order. Since the x86 architecture is little-endian, they will be placed in memory in the correct byte order when read with fread.

First, obtain information about the file contents from the end of central directory record (sec. 4.3.16). For a .zip file with no comments, these are the last 22 bytes of the file. They contain the following relevant information:
```
Offset	Byte count	Meaning
-------------------------------
10      2		number of entries in central directory (list of files)
12	4		size of central directory
16	4		offset of central directory within zipfile
```

Next, read the central directory (after seeking to the appropriate offset). For each archived file, it contains a fixed part (of 46 bytes) and a variable part (including file name), with the following layout

Offset	Byte count	Meaning
-------------------------------
12	2		file modification time
14	2		file modification date
24	4		uncompressed file size
28	2		file name length: fnlen
30	2		extra field length: xlen
32	2		comment length: clen
46	fnlen		file name (not null-terminated)
	xlen		extra field
	clen		comment

Create an array of structures which contain the relevant information for each file (at the minimum, file name, file name length and uncompressed size). Sort and display the files in decreasing order of size.
Optionally, represent time (of the last file modification). In the directory, this is represented using bits, as follows:
- time: seconds (0-29, with granularity multiple of 2 seconds), then minutes and hours
- date: day, month, year (as difference from starting year 1980)
You can use bitfields or bit operations to work with these values.

The following problems are more advanced and optional.

10. Predicate formulas. A formula in predicate logic is

a predicate over terms (variables or functions of terms)
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).

11.Processor simulation A simple processor has registers labeled by lowercase letters and uses the following instructions:

assignment: LD reg val . Equivalent to reg = val. val can be either a register or an integer constant.
arithmetic: ADD reg val, SUB reg val, MUL reg val, DIV reg val . These are equivalent to reg += val, etc.
unconditional jumps: JMP offset . Jumps as many statements forward or backward as indicated by the integer constant offset, counted from the next instruction after the jump. Thus, JMP 0 does nothing. JMP -1 does an infinite loop.
comparison: CMP reg val . Computes reg - val but the result is not stored; it remembers only how the result was with respect to zero (less, equal, etc.)
conditional jumps: JE offset, JNE offset, JG offset, JGE offset, JL offset, JLE offset: jump to the specified offset if the result of the previous CMP or SUB instruction was equal/not equal/greater/greater or equal/less than/less than or equal to zero, else continue with next statement
stop computation: HLT

Design a structure type that can hold such instructions.
Write a function that simulates the execution of code given by such instruction. The function will receive as parameters an array with register values (for all letters) and another array with the code. Use it for the computation of factorial.

Marius Minea

Last modified: Fri Dec 16 8:00:00 EET 2016