1 The memory requirements, in KB , for eight computer files are given below. $$\begin{array} { l l l l l l l l } 43 & 172 & 536 & 17 & 314 & 462 & 220 & 231 \end{array}$$ The files are to be grouped into folders. No folder is to contain more than 1000 KB , so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders.
2. Use the first-fit decreasing method to group the files into folders. First-fit decreasing is a quadratic order algorithm.
3. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers?
4. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3 . A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex.
   A simply connected graph is one that is both simple and connected.
5. (a) Draw a graph with five vertices of orders \(1,1,2,2\) and 4 that is neither simple nor connected.
   (b) Explain why your graph from part (a) is not semi-Eulerian.
   (c) Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.
6. (a) Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour.
   (b) Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour.