Due: 12:00 Noon Thu Nov 14
You are to create a number of files, as directed below, and then submit them electronically on host lectura.cs.arizona.edu using the command
Please follow the directions below carefully: submissions that don't follow directions will be penalized heavily.
Note: As before, your C code should compile with no errors or warnings when compiled with gcc -Wall. Moreover, each program should exit with a status of 0 if execution proceeds normally, and a status of -1 if any sort of error occurs.
In addition, your programs will be expected to follow the coding guidelines for this class.
Specifically, you are to write a C program, in a file relationships.c, that behaves as follows:
Invocation:Your program will be invoked with a single argument, which is the name of a file specifying parent-child relationships, as described below. If there are too few or too many arguments, or if the argument does not correspond to a readable file, the program should give a descriptive error message indicating the problem (use perror() in the latter case) and exit with status -1.Behavior:Format of the Input File:
You may assume that the input file consists of a series of lines where each line consists of two alphanumeric strings, each of length at most 64, separated by whitespace. Each input line is therefore of the formname1 name2and signifies that name1 is a parent of name2.Simplifying Assumptions about the Input:
- We will not worry about whether a name is male or female (and, therefore, whether a parent-child relationship is father-son, mother-son, father-daughter, etc.).
- We will not make any a priori assumptions about how many parents a person can have (some or all of the parents may be unknown due to lost or incomplete records; at the other extreme, once we consider the ramifications of modern practises, which may involve some or all of egg/sperm donation, surrogate motherhood, adoption, etc., the number of people with some sort of legal claim of parenthood on a person can be quite large).
- We will make the simplifying assumption that relatives, no matter how distant, never marry; in other words, that the family relationship diagram never has any sort of ``diamond structure''. This, in turn, implies that there is exactly one way to go from (the node for) a person to (the node for) an ancestor of that person.
An example of an input file and the corresponding family tree (in this case, part of William Shakespeare's) is shown here.
After reading the file giving parent-child relationships, your program will repeatedly read pairs of names from stdin, until end-of-file is encountered. For each such pairExample:person1 person2your program should print out a pair of integers, separated by a single space, that identifies the relationship of person2 to person1, as discussed below. There will be one such pair of integers per line, i.e., each input line will correspond to an output line. The first number, which we will refer to as M, will denote the number of generations we have to go up the family tree, starting from person1, to get to the nearest common ancestor of person1 and person2; and the second integer, which we will refer to as N, will denote the number of generations we have to go down the family tree, from this common ancestor, to get to person2.If person1 and person2 are not related (i.e., we cannot find a common ancestor for them), your program should print out
-1 -1Notice that relations are not symmetric, so the order of the numbers printed out matters.
- if person1 and person2 are siblings, then M = 1 and N = 1 (here, the nearest common ancestor is either parent of person1 and person2);
- if person1 and person2 are first cousins, then M = 2 and N = 2 (here, the nearest common ancestor is a grandparent of person1 and person2); and
- if person1 and person2 are second cousins thrice removed, then M = 3 and N = 6 (here, the nearest common ancestor is person1's great grandparent).
![]()
Restrictions:
There should not be any fixed hard limits on the input, e.g., the number of people or relationships, or the number of queries allowed. Moreover, the amount of memory used by your program should be proportional to the size of the input.Please do not use realloc for dynamic memory allocation: I would like you to use malloc.
Miscellaneous:
The file/home/cs352/FALL02/hw9_stuff/relationshipsis a SPARC executable that implements the behavior expected of your program.(Just for grins, this executable takes an option -v and generates verbose output that specifies actual relationships in words. Your program is not required to implement this functionality.)
- [50 points ] The file /home/cs352/FALL02/hw9_stuff/goldbach.c is based on the C source code for a solution to the Goldbach conjecture problem from Assignment 2. It reads in a positive integer from stdin, verifies Goldbach's conjecture for all even integers betwen 4 and the value read in, and sums up all the prime summands so found. Unfortunately, this code is not very efficient.
You are to improve the performance of this program using profiling tools (gprof) to identify hot spots. The rules for this performance tuning process are given here. Some general hints and techniques for performance tuning are given here.
The file /home/cs352/FALL02/hw9_stuff/fast_goldbach is (the executable for) a faster version of your program. I will use this executable as the baseline for evaluating your program.
Turn in your modified file, together with a README file that provides the following information for each separate code transformation you carry out:
- profile data (only the flat profiles portion from gprof output);
- the hot spot(s) identified for optimization based on this;
- the performance overheads identified from examining this profile, as well as the changes you made to your code carried out in order to eliminate such overheads; and
- the performance improvement obtained.
The optimized program must still be correct, i.e., for the same input, it should compute the same output as the original program. Moreover, it must do this without in any way "special casing" the particular input being considered (e.g., by skipping all the computation and simply printing out a particular value if the input happens to have some special value).
Given these constraints, your score on this problem will be based on the amount of speedup you are able to achieve (relative to the execution time of the fast_goldbach executable, on lectura), for the input value 500000:
Your (relative) execution time Your score > 5.0 0% 4.0+ - 5.0 10% 3.0+ - 4.0 30% 2.5+ - 3.0 50% 2.0+ - 2.5 60% 1.5+ - 2.0 80% 1.25+ - 1.5 90% 1.0+ - 1.25 100% < 1.0 125%