MATH2800 Introduction to Discrete Structures

Third Exam, Tuesday, November 27, 2007.

You may use one sheet of handwritten notes, but no other sources. The exam consists of seven questions, and lasts fifty minutes. Please work all seven problems. Please show all work clearly and in reasonable detail. Answers without appropriate supporting work or requested explanations may not receive full credit. No calculators are allowed. Please ring your section below:

  1. (20 points) A factory makes custom sports cars at an increasing rate. In the first month only one car is made, in the second month two cars are made, and so on, with $n$ cars made in the $n$th month.
    1. Set up a recurrence relation for the number of cars produced in the first $n$ months by this factory.
    2. Find an explicit formula for the number of cars produced in the first $n$ months by this factory.

  2. (10 points) How many bit strings of length six do not contain the string 0101? (Hint: Consider the starting position of the string 0101.)

  3. (15 points) This question concerns the following graph:

    \begin{picture}(300,200) %(0,-10) \put(0,0){\circle*{10}} \put(0,200){\circle*{1... ...{100}} \put(100,150){\line(1,0){200}} \put(200,0){\line(2,3){100}} \end{picture}

    1. (5 points) Why does this graph have an Euler circuit? (Note: you don't need to give the circuit.)
    2. (10 points) Why must any coloring for this graph use at least four colors? (Note: You don't need to find a coloring.)

  4. (10 points) Show that the graph in Question 3 has a subgraph homeomorphic to $K_5$. What do you conclude?

  5. (10 points) Consider again the graph from questions 3 and 4 with the edge $(b,c)$ deleted, namely:

    \begin{picture}(300,200) \put(0,0){\circle*{10}} \put(0,200){\circle*{10}} \put(... ...{100}} \put(100,150){\line(1,0){200}} \put(200,0){\line(2,3){100}} \end{picture}

    Show that this graph is planar.

  6. (15 points) Use Dijkstra's algorithm to find the shortest path from $a$ to $d$ in the following graph with edge lengths indicated:

    \begin{picture}(300,200) %(0,-10) \put(0,0){\circle*{10}} % put(0,200)\{ circle*... ...t(255,70){6} % put(230,105)\{5\} \put(120,120){1} \put(210,90){11} \end{picture}

  7. (20 points) Find the solution to the recurrence relation

    \begin{displaymath} a_n = 5a_{n-1} - 6a_{n-2} \end{displaymath}

    with initial conditions $a_0=0$ and $a_1=1$.


John Mitchell
2008-11-09