)
of the following graph? Prove it.
(The chromatic number of a graph is the minimum k such that the graph is k-colourable.)
Total: 50 marks.
Time allotted: 60 minutes
double coeff[4];, and if
coeff[3] is 2,
coeff[2] is 3,
coeff[1] is 5,
and coeff[0] is 6,
we have the polynomial 2x3 + 3x2 + 5x + 6.
Furthermore, we could have initialized the array to have these values in the declaration by writing
double coeff[4] = { 6, 5, 3, 2 };
1. [2 marks]
Write a function add_poly() which adds together two polynomials
by adding together their coefficients.
It takes four arguments: polynomials
z, x, and y,
and integer n which is the degree of the polynomial
(hence the arrays are of size n+1).
It computes z := x + y.
void add_poly(double *z, double *x, double *y, int n)
{
int i;
for (i = 0; i <= n; i++)
z[i] =
}
(You have only one line to fill in above.)
2. [10 marks]
Write a similar function except that it multiplies together two polynomials.
The x and y arrays are of size n+1
(so that the maximum array index is n), but the
z array is of size 2n+1 to hold the product.
void mult_poly(double *z, double *x, double *y, int n)
{
(Answer below.)
3. [8 marks] Here is print_poly(). (Its output is rather ugly, but it's good enough for this midterm.)
void print_poly(double *x, int n)
{
int i;
for (i = n; i >= 0; i--)
if (x[i])
printf(" + %gx**%d", x[i], i);
printf("\n");
}
Using print_poly(), add_poly(), and mult_poly(), write a main program which outputs the simplified form of the polynomial ((x3 + 3x2 + 7)(2x + 6)) + ((4x3 + 5x + 9)(8x3 + 7)).
Assume that the various _poly functions have already been declared, and don't worry about #includes and such; just write the entire main() function.
Answer to all of part 1: see mid-poly.c, which includes the above functions completed; new functions written including the main() requested in question 3; and a better print_poly() without the above defects.
State initial conditions and show two iterations of using the bisection method to find the square root of 3. Your answer might be short but it must be clear. Do not write any code; just state the numbers involved and make it clear where you got them from.
Answer:
First, we need to find two x values such that f(x0) < 0 and f(x1) > 0.
Let x0 = 0 and x1 = 2 (easily chosen by inspecting the function).
First iteration of the bisection method: Let xnew = (x0+x1)/2, which is 1. So f(xnew) = -1, which is negative; thus xnew replaces x0.
Second iteration of the bisection method: Starting with x0=1 and x1=2. Let xnew=1.5 (again the mean). Note that f(xnew) < 0 (easier to do in my head than actually calculating it! 1.52 is 2.25, which is less than 3). So this again replaces x0. Now x0=1.5 and x1=2.
(We could call either 1.5 or 2 "the answer". Obviously, two iterations is entirely insufficient.)
a) Which of these data structures did you use?
Answer: Obviously answers might differ here depending upon what you actually did, but most likely nearly everyone, or perhaps everyone, will say "adjacency matrix". This is worth zero marks! But needed to be able to grade parts (b) and (c).
b) State in a sentence what that data structure looks like.
Answer: An n2 boolean matrix where M[i][j] indicates whether or not there is an edge i->j.
c) What is one advantage of the representation you chose (as compared to the representation you did not choose)?
Some possible answers:
6. [12 marks]
What is the chromatic number ()
of the following graph? Prove it.
(The chromatic number of a graph is the minimum k such that the
graph is k-colourable.)
Answer: The chromatic number of that graph is four. To prove this, we note that it is at least four (because it contains a subgraph which is K4 -- the four rightmost vertices) and that it is at most four (by providing an example colouring).
Example colouring:
